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 l_p(e)) time, successor(e) in O(log l_s(e)) time and search(e) in O(log min(l_p(e),l_e,l_s(e))) time, where n is the number of elements stored in the dictionary, l_e 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

• arxiv.org/abs/1112.5472

BIBT_EX entry

@techreport{arxiv1112.5472,
  author = "Gerth Stø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"
}