Cache-oblivious String Dictionaries

Gerth Stølting Brodal and Rolf Fagerberg

In Proc. 17th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 581-590, 2006.

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(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.

Copyright notice

Copyright © 2006 by the Association for Computer Machinery, Inc., and the Society for Industrial and Applied Mathematics.

Online version

soda06.pdf (204 Kb)

DOI

10.1145/1109557.1109621

Slides

soda06.pdf (809 Kb)

BIBTEX entry

@inproceedings{soda06,
  author = "Gerth St{\o}lting Brodal and Rolf Fagerberg",
  booktitle = "Proc. 17th Annual ACM-SIAM Symposium on Discrete Algorithms",
  doi = "10.1145/1109557.1109621",
  isbn = "0-89871-605-5",
  pages = "581-590",
  title = "Cache-oblivious String Dictionaries",
  year = "2006"
}