NDLI: Backyard Cuckoo Hashing: Constant Worst-Case Operations with a Succinct Representation

Content Provider	IEEE Xplore Digital Library
Author	Arbitman, Y. Naor, M. Segev, G.
Copyright Year	2010
Abstract	The performance of a dynamic dictionary is measured mainly by its update time, lookup time, and space consumption. In terms of update time and lookup time there are known constructions that guarantee constant-time operations in the worst case with high probability, and in terms of space consumption there are known constructions that use essentially optimal space. However, although the first analysis of a dynamic dictionary dates back more than 45 years ago (when Knuth analyzed linear probing in 1963), the trade-off between these aspects of performance is still not completely understood. In this paper we settle two fundamental open problems: \begin{itemize} \item We construct the first dynamic dictionary that enjoys the best of both worlds: it stores $\boldsymbol{n}$ elements using $\boldsymbol{(1 + \epsilon) n}$ memory words, and guarantees constant-time operations in the worst case with high probability. Specifically, for any \boldsymbol{\epsilon = \Omega ( (\log \log n / \log n)^{1/2} )}$ and for any sequence of polynomially many operations, with high probability over the randomness of the initialization phase, all operations are performed in constant time which is independent of $\boldsymbol{\epsilon}$. The construction is a two-level variant of cuckoo hashing, augmented with a ``backyard'' that handles a large fraction of the elements, together with a de-amortized perfect hashing scheme for eliminating the dependency on $\boldsymbol{\epsilon}$. \item We present a variant of the above construction that uses only $\boldsymbol{(1 + o(1))\B}$ bits, where $\boldsymbol{\B}$ is the information-theoretic lower bound for representing a set of size $\boldsymbol{n}$ taken from a universe of size $\boldsymbol{u}$, and guarantees constant-time operations in the worst case with high probability, as before. This problem was open even in the {\em amortized} setting. One of the main ingredients of our construction is a permutation-based variant of cuckoo hashing, which significantly improves the space consumption of cuckoo hashing when dealing with a rather small universe. \end{itemize}
Starting Page	787
Ending Page	796
File Size	390432
Page Count	10
File Format	PDF
ISBN	9781424485253
ISSN	02725428
DOI	10.1109/FOCS.2010.80
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2010-10-23
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Dictionaries Polynomials Data structures Random access memory Redundancy Timing Memory management
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Backyard cuckoo hashing: constant worst-case operations with a succinct representation (2010).

Backyard Cuckoo Hashing: Constant Worst-Case Operations with a Succinct Representation

Backyard cuckoo hashing: Constant worstcase operations with a succinct representation

Backyard cuckoo hashing: Constant worst-case operations with a succinct representation (2010)

Backyard Cuckoo hashing: Constant worst-case operations with a succinct representation (2010)

Backyard Cuckoo hashing: Constant worst-case operations with a succinct representation (2010)

Space efficient hash tables with worst case constant access time (2003)

Space Efficient Hash Tables With Worst Case Constant Access Time (2003)

A lower bound for the dictionary problem under a hashing model

Backyard Cuckoo Hashing: Constant Worst-Case Operations with a Succinct Representation

Similar Documents

Backyard cuckoo hashing: constant worst-case operations with a succinct representation (2010).

Backyard Cuckoo Hashing: Constant Worst-Case Operations with a Succinct Representation

Backyard cuckoo hashing: Constant worstcase operations with a succinct representation

Backyard cuckoo hashing: Constant worst-case operations with a succinct representation (2010)

Backyard Cuckoo hashing: Constant worst-case operations with a succinct representation (2010)

Backyard Cuckoo hashing: Constant worst-case operations with a succinct representation (2010)

Space efficient hash tables with worst case constant access time (2003)

Space Efficient Hash Tables With Worst Case Constant Access Time (2003)

A lower bound for the dictionary problem under a hashing model

Backyard Cuckoo Hashing: Constant Worst-Case Operations with a Succinct Representation