Fully De-Amortized Cuckoo Hashing for Cache-Oblivious Dictionaries and Multimaps

Details Fully De-Amortized Cuckoo Hashing for Cache-Oblivious Dictionaries and Multimaps Fully De-Amortized Cuckoo Hashing for Cache-Oblivious Dictionaries and Multimaps

2011-07-21

arxiv.org/abs/1107.4378v1

Computer Science

Data Structures and Algorithms

27 pages, 1 table

Scientific paper

A dictionary (or map) is a key-value store that requires all keys be unique, and a multimap is a key-value store that allows for multiple values to be associated with the same key. We design hashing-based indexing schemes for dictionaries and multimaps that achieve worst-case optimal performance for lookups and updates, with a small or negligible probability the data structure will require a rehash operation, depending on whether we are working in the the external-memory (I/O) model or one of the well-known versions of the Random Access Machine (RAM) model. One of the main features of our constructions is that they are \emph{fully de-amortized}, meaning that their performance bounds hold without one having to tune their constructions with certain performance parameters, such as the constant factors in the exponents of failure probabilities or, in the case of the external-memory model, the size of blocks or cache lines and the size of internal memory (i.e., our external-memory algorithms are cache oblivious). Our solutions are based on a fully de-amortized implementation of cuckoo hashing, which may be of independent interest. This hashing scheme uses two cuckoo hash tables, one "nested" inside the other, with one serving as a primary structure and the other serving as an auxiliary supporting queue/stash structure that is super-sized with respect to traditional auxiliary structures but nevertheless adds negligible storage to our scheme. This auxiliary structure allows the success probability for cuckoo hashing to be very high, which is useful in cryptographic or data-intensive applications.

Affiliated with

Also associated with

No associations

Rating

Fully De-Amortized Cuckoo Hashing for Cache-Oblivious Dictionaries and Multimaps 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 Fully De-Amortized Cuckoo Hashing for Cache-Oblivious Dictionaries and Multimaps, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fully De-Amortized Cuckoo Hashing for Cache-Oblivious Dictionaries and Multimaps will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-675668