# Cache-oblivious String Dictionaries

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*(log_{B} *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)

**BIBT**_{E}X 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"
}