Nearly Optimal Static Las Vegas Succinct Dictionary

DOI10.1137/20M1363649OpenAlexW2987685153MaRDI QIDQ5080480

Huacheng Yu

Publication date: 31 May 2022

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/20m1363649

zbMATH Keywords

succinct data structuredictionaryperfect hashing

Mathematics Subject Classification ID

Data structures (68P05)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The design of dynamic data structures
• Universal classes of hash functions
• On data structures and asymmetric communication complexity
• Surpassing the information theoretic bound with fusion trees
• Low Redundancy in Static Dictionaries with Constant Query Time
• Changing base without losing space
• Time-space trade-offs for predecessor search
• Storing a sparse table
• Are Bitvectors Optimal?
• The Spatial Complexity of Oblivious k-Probe Hash Functions
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• Should Tables Be Sorted?
• Implicit $O(1)$ Probe Search
• Membership in Constant Time and Almost-Minimum Space
• Nonoblivious hashing
• Bit-Probe Lower Bounds for Succinct Data Structures
• Succinct indexable dictionaries with applications to encoding k -ary trees, prefix sums and multisets
• Tables should be sorted (on random access machines)
• How to Store a Random Walk
• On the cell probe complexity of membership and perfect hashing
• Optimal succinct rank data structure via approximate nonnegative tensor decomposition
• More Haste, Less Waste: Lowering the Redundancy in Fully Indexable Dictionaries
• Succinct sampling from discrete distributions