Abstract
In this paper we present an implicit dynamic dictionary with the working-set
property, supporting \op{insert}($e$) and \op{delete}($e$) in $\O(\log n)$
time, \op{predecessor}($e$) in $\O(\log \ws{\pred(e)})$ time,
\op{successor}($e$) in $\O(\log \ws{\succ(e)})$ time and \op{search}($e$) in
$\O(\log \min(\ws{\pred(e)},\ws{e}, \ws{\succ(e)}))$ time, where $n$ is the
number of elements stored in the dictionary, $\ws{e}$ is the number of distinct
elements searched for since element~$e$ was last searched for and $\pred(e)$
and $\succ(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 \emph{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.
property, supporting \op{insert}($e$) and \op{delete}($e$) in $\O(\log n)$
time, \op{predecessor}($e$) in $\O(\log \ws{\pred(e)})$ time,
\op{successor}($e$) in $\O(\log \ws{\succ(e)})$ time and \op{search}($e$) in
$\O(\log \min(\ws{\pred(e)},\ws{e}, \ws{\succ(e)}))$ time, where $n$ is the
number of elements stored in the dictionary, $\ws{e}$ is the number of distinct
elements searched for since element~$e$ was last searched for and $\pred(e)$
and $\succ(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 \emph{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.
| Originalsprog | Engelsk |
|---|---|
| Bogserie | Leibniz International Proceedings in Informatics |
| Vol/bind | 14 |
| Sider (fra-til) | 112--123 |
| Antal sider | 12 |
| ISSN | 1868-8969 |
| DOI | |
| Status | Udgivet - 2012 |
| Begivenhed | Symposium on Theoretical Aspects of Computer Science - Paris, Frankrig Varighed: 1 mar. 2012 → 3 mar. 2012 |
Konference
| Konference | Symposium on Theoretical Aspects of Computer Science |
|---|---|
| Land/Område | Frankrig |
| By | Paris |
| Periode | 01/03/2012 → 03/03/2012 |
Emneord
- working-set property
- dictionary
- implicit
- cache-oblivious
- worst-case
- external memory
- I/O efficient