Cache-Oblivious Implicit Predecessor Dictionaries with the Working-Set Property

In this paper we present an implicit dynamic dictionary with the working-set property, support-ing insert(e) and delete(e) in O(logn) time, predecessor(e) in O(log `p(e)) time, successor(e) in O(log `s(e)) time and search(e) in O(log min(`p(e), `e, `s(e))) time, where n is the number of ele-ments stored in the dictionary, `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 impli-cit dictionary supporting predecessor and successor searches in the working-set bound. Previous implicit structures required O(logn) time