A Cache-Oblivious Implicit Dictionary with the Working Set Property

Gerth Stølting Brodal, Casper Kejlberg-Rasmussen, and Jakob Truelsen

In Proc. 21th Annual International Symposium on Algorithms and Computation, Part II, volume 6507 of Lecture Notes in Computer Science, pages 37-48. Springer Verlag, Berlin, 2010.

Abstract

In this paper we present an implicit dictionary with the working set property i.e. a dictionary supporting insert(e), delete(x) and predecessor(x) in O(log n) time and search(x) in O(log l) time, where n is the number of elements stored in the dictionary and l is the number of distinct elements searched for since the element with key x was last searched for. The dictionary stores the elements in an array of size n using no additional space. In the cache-oblivious model the operations insert(e), delete(x) and predecessor(x) cause O(log_B n) cache-misses and search(x) causes O(log_B l) cache-misses.

Copyright notice

© Springer-Verlag Berlin Heidelberg 2010. All rights reserved.

Online version

isaac10implicit.pdf (316 Kb)

DOI

10.1007/978-3-642-17514-5_4

Links

• Springer Verlag
• Lecture Notes in Computer Science

BIBT_EX entry

@incollection{isaac10implicit,
  author = "Gerth St{\o}lting Brodal and Casper Kejlberg-Rasmussen and Jakob Truelsen",
  booktitle = "Proc. 21th Annual International Symposium on Algorithms and Computation, Part II",
  doi = "10.1007/978-3-642-17514-5_4",
  isbn = "978-3-642-17513-8",
  pages = "37-48",
  publisher = "Springer {V}erlag, Berlin",
  series = "Lecture Notes in Computer Science",
  title = "A Cache-Oblivious Implicit Dictionary with the Working Set Property",
  volume = "6507",
  year = "2010"
}