Anzeige
Erschienen in:
2010 | OriginalPaper | Buchkapitel
A Cache-Oblivious Implicit Dictionary with the Working Set Property
verfasst von : Gerth Stølting Brodal, Casper Kejlberg-Rasmussen, Jakob Truelsen
Erschienen in: Algorithms and Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. 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.