2026-07-23T06:22:02Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3410 2024-03-06T10:34:09Z ddc:004 open_access

Cache-Oblivious Implicit Predecessor Dictionaries with the Working-Set Property Stølting Brodal, Gerth Kejlberg-Rasmussen, Casper working-set property dictionary implicit cache-oblivious worst-case external memory I/O efficient 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Gerth Stølting Brodal and Casper Kejlberg-Rasmussen 2012 Is Part Of LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2012.112 urn:nbn:de:0030-drops-34101 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.112 eng https://creativecommons.org/licenses/by-nd/3.0/legalcode