Cache-Oblivious Implicit Predecessor Dictionaries with the Working Set Property

Gerth Stølting Brodal and Casper Kejlberg-Rasmussen

In Proc. 29th Annual Symposium on Theoretical Aspects of Computer Science, volume 14 of Leibniz International Proceedings in Informatics, pages 112-123. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany, 2012.

Abstract

In this paper we present an implicit dynamic dictionary with the working-set property, supporting insert(e) and delete(e) in O(log n) time, predecessor(e) in O(log lp(e)) time, successor(e) in O(log ls(e)) time and search(e) in O(log min(lp(e),le,ls(e))) time, where n is the number of elements stored in the dictionary, le is the number of distinct elements searched for since element e was last searched for and p(e) and s(e) are the predecessor and successor of e, respectively. The time-bounds are all worst-case. The dictionary stores the elements in an array of size n using no additional space. In the cache-oblivious model the log is base B and the cache-obliviousness is due to our black box use of an existing cache-oblivious implicit dictionary. This is the first implicit dictionary supporting predecessor and successor searches in the working-set bound. Previous implicit structures required O(log n) time.

Copyright notice

Creative Commons License ND

Online version

stacs12.pdf (661 Kb)

DOI

10.4230/LIPIcs.STACS.2012.112

BIBTEX entry

@incollection{stacs12,
  author = "Gerth St{\o}lting Brodal and Casper Kejlberg-Rasmussen",
  booktitle = "Proc. 29th Annual Symposium on Theoretical Aspects of Computer Science",
  doi = "10.4230/LIPIcs.STACS.2012.112",
  isbn = "978-3-939897-35-4",
  pages = "112-123",
  publisher = "Schloss Dagstuhl - Leibniz-Zentrum f\"ur Informatik, Dagstuhl Publishing, Germany",
  series = "Leibniz International Proceedings in Informatics",
  title = "Cache-Oblivious Implicit Predecessor Dictionaries with the Working Set Property",
  volume = "14",
  year = "2012"
}

Other versions