Efficient Representation for Online Suffix Tree Construction

N. Jesper Larsson; Kasper Fuglsang; Kenneth Karlsson

doi:10.1007/978-3-319-07959-2_34

Efficient Representation for Online Suffix Tree Construction

N. Jesper Larsson, Kasper Fuglsang, Kenneth Karlsson

Algorithms

Publikation: Konference artikel i Proceeding eller bog/rapport kapitel › Konferencebidrag i proceedings › Forskning › peer review

Abstract

Suffix tree construction algorithms based on suffix links are popular because they are simple to implement, can operate online in linear time, and because the suffix links are often convenient for pattern matching. We present an approach using edge-oriented suffix links, which reduces the number of branch lookup operations (known to be a bottleneck in construction time) with some additional techniques to reduce construction cost. We discuss various effects of our approach and compare it to previous techniques. An experimental evaluation shows that we are able to reduce construction time to around half that of the original algorithm, and about two thirds that of previously known branch-reduced construction.

Originalsprog	Engelsk
Titel	Experimental Algorithms : 13th International Symposium, SEA 2014
Redaktører	Joachim Gudmundsson, Jyrki Katajainen
Antal sider	12
Forlag	Springer
Publikationsdato	2014
Sider	400-411
ISBN (Trykt)	978-3-319-07958-5
ISBN (Elektronisk)	978-3-319-07959-2
DOI	https://doi.org/10.1007/978-3-319-07959-2_34
Status	Udgivet - 2014
Begivenhed	Symposium on Experimental Algorithms 2014 - Copenhagen, Danmark Varighed: 29 jun. 2014 → 1 jul. 2014 http://www.diku.dk/sea2014/

Konference

Konference	Symposium on Experimental Algorithms 2014
Land/Område	Danmark
By	Copenhagen
Periode	29/06/2014 → 01/07/2014
Internetadresse	http://www.diku.dk/sea2014/

Navn	Lecture Notes in Computer Science
Vol/bind	8504
ISSN	0302-9743

Adgang til dokumentet

10.1007/978-3-319-07959-2_34

http://dx.doi.org/10.1007/978-3-319-07959-2_34

Citationsformater

@inproceedings{5a6ab72c729a4a33883351b5bc3092f8,

title = "Efficient Representation for Online Suffix Tree Construction",

abstract = "Suffix tree construction algorithms based on suffix links are popular because they are simple to implement, can operate online in linear time, and because the suffix links are often convenient for pattern matching. We present an approach using edge-oriented suffix links, which reduces the number of branch lookup operations (known to be a bottleneck in construction time) with some additional techniques to reduce construction cost. We discuss various effects of our approach and compare it to previous techniques. An experimental evaluation shows that we are able to reduce construction time to around half that of the original algorithm, and about two thirds that of previously known branch-reduced construction.",

author = "Larsson, {N. Jesper} and Kasper Fuglsang and Kenneth Karlsson",

year = "2014",

doi = "10.1007/978-3-319-07959-2_34",

language = "English",

isbn = "978-3-319-07958-5",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "400--411",

editor = "Joachim Gudmundsson and Jyrki Katajainen",

booktitle = "Experimental Algorithms",

address = "Germany",

note = "Symposium on Experimental Algorithms 2014, SEA 2014 ; Conference date: 29-06-2014 Through 01-07-2014",

url = "http://www.diku.dk/sea2014/",

}

Larsson, NJ, Fuglsang, K & Karlsson, K 2014, Efficient Representation for Online Suffix Tree Construction. i J Gudmundsson & J Katajainen (red), Experimental Algorithms: 13th International Symposium, SEA 2014. Springer, Lecture Notes in Computer Science, bind 8504, s. 400-411, Symposium on Experimental Algorithms 2014, Copenhagen, Danmark, 29/06/2014. https://doi.org/10.1007/978-3-319-07959-2_34

Efficient Representation for Online Suffix Tree Construction. / Larsson, N. Jesper; Fuglsang, Kasper; Karlsson, Kenneth.
Experimental Algorithms: 13th International Symposium, SEA 2014. red. / Joachim Gudmundsson; Jyrki Katajainen. Springer, 2014. s. 400-411 (Lecture Notes in Computer Science, Bind 8504).

Publikation: Konference artikel i Proceeding eller bog/rapport kapitel › Konferencebidrag i proceedings › Forskning › peer review

TY - GEN

T1 - Efficient Representation for Online Suffix Tree Construction

AU - Larsson, N. Jesper

AU - Fuglsang, Kasper

AU - Karlsson, Kenneth

PY - 2014

Y1 - 2014

N2 - Suffix tree construction algorithms based on suffix links are popular because they are simple to implement, can operate online in linear time, and because the suffix links are often convenient for pattern matching. We present an approach using edge-oriented suffix links, which reduces the number of branch lookup operations (known to be a bottleneck in construction time) with some additional techniques to reduce construction cost. We discuss various effects of our approach and compare it to previous techniques. An experimental evaluation shows that we are able to reduce construction time to around half that of the original algorithm, and about two thirds that of previously known branch-reduced construction.

AB - Suffix tree construction algorithms based on suffix links are popular because they are simple to implement, can operate online in linear time, and because the suffix links are often convenient for pattern matching. We present an approach using edge-oriented suffix links, which reduces the number of branch lookup operations (known to be a bottleneck in construction time) with some additional techniques to reduce construction cost. We discuss various effects of our approach and compare it to previous techniques. An experimental evaluation shows that we are able to reduce construction time to around half that of the original algorithm, and about two thirds that of previously known branch-reduced construction.

U2 - 10.1007/978-3-319-07959-2_34

DO - 10.1007/978-3-319-07959-2_34

M3 - Article in proceedings

SN - 978-3-319-07958-5

T3 - Lecture Notes in Computer Science

SP - 400

EP - 411

BT - Experimental Algorithms

A2 - Gudmundsson, Joachim

A2 - Katajainen, Jyrki

PB - Springer

T2 - Symposium on Experimental Algorithms 2014

Y2 - 29 June 2014 through 1 July 2014

ER -

Efficient Representation for Online Suffix Tree Construction

Abstract

Konference

Adgang til dokumentet

Fingeraftryk

Citationsformater