We present static cache-oblivious dictionary structures for strings which provide analogues of tries and suffix trees in the cache-oblivious model. Our construction takes as input either a set of strings to store, a single string for which all suffixes are to be stored, a trie, a compressed trie, or a suffix tree, and creates a cache-oblivious data structure which performs prefix queries in O(logB n + |P|/B) I/Os, where n is the number of leaves in the trie, P is the query string, and B is the block size. This query cost is optimal for unbounded alphabets. The data structure uses linear space.
Soda '06 Proceedings of the Seventeenth Annual Acm-siam Symposium on Discrete Algorithm, 2006, p. 581-590
Main Research Area:
Annual ACM-SIAM Symposium on Discrete Algorithms, 2006