TY - GEN
T1 - Suffix trays and suffix trists
T2 - 33rd International Colloquium on Automata, Languages and Programming, ICALP 2006
AU - Cole, Richard
AU - Kopelowitz, Tsvi
AU - Lewenstein, Moshe
PY - 2006
Y1 - 2006
N2 - Suffix trees and suffix arrays are two of the most widely used data structures for text indexing. Each uses linear space and can be constructed in linear time [3,5,6,7]. However, when it comes to answering queries, the prior does so in O(m log |Σ|) time, where m is the query size, |Σ| is the alphabet size, and the latter does so in O(m + log n), where n is the text size. We propose a novel way of combining the two into, what we call, a suffix tray. The space and construction time remain linear and the query time improves to O(m + log |Σ|). We also consider the online version of indexing, where the indexing structure continues to update the text online and queries are answered in tandem. Here we suggest a suffix trist, a cross between a suffix tree and a suffix list. It supports queries in O(m+log |Σ|). The space and text update time of a suffix trist are the same as for the suffix tree or the suffix list.
AB - Suffix trees and suffix arrays are two of the most widely used data structures for text indexing. Each uses linear space and can be constructed in linear time [3,5,6,7]. However, when it comes to answering queries, the prior does so in O(m log |Σ|) time, where m is the query size, |Σ| is the alphabet size, and the latter does so in O(m + log n), where n is the text size. We propose a novel way of combining the two into, what we call, a suffix tray. The space and construction time remain linear and the query time improves to O(m + log |Σ|). We also consider the online version of indexing, where the indexing structure continues to update the text online and queries are answered in tandem. Here we suggest a suffix trist, a cross between a suffix tree and a suffix list. It supports queries in O(m+log |Σ|). The space and text update time of a suffix trist are the same as for the suffix tree or the suffix list.
UR - http://www.scopus.com/inward/record.url?scp=33746367784&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33746367784&partnerID=8YFLogxK
U2 - 10.1007/11786986_32
DO - 10.1007/11786986_32
M3 - Conference contribution
AN - SCOPUS:33746367784
SN - 3540359044
SN - 9783540359043
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 358
EP - 369
BT - Automata, Languages and Programming - 33rd International Colloquium, ICALP 2006, Proceedings
PB - Springer Verlag
Y2 - 10 July 2006 through 14 July 2006
ER -