Suffix Tree Construction and Storage with Limited Main Memory

Schürmann K-B, Stoye J (2003) Forschungsberichte.
Bielefeld: Technische Fakultät der Universität Bielefeld.

Download
OA
Report | English
Author
;
Abstract
Suffix trees have been established as one of the most versatile index structures for unstructured string data like genomic sequences and other strings. In this work, our goal is the development of algorithms for the efficient construction of suffix trees for very large strings and their convenient storage regarding fast access when main memory is limited. We present a construction algorithm which, to the best of our knowledge, is currently the fastest practical construction method for large suffix trees. Further we propose a clustered storage scheme for the suffix tree that takes into account the locality behavior of typical query types, which leads to a significant speed-up particularly for the exact string matching problem. For very large strings the query time is faster than that of other recent index structures like the enhanced suffix array.
Publishing Year
PUB-ID

Cite this

Schürmann K-B, Stoye J. Suffix Tree Construction and Storage with Limited Main Memory. Forschungsberichte. Bielefeld: Technische Fakultät der Universität Bielefeld; 2003.
Schürmann, K. - B., & Stoye, J. (2003). Suffix Tree Construction and Storage with Limited Main Memory (Forschungsberichte). Bielefeld: Technische Fakultät der Universität Bielefeld.
Schürmann, K. - B., and Stoye, J. (2003). Suffix Tree Construction and Storage with Limited Main Memory. Forschungsberichte, Bielefeld: Technische Fakultät der Universität Bielefeld.
Schürmann, K.-B., & Stoye, J., 2003. Suffix Tree Construction and Storage with Limited Main Memory, Forschungsberichte, Bielefeld: Technische Fakultät der Universität Bielefeld.
K.-B. Schürmann and J. Stoye, Suffix Tree Construction and Storage with Limited Main Memory, Forschungsberichte, Bielefeld: Technische Fakultät der Universität Bielefeld, 2003.
Schürmann, K.-B., Stoye, J.: Suffix Tree Construction and Storage with Limited Main Memory. Forschungsberichte. Technische Fakultät der Universität Bielefeld, Bielefeld (2003).
Schürmann, Klaus-Bernd, and Stoye, Jens. Suffix Tree Construction and Storage with Limited Main Memory. Bielefeld: Technische Fakultät der Universität Bielefeld, 2003. Forschungsberichte.
Main File(s)
Access Level
OA Open Access

This data publication is cited in the following publications:
This publication cites the following data publications:

Export

0 Marked Publications

Open Data PUB

Search this title in

Google Scholar