1 Department of Computer Science, Faculty of Science, Aarhus University, Aarhus University2 Department of Computer Science, Science and Technology, Aarhus University3 Syddansk Universitet4 Department of Computer Science, Science and Technology, Aarhus University
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