2010 | OriginalPaper | Chapter
A Cache-Oblivious Implicit Dictionary with the Working Set Property
Authors : Gerth Stølting Brodal, Casper Kejlberg-Rasmussen, Jakob Truelsen
Published in: Algorithms and Computation
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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
${\mathcal O}(\log n)$
time and
search
(
x
) in
${\mathcal O}(\log\ell)$
time, where
n
is the number of elements stored in the dictionary and ℓ 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
${\mathcal O}(\log_B n)$
cache-misses and
search
(
x
) causes
${\mathcal O}(\log_B \ell)$
cache-misses.