A Cache-Oblivious Implicit Dictionary with the Working Set Property

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperConference articleResearchpeer-review

  • Department of Computer Science
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 languageEnglish
Book seriesLecture Notes in Computer Science
Volume6507
Pages (from-to)37-48
Number of pages12
ISSN0302-9743
DOIs
Publication statusPublished - 2010
EventInternational Symposium on Algorithms and Computation. ISAAC 2010 - Jeju, Korea, Republic of
Duration: 15 Dec 201017 Dec 2010
Conference number: 21

Conference

ConferenceInternational Symposium on Algorithms and Computation. ISAAC 2010
Number21
CountryKorea, Republic of
CityJeju
Period15/12/201017/12/2010

Bibliographical 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

    Research areas

  • implicit, cache-oblivious, dictionary

See relations at Aarhus University Citationformats

ID: 32836686