More Web Proxy on the site http://driver.im/

research-article

On the optimal time/space tradeoff for hash tables

Authors:

Michael A. Bender,

Martín Farach-Colton,

William Kuszmaul,

Mingmou LiuAuthors Info & Claims

STOC 2022: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing

Pages 1284 - 1297

https://doi.org/10.1145/3519935.3519969

Published: 10 June 2022 Publication History

Abstract

For nearly six decades, the central open question in the study of hash tables has been to determine the optimal achievable tradeoff curve between time and space. State-of-the-art hash tables offer the following guarantee: If keys/values are Θ(logn) bits each, then it is possible to achieve constant-time insertions/deletions/queries while wasting only O(loglogn) bits of space per key when compared to the information-theoretic optimum—this bound has been proven to be optimal for a number of closely related problems (e.g., stable hashing, dynamic retrieval, and dynamically-resized filters).

This paper shows that O(loglogn) wasted bits per key is not the end of the line for hashing. In fact, for any k ∈ [log^* n], it is possible to achieve O(k)-time insertions/deletions, O(1)-time queries, and the k-th iterated logarithm O(log^(k) n) wasted bits per key (all with high probability in n), while also supporting dynamic resizing as the size of the table changes. We further show that this tradeoff curve is the best achievable by any of a large class of hash tables, including any hash table designed using the current framework for making constant-time hash tables succinct.

Our result holds for arbitrarily large keys/values, and in the case where keys/values are very small, we can tighten our bounds to o(1) wasted bits per key. Building on this, we obtain a constant-time dynamic filter that uses n ⌈logє⁻¹ ⌉+ n loge + o(n) bits of space for a wide choice of false-positive rates є, resolving a long-standing open problem for the design of dynamic filters.

References

[1]

Yuriy Arbitman, Moni Naor, and Gil Segev. 2009. De-amortized Cuckoo Hashing: Provable Worst-Case Performance and Experimental Results. In Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP). 107–118.

Digital Library

[2]

Yuriy Arbitman, Moni Naor, and Gil Segev. 2010. Backyard cuckoo hashing: Constant worst-case operations with a succinct representation. In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science (FOCS). 787–796.

Digital Library

[3]

Michael A Bender, Alex Conway, Martín Farach-Colton, William Kuszmaul, and Guido Tagliavini. 2021. All-Purpose Hashing. arXiv preprint arXiv:2109.04548.

[4]

Michael A Bender, Martin Farach-Colton, Mayank Goswami, Rob Johnson, Samuel McCauley, and Shikha Singh. 2018. Bloom filters, adaptivity, and the dictionary problem. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS). 182–193.

[5]

Michael A Bender, Martin Farach-Colton, Rob Johnson, Rus C Kraner, Dzejla Medjedovic, Pablo Montes, Pradeep Shetty, Richard P Spillane, and Erez Zadok. 2012. Don’t thrash: how to cache your hash on flash. Proceedings of the VLDB Endowment, 5, 11 (2012), 1627–1637.

Digital Library

[6]

Michael A Bender, Martín Farach-Colton, John Kuszmaul, and William Kuszmaul. 2021. On the Optimal Time/Space Tradeoff for Hash Tables. arXiv preprint arXiv:2111.00602.

[7]

Ioana O Bercea and Guy Even. 2020. A Dynamic Space-Efficient Filter with Constant Time Operations. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020).

[8]

Burton H Bloom. 1970. Space/time trade-offs in hash coding with allowable errors. Commun. ACM, 13, 7 (1970), 422–426.

Digital Library

[9]

Larry Carter, Robert Floyd, John Gill, George Markowsky, and Mark Wegman. 1978. Exact and approximate membership testers. In Proceedings of the tenth annual ACM Symposium on Theory of Computing (STOC). 59–65.

Digital Library

[10]

Erik D Demaine, Friedhelm Meyer auf der Heide, Rasmus Pagh, and Mihai Pǎtraşcu. 2006. De dictionariis dynamicis pauco spatio utentibus. In Latin American Symposium on Theoretical Informatics. 349–361.

[11]

Martin Dietzfelbinger and Friedhelm Meyer auf der Heide. 1990. A New Universal Class of Hash Functions and Dynamic Hashing in Real Time. In Proceedings of the 17th International Colloquium on Automata, Languages and Programming (ICALP). 6–19.

[12]

M Dietzfelbinger, A Karlin, K Mehlhorn, FM auf der Heide, H Rohnert, and RE Tarjan. 1988. Dynamic perfect hashing: upper and lower bounds. In [Proceedings 1988] 29th Annual Symposium on Foundations of Computer Science (FOCS). 524–531.

[13]

Martin Dietzfelbinger and Rasmus Pagh. 2008. Succinct Data Structures for Retrieval and Approximate Membership. In Proceedings of the 35th international colloquium on Automata, Languages and Programming (ICALP). 385–396.

[14]

Martin Dietzfelbinger and Christoph Weidling. 2005. Balanced allocation and dictionaries with tightly packed constant size bins. In Proceedings of the 32nd international conference on Automata, Languages and Programming (ICALP). 166–178.

Digital Library

[15]

Martin Dietzfelbinger and Philipp Woelfel. 2003. Almost random graphs with simple hash functions. In Proceedings of the thirty-fifth annual ACM Symposium on Theory of Computing (STOC). 629–638.

Digital Library

[16]

Peter C Dillinger and Stefan Walzer. 2021. Ribbon filter: practically smaller than Bloom and Xor. arXiv preprint arXiv:2103.02515.

[17]

Bin Fan, Dave G Andersen, Michael Kaminsky, and Michael D Mitzenmacher. 2014. Cuckoo filter: Practically better than bloom. In Proceedings of the 10th ACM International on Conference on emerging Networking Experiments and Technologies. 75–88.

Digital Library

[18]

Dimitris Fotakis, Rasmus Pagh, Peter Sanders, and Paul G Spirakis. 2003. Space Efficient Hash Tables with Worst Case Constant Access Time. In Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science (STOC). 271–282.

Digital Library

[19]

Michael L. Fredman, Janos Komlos, and Endre Szemeredi. 1982. Storing a Sparse Table with O(1) Worst Case Access Time. In Proceedings of the 23rd Annual Symposium on Foundations of Computer Science (FOCS) (SFCS ’82). IEEE Computer Society, 165–169.

Digital Library

[20]

Don Knuth. 1963. Notes on öpen" addressing.

[21]

Donald E. Knuth. 1973. The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley. isbn:0-201-03803-X

[22]

Mingmou Liu, Yitong Yin, and Huacheng Yu. 2020. Succinct Filters for Sets of Unknown Sizes. In 47th International Colloquium on Automata, Languages, and Programming (ICALP).

[23]

Shachar Lovett and Ely Porat. 2010. A lower bound for dynamic approximate membership data structures. In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science (FOCS). 797–804.

Digital Library

[24]

Michael Mitzenmacher. 2001. The power of two choices in randomized load balancing. IEEE Transactions on Parallel and Distributed Systems, 12, 10 (2001), 1094–1104.

Digital Library

[25]

Christian Worm Mortensen, Rasmus Pagh, and Mihai Pǎtraçcu. 2005. On dynamic range reporting in one dimension. In Proceedings of the thirty-seventh annual ACM Symposium on Theory of Computing (STOC). 104–111.

Digital Library

[26]

Anna Ostlin and Rasmus Pagh. 2003. Uniform hashing in constant time and linear space. In Proceedings of the thirty-fifth annual ACM Symposium on Theory of Computing (STOC). 622–628.

Digital Library

[27]

Anna Pagh, Rasmus Pagh, and S Srinivasa Rao. 2005. An optimal Bloom filter replacement. In Proceedings of the sixteenth annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 823–829.

Digital Library

[28]

Rasmus Pagh. 2001. Low redundancy in static dictionaries with constant query time. SIAM J. Comput., 31, 2 (2001), 353–363.

Digital Library

[29]

Rasmus Pagh and Flemming Friche Rodler. 2004. Cuckoo Hashing. Journal of Algorithms, 51, 2 (2004), May, 122–144. issn:0196-6774 https://doi.org/10.1016/j.jalgor.2003.12.002

Digital Library

[30]

Rasmus Pagh, Gil Segev, and Udi Wieder. 2013. How to approximate a set without knowing its size in advance. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS). 80–89.

Digital Library

[31]

Mihai Patrascu. 2008. Succincter. In Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS). 305–313.

[32]

Rajeev Raman and Satti Srinivasa Rao. 2003. Succinct dynamic dictionaries and trees. In Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP). 357–368.

[33]

A Siegel. 1989. On universal classes of fast high performance hash functions, their time-space tradeoff, and their applications. In Proceedings of the 30th Annual Symposium on Foundations of Computer Science (FOCS). 20–25.

Digital Library

[34]

Huacheng Yu. 2020. Nearly optimal static Las Vegas succinct dictionary. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC). 1389–1401.

Digital Library

Cited By

Shahbazi NSintos SAsudeh A(2024)FairHash: A Fair and Memory/Time-efficient HashmapProceedings of the ACM on Management of Data10.1145/36549392:3(1-29)Online publication date: 30-May-2024
https://dl.acm.org/doi/10.1145/3654939
Bender MConway AFarach-Colton MKomlós HKoucký MKuszmaul WSaks M(2024)Nearly Optimal List Labeling2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS61266.2024.00132(2253-2274)Online publication date: 27-Oct-2024
https://doi.org/10.1109/FOCS61266.2024.00132
Bender MKuszmaul WZhou R(2024)Tight Bounds for Classical Open Addressing2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS61266.2024.00047(636-657)Online publication date: 27-Oct-2024
https://doi.org/10.1109/FOCS61266.2024.00047
Show More Cited By

Index Terms

On the optimal time/space tradeoff for hash tables
1. Theory of computation
  1. Design and analysis of algorithms
    1. Data structures design and analysis

Recommendations

Super-linear time-space tradeoff lower bounds for randomized computation
FOCS '00: Proceedings of the 41st Annual Symposium on Foundations of Computer Science

We prove the first time-space lower bound tradeoffs for randomized computation of decision problems. The bounds hold even in the case that the computation is allowed to have arbitrary probability of error on a small fraction of inputs. Our techniques ...
Near-optimal time-space tradeoff for element distinctness
SFCS '88: Proceedings of the 29th Annual Symposium on Foundations of Computer Science

It was conjectured by A. Borodin et al. that to solve the element distinctness problem requires TS= Omega (n/sup 2/) on a comparison-based branching program using space S and time T, which, if true, would be close to optimal since TS=O(n/sup 2/ log n) ...
Near-Optimal Time-Space Tradeoff for Element Distinctness

It was conjectured in Borodin et al. [J. Comput. System Sci., 22 (1981), pp. 351--364] that to solve the element distinctness problem requires $TS = \Omega(n^2)$ on a comparison-based branching program using space $S$ and time $T$, which, if true, would ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC 2022: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing

June 2022

1698 pages

ISBN:9781450392648

DOI:10.1145/3519935

General Chair:
Stefano Leonardi
Sapienza University of Rome, Italy
,
Program Chair:
Anupam Gupta
Carnegie Mellon University, USA

Copyright © 2022 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 10 June 2022

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

STOC '22

Sponsor:

SIGACT

STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing

June 20 - 24, 2022

Rome, Italy

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
324
Total Downloads

Downloads (Last 12 months)136
Downloads (Last 6 weeks)7

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Shahbazi NSintos SAsudeh A(2024)FairHash: A Fair and Memory/Time-efficient HashmapProceedings of the ACM on Management of Data10.1145/36549392:3(1-29)Online publication date: 30-May-2024
https://dl.acm.org/doi/10.1145/3654939
Bender MConway AFarach-Colton MKomlós HKoucký MKuszmaul WSaks M(2024)Nearly Optimal List Labeling2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS61266.2024.00132(2253-2274)Online publication date: 27-Oct-2024
https://doi.org/10.1109/FOCS61266.2024.00132
Bender MKuszmaul WZhou R(2024)Tight Bounds for Classical Open Addressing2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS61266.2024.00047(636-657)Online publication date: 27-Oct-2024
https://doi.org/10.1109/FOCS61266.2024.00047
Even GMarques Domingues G(2024)A Micro-architecture that supports the Fano–Elias encoding and a hardware accelerator for approximate membership queriesMicroprocessors & Microsystems10.1016/j.micpro.2023.104992105:COnline publication date: 25-Jun-2024
https://dl.acm.org/doi/10.1016/j.micpro.2023.104992
Tripathi RSingh PSingh S(2024)Revisiting Cuckoo Hashing: re-addressing the challenges of Cuckoo HashingInternational Journal of Information Technology10.1007/s41870-024-02274-2Online publication date: 20-Nov-2024
https://doi.org/10.1007/s41870-024-02274-2
Halkarnikar PMeshram PJoshi SMahajan DPawar V(2024)Binary Probing: A Novel Approach for Efficient Hash Table OperationsProceedings of International Conference on Computational Intelligence10.1007/978-981-97-3526-6_13(153-165)Online publication date: 18-Jul-2024
https://doi.org/10.1007/978-981-97-3526-6_13
Li TLiang JYu HZhou R(2023)Tight Cell-Probe Lower Bounds for Dynamic Succinct Dictionaries2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00112(1842-1862)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00112
Kuszmaul W(2023)Strongly History-Independent Storage Allocation: New Upper and Lower Bounds2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00111(1822-1841)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00111
Li TLiang JYu HZhou R(2023)Dynamic “Succincter”2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00104(1715-1733)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00104
Kuszmaul W(2022)A Hash Table Without Hash Functions, and How to Get the Most Out of Your Random Bits2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS54457.2022.00097(991-1001)Online publication date: Oct-2022
https://doi.org/10.1109/FOCS54457.2022.00097
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents