research-article

Nearly optimal static Las Vegas succinct dictionary

Author:

Huacheng YuAuthors Info & Claims

STOC 2020: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing

Pages 1389 - 1401

https://doi.org/10.1145/3357713.3384274

Published: 22 June 2020 Publication History

Abstract

Given a set S of n (distinct) keys from key space [U], each associated with a value from Σ, the static dictionary problem asks to preprocess these (key, value) pairs into a data structure, supporting value-retrieval queries: for any given x∈ [U], valRet(x) must return the value associated with x if x∈ S, or return ⊥ if x∉ S. The special case where |Σ|=1 is called the membership problem. The “textbook” solution is to use a hash table, which occupies linear space and answers each query in constant time. On the other hand, the minimum possible space to encode all (key, value) pairs is only OPT:= ⌈lg₂(

U n

)+nlg₂|Σ|⌉ bits, which could be much less.

In this paper, we design a randomized dictionary data structure using

OPT+lgn+O(lglglglglgU)

bits of space, and it has expected constant query time, assuming the query algorithm can access an external lookup table of size n ^0.001. The lookup table depends only on U, n and |Σ|, and not the input. Previously, even for membership queries and U≤ n ^O(1), the best known data structure with constant query time requires OPT+n/lgn bits of space by Pagh (SIAM J. Comput. 2001) and Pǎtraşcu (FOCS 2008); the best known using OPT+n ^0.999 space has query time O(lgn); the only known non-trivial data structure with OPT+n ^0.001 space has O(lgn) query time and requires a lookup table of size ≥ n ^2.99 (!). Our new data structure answers open questions by Pǎtraşcu and Thorup.

References

[1]

Karl Bringmann and Kasper Green Larsen. 2013. Succinct sampling from discrete distributions. In Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013. 775-782.

Digital Library

[2]

Andrej Brodnik and J. Ian Munro. 1999. Membership in Constant Time and Almost-Minimum Space. SIAM J. Comput. 28, 5 ( 1999 ), 1627-1640.

Digital Library

[3]

Harry Buhrman, Peter Bro Miltersen, Jaikumar Radhakrishnan, and Srinivasan Venkatesh. 2002. Are Bitvectors Optimal? SIAM J. Comput. 31, 6 ( 2002 ), 1723-1744.

Digital Library

[4]

Larry Carter and Mark N. Wegman. 1979. Universal Classes of Hash Functions. J. Comput. Syst. Sci. 18, 2 ( 1979 ), 143-154.

[5]

Yevgeniy Dodis, Mihai Paˇtraşcu, and Mikkel Thorup. 2010. Changing Base without Losing Space. In Proc. 42nd ACM Symposium on Theory of Computing (STOC). 593-602.

Digital Library

[6]

Amos Fiat and Moni Naor. 1993. Implicit O(1) Probe Search. SIAM J. Comput. 22, 1 ( 1993 ), 1-10.

Digital Library

[7]

Amos Fiat, Moni Naor, Jeanette P. Schmidt, and Alan Siegel. 1992. Nonoblivious Hashing. J. ACM 39, 4 ( 1992 ), 764-782.

Digital Library

[8]

Faith E. Fich and Peter Bro Miltersen. 1995. Tables Should Be Sorted (On Random Access Machines). In Algorithms and Data Structures, 4th International Workshop, WADS '95, Kingston, Ontario, Canada, August 16-18, 1995, Proceedings. 482-493.

[9]

Michael L. Fredman, János Komlós, and Endre Szemerédi. 1984. Storing a Sparse Table with O(1) Worst Case Access Time. J. ACM 31, 3 ( 1984 ), 538-544.

Digital Library

[10]

Roberto Grossi, Alessio Orlandi, Rajeev Raman, and S. Srinivasa Rao. 2009. More Haste, Less Waste: Lowering the Redundancy in Fully Indexable Dictionaries. In 26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009, February 26-28, 2009, Freiburg, Germany, Proceedings. 517-528.

[11]

Guy Jacobson. 1989. Space-eficient Static Trees and Graphs. In 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October-1 November 1989. 549-554.

[12]

Peter Bro Miltersen. 1996. Lower Bounds for Static Dictionaries on RAMs with Bit Operations But No Multiplication. In Automata, Languages and Programming, 23rd International Colloquium, ICALP96, Paderborn, Germany, 8-12 July 1996, Proceedings. 442-453.

[13]

Peter Bro Miltersen, Noam Nisan, Shmuel Safra, and Avi Wigderson. 1998. On Data Structures and Asymmetric Communication Complexity. J. Comput. Syst. Sci. 57, 1 ( 1998 ), 37-49.

Digital Library

[14]

Mark H. Overmars. 1983. The Design of Dynamic Data Structures. Springer-Verlag.

[15]

Rasmus Pagh. 2001. Low Redundancy in Static Dictionaries with Constant Query Time. SIAM J. Comput. 31, 2 ( 2001 ), 353-363.

Digital Library

[16]

Rasmus Pagh. 2001. On the cell probe complexity of membership and perfect hashing. In Proceedings on 33rd Annual ACM Symposium on Theory of Computing, July 6-8, 2001, Heraklion, Crete, Greece. 425-432.

Digital Library

[17]

Mihai Paˇtraşcu. 2008. Succincter. In Proc. 49th IEEE Symposium on Foundations of Computer Science (FOCS). 305-313.

[18]

Mihai Paˇtraşcu and Mikkel Thorup. 2006. Time-space trade-ofs for predecessor search. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing, Seattle, WA, USA, May 21-23, 2006. 232-240.

[19]

Mihai Paˇtraşcu and Mikkel Thorup. 2007. Randomization does not help searching predecessors. In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, New Orleans, Louisiana, USA, January 7-9, 2007. 555-564.

[20]

Mihai Paˇtraşcu and Emanuele Viola. 2010. Cell-Probe Lower Bounds for Succinct Partial Sums. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010. 117-122.

[21]

Rajeev Raman, Venkatesh Raman, and Srinivasa Rao Satti. 2007. Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets. ACM Trans. Algorithms 3, 4 ( 2007 ), 43.

Digital Library

[22]

Jeanette P. Schmidt and Alan Siegel. 1990. The Spatial Complexity of Oblivious k-Probe Hash Functions. SIAM J. Comput. 19, 5 ( 1990 ), 775-786.

Digital Library

[23]

Robert Endre Tarjan and Andrew Chi-Chih Yao. 1979. Storing a Sparse Table. Commun. ACM 22, 11 ( 1979 ), 606-611.

[24]

Emanuele Viola. 2012. Bit-Probe Lower Bounds for Succinct Data Structures. SIAM J. Comput. 41, 6 ( 2012 ), 1593-1604.

[25]

Emanuele Viola, Omri Weinstein, and Huacheng Yu. 2019. How to Store a Random Walk. CoRR abs/ 1907.10874 ( 2019 ). http://arxiv.org/abs/ 1907.10874

[26]

Andrew Chi-Chih Yao. 1981. Should Tables Be Sorted? J. ACM 28, 3 ( 1981 ), 615-628.

[27]

Huacheng Yu. 2019. Optimal succinct rank data structure via approximate nonnegative tensor decomposition. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019. 955-966.

Digital Library

Cited By

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
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
Bercea IEven GLeonardi SGupta A(2022)An extendable data structure for incremental stable perfect hashingProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3519935.3520070(1298-1310)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519935.3520070
Show More Cited By

Index Terms

Nearly optimal static Las Vegas succinct dictionary
1. Mathematics of computing
  1. Information theory
2. Theory of computation
  1. Design and analysis of algorithms
    1. Algorithm design techniques
      1. Divide and conquer
    2. Data structures design and analysis

Recommendations

Nearly Optimal Static Las Vegas Succinct Dictionary

For positive integers $U$, $n$, and $\sigma$, given a set $S$ of $n$ (distinct) keys from key space $[U]$, each associated with a value from $[\sigma]$, the static dictionary problem asks one to preprocess these (key, value) pairs into a data structure, ...
Bit-probe lower bounds for succinct data structures
STOC '09: Proceedings of the forty-first annual ACM symposium on Theory of computing

We prove lower bounds on the redundancy necessary to represent a set S of objects using a number of bits close to the information-theoretic minimum log₂ |S|, while answering various queries by probing few bits. Our main results are: To represent n ...
(Nearly) sample-optimal sparse Fourier transform
SODA '14: Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms

We consider the problem of computing a k-sparse approximation to the discrete Fourier transform of an n-dimensional signal. Our main result is a randomized algorithm that computes such an approximation using O(k log n(log log n)^O(1)) signal samples in ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC 2020: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing

June 2020

1429 pages

ISBN:9781450369794

DOI:10.1145/3357713

General Chairs:
Konstantin Makarychev
Northwestern University, USA
,
Yury Makarychev
Toyota Technological Institute at Chicago, USA
,
Madhur Tulsiani
Toyota Technological Institute at Chicago, USA
,
Gautam Kamath
University of Waterloo, Canada
,
Program Chair:
Julia Chuzhoy
Toyota Technological Institute at Chicago, USA

Copyright © 2020 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 ACM 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: 22 June 2020

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

STOC '20

Sponsor:

SIGACT

STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing

June 22 - 26, 2020

IL, Chicago, USA

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
142
Total Downloads

Downloads (Last 12 months)11
Downloads (Last 6 weeks)2

Reflects downloads up to 10 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

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
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
Bercea IEven GLeonardi SGupta A(2022)An extendable data structure for incremental stable perfect hashingProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3519935.3520070(1298-1310)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519935.3520070
Bender MFarach-Colton MKuszmaul JKuszmaul WLiu MLeonardi SGupta A(2022)On the optimal time/space tradeoff for hash tablesProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3519935.3519969(1284-1297)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519935.3519969

View Options

Get Access

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