A Cache-Oblivious Implicit Dictionary with the Working Set Property

Gerth Stølting Brodal; Casper Kejlberg-Rasmussen; Jakob Truelsen

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

A Cache-Oblivious Implicit Dictionary with the Working Set Property

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

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaper › Conference article › Research › peer-review

Abstract

In this paper we present an implicit dictionary with the working set property i.e. a dictionary supporting \op{insert}($e$), \op{delete}($x$) and \op{predecessor}($x$) in~$\O(\log n)$ time and \op{search}($x$) in $\O(\log\ell)$ time, where $n$ is the number of elements stored in the dictionary and $\ell$ 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 \emph{no} additional space. In the cache-oblivious model the operations \op{insert}($e$), \op{delete}($x$) and \op{predecessor}($x$) cause $\O(\log_B n)$ cache-misses and \op{search}($x$) causes $\O(\log_B \ell)$ cache-misses.

Original language	English
Book series	Lecture Notes in Computer Science
Volume	6507
Pages (from-to)	37-48
Number of pages	12
ISSN	0302-9743
DOIs	https://doi.org/10.1007/978-3-642-17514-5_4
Publication status	Published - 2010
Event	International Symposium on Algorithms and Computation. ISAAC 2010 - Jeju, Korea, Republic of Duration: 15 Dec 2010 → 17 Dec 2010 Conference number: 21

Conference

Conference	International Symposium on Algorithms and Computation. ISAAC 2010
Number	21
Country/Territory	Korea, Republic of
City	Jeju
Period	15/12/2010 → 17/12/2010

Keywords

implicit
cache-oblivious
dictionary

Access to Document

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

Cite this

@inproceedings{fee24000d13011df8cb9000ea68e967b,

title = "A Cache-Oblivious Implicit Dictionary with the Working Set Property",

abstract = "In this paper we present an implicit dictionary with the working set property i.e. a dictionary supporting \op{insert}($e$), \op{delete}($x$) and \op{predecessor}($x$) in~$\O(\log n)$ time and \op{search}($x$) in $\O(\log\ell)$ time, where $n$ is the number of elements stored in the dictionary and $\ell$ 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 \emph{no} additional space. In the cache-oblivious model the operations \op{insert}($e$), \op{delete}($x$) and \op{predecessor}($x$) cause $\O(\log_B n)$ cache-misses and \op{search}($x$) causes $\O(\log_B \ell)$ cache-misses.",

keywords = "implicit, cache-oblivious, dictionary",

author = "Brodal, {Gerth St{\o}lting} and Casper Kejlberg-Rasmussen and Jakob Truelsen",

note = "Title of the vol.: Algorithms and Computation. Proceedings. Part II / Otfried Cheong, Kyung-Yong Chwa and Kunsoo Park (eds.) ISBN: 978-3-642-17513-8; International Symposium on Algorithms and Computation. ISAAC 2010 ; Conference date: 15-12-2010 Through 17-12-2010",

year = "2010",

doi = "10.1007/978-3-642-17514-5_4",

language = "English",

volume = "6507",

pages = "37--48",

journal = "Lecture Notes in Computer Science",

issn = "0302-9743",

publisher = "Springer",

}

TY - GEN

T1 - A Cache-Oblivious Implicit Dictionary with the Working Set Property

AU - Brodal, Gerth Stølting

AU - Kejlberg-Rasmussen, Casper

AU - Truelsen, Jakob

N1 - Conference code: 21

PY - 2010

Y1 - 2010

N2 - In this paper we present an implicit dictionary with the working set property i.e. a dictionary supporting \op{insert}($e$), \op{delete}($x$) and \op{predecessor}($x$) in~$\O(\log n)$ time and \op{search}($x$) in $\O(\log\ell)$ time, where $n$ is the number of elements stored in the dictionary and $\ell$ 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 \emph{no} additional space. In the cache-oblivious model the operations \op{insert}($e$), \op{delete}($x$) and \op{predecessor}($x$) cause $\O(\log_B n)$ cache-misses and \op{search}($x$) causes $\O(\log_B \ell)$ cache-misses.

AB - In this paper we present an implicit dictionary with the working set property i.e. a dictionary supporting \op{insert}($e$), \op{delete}($x$) and \op{predecessor}($x$) in~$\O(\log n)$ time and \op{search}($x$) in $\O(\log\ell)$ time, where $n$ is the number of elements stored in the dictionary and $\ell$ 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 \emph{no} additional space. In the cache-oblivious model the operations \op{insert}($e$), \op{delete}($x$) and \op{predecessor}($x$) cause $\O(\log_B n)$ cache-misses and \op{search}($x$) causes $\O(\log_B \ell)$ cache-misses.

KW - implicit

KW - cache-oblivious

KW - dictionary

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

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

M3 - Conference article

SN - 0302-9743

VL - 6507

SP - 37

EP - 48

JO - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

T2 - International Symposium on Algorithms and Computation. ISAAC 2010

Y2 - 15 December 2010 through 17 December 2010

ER -

A Cache-Oblivious Implicit Dictionary with the Working Set Property

Abstract

Conference

Keywords

Access to Document

Fingerprint

Cite this