Compressed suffix arrays for massive data
J Sirén - International Symposium on String Processing and …, 2009 - Springer
International Symposium on String Processing and Information Retrieval, 2009•Springer
We present a fast space-efficient algorithm for constructing compressed suffix arrays (CSA).
The algorithm requires O (n log n) 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.
The algorithm requires O (n log n) 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.
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.
Springer
以上显示的是最相近的搜索结果。 查看全部搜索结果