Cache-Oblivious Implicit Predecessor Dictionaries with the Working Set Property

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

2011-12-22

arxiv.org/abs/1112.5472v3

Computer Science

Data Structures and Algorithms

An extended abstract is accepted at STACS 2012, this is the full version of that paper with the same name "Cache-Oblivious Imp

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Cache-Oblivious Implicit Predecessor Dictionaries with the Working Set Property does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Cache-Oblivious Implicit Predecessor Dictionaries with the Working Set Property, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cache-Oblivious Implicit Predecessor Dictionaries with the Working Set Property will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-191559