Leibniz International Proceedings in Informatics: Invited talk

TY - GEN

T1 - Leibniz International Proceedings in Informatics

T2 - Symposium on Theoretical Aspects of Computer Science

AU - Miltersen, Peter Bro

N1 - Conference code: 31

PY - 2014

Y1 - 2014

N2 - 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.

AB - 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.

KW - Real Algebraic Geometry

KW - Computational Game Theory

KW - working-set property

KW - dictionary

KW - implicit

KW - cache-oblivious

KW - worst-case

KW - external memory

KW - I/O efficient

U2 - 10.4230/LIPIcs.STACS.2014.11

DO - 10.4230/LIPIcs.STACS.2014.11

M3 - Conference article

SN - 1868-8969

VL - 25

SP - 11

EP - 12

JO - Leibniz International Proceedings in Informatics

JF - Leibniz International Proceedings in Informatics

Y2 - 5 March 2014 through 8 March 2014

ER -