ITU

Efficient Representation for Online Suffix Tree Construction

Research output: Conference Article in Proceeding or Book/Report chapterArticle in proceedingsResearchpeer-review

View graph of relations

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.
Original languageEnglish
Title of host publicationExperimental Algorithms : 13th International Symposium, SEA 2014
EditorsJoachim Gudmundsson, Jyrki Katajainen
Number of pages12
PublisherSpringer
Publication date2014
Pages400-411
ISBN (Print)978-3-319-07958-5
ISBN (Electronic)978-3-319-07959-2
DOIs
Publication statusPublished - 2014
EventSymposium on Experimental Algorithms 2014 - Copenhagen, Denmark
Duration: 29 Jun 20141 Jul 2014
http://www.diku.dk/sea2014/

Conference

ConferenceSymposium on Experimental Algorithms 2014
LandDenmark
ByCopenhagen
Periode29/06/201401/07/2014
Internetadresse
SeriesLecture Notes in Computer Science
Volume8504
ISSN0302-9743

ID: 76476122