Abstract: 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(logBn + |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.
Publication Year: 2006
Publication Date: 2006-01-22
Language: en
Type: article
Access and Citation
Cited By Count: 39
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot