Paper Info
Title
Compressed Suffix Arrays for Massive Data
Abstract
We present a fast space-efficient algorithm for constructing compressed suffix arrays (CSA). The algorithm requires O (n logn ) time in the worst case, and only O (n ) bits of extra space in addition to the CSA. As the basic step, we describe an algorithm for merging two CSAs. We show that the construction algorithm can be parallelized in a symmetric multiprocessor system, and discuss the possibility of a distributed implementation. We also describe a parallel implementation of the algorithm, capable of indexing several gigabytes per hour.
Year
DOI
Venue
2009
10.1007/978-3-642-03784-9_7
SPIRE
Keywords
Field
DocType
basic step,symmetric multiprocessor system,parallel implementation,massive data,compressed suffix arrays,worst case,suffix array,fast space-efficient algorithm,n logn,construction algorithm,extra space,preprint,indexation
Partial index,Suffix,Computer science,Parallel computing,Symmetric multiprocessor system,Search engine indexing,Compressed suffix array,Merge (version control),Auxiliary memory
Conference
Volume
ISSN
Citations 
5721
0302-9743
13
PageRank 
References 
Authors
0.94
23
1
Name
Order
Citations
PageRank
Jouni Sirén122214.85