Compressed Suffix Arrays for Massive Data

Näytä kaikki kuvailutiedot

Permalink

http://hdl.handle.net/10138/1208
Julkaisun nimi: Compressed Suffix Arrays for Massive Data
Tekijä: Sirén, Jouni
Tiivistelmä: 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.
URI: http://hdl.handle.net/10138/1208
Päiväys: 2009-06-15


Tiedostot

Latausmäärä yhteensä: Ladataan...

Tiedosto(t) Koko Formaatti Näytä
paper.pdf 176.4KB PDF Avaa tiedosto

Viite kuuluu kokoelmiin:

Näytä kaikki kuvailutiedot