Cache-Oblivious Implicit Predecessor Dictionaries with the Working Set Property

Gerth Stølting Brodal and Casper Kejlberg-Rasmussen

Technical Report, 1112.5472, arXiv.org, 16 pages, December 2011.

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.

Online version

arxiv1112.5472.pdf (795 Kb)

Links

BIBTEX entry

@techreport{arxiv1112.5472,
  author = "Gerth St{\o}lting Brodal and Casper Kejlberg-Rasmussen",
  institution = "arXiv.org",
  month = "December",
  number = "1112.5472",
  pages = "16",
  title = "Cache-Oblivious Implicit Predecessor Dictionaries with the Working Set Property",
  year = "2011"
}