Please use this identifier to cite or link to this item:
|Title:||Breaking a time-and-space barrier in constructing full-text indices|
|Citation:||Hon, W.-K.,Sadakane, K.,Sung, W.-K. (2003). Breaking a time-and-space barrier in constructing full-text indices. Annual Symposium on Foundations of Computer Science - Proceedings : 251-260. ScholarBank@NUS Repository.|
|Abstract:||Suffix trees and suffix arrays are the most prominent full-text indices, and their construction algorithms are well studied. It has been open for a long time whether these indices can be constructed in both o(n log n) time and o(n log n)-bit working space, where n denotes the length of the text. In the literature, the fastest algorithm runs in O(n) time, while it requires O(n log n)-bit working space. On the other hand, the most space-efficient algorithm requires O(n)-bit working space while it runs in O(n log n) time. This paper breaks the long-standing time-and-space barrier under the unit-cost word RAM. We give an algorithm for constructing the suffix array which takes O(n) time and O(n)-bit working space, for texts with constant-size alphabets. Note that both the time and the space bounds are optimal. For constructing the suffix tree, our algorithm requires O(n logε n) time and O(n)-bit working space for any 0 < ε < 1. Apart from that, our algorithm can also be adopted to build other existing full-text indices, such as Compressed Suffix Tree, Compressed Suffix Arrays and FM-index. We also study the general case where the size of the alphabet A is not constant. Our algorithm can construct a suffix array and a suffix tree using optimal O(n log|A|)-bit working space while running in O(n log log |A|) time and O(n logε n) time, respectively. These are the first algorithms that achieve o(n log n) time with optimal working space, under a reasonable assumption that log|A| = o(log n).|
|Source Title:||Annual Symposium on Foundations of Computer Science - Proceedings|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Nov 17, 2018
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.