Aarhus University Seal / Aarhus Universitets segl

Leibniz International Proceedings in Informatics: Invited talk

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperConference articleResearch

In this paper we present an implicit dynamic dictionary with the working-set property, supporting insert(e) and delete(e) in O(log n) time, predecessor(e) in O(log l_{p(e)}) time, successor(e) in O(log l_{s(e)}) time and search(e) in O(log min(l_{p(e)},l_{e}, l_{s(e)})) time, where n is the number of elements stored in the dictionary, l_{e} is the number of distinct elements searched for since element e was last searched for and p(e) and s(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 *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.
Original languageEnglish
JournalLeibniz International Proceedings in Informatics
Pages (from-to)11-12
Number of pages2
Publication statusPublished - 2014
Event Symposium on Theoretical Aspects of Computer Science - Lyon, France
Duration: 5 Mar 20148 Mar 2014
Conference number: 31


Conference Symposium on Theoretical Aspects of Computer Science

Bibliographical note

Title of the vol.: 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012 / ed. by Christoph Dürr and Thomas Wilke.
ISBN: 978-3-939897-35-4

    Research areas

  • working-set property, dictionary, implicit, cache-oblivious, worst-case, external memory, I/O efficient

See relations at Aarhus University Citationformats

ID: 81805315