Nearly Optimal Static Las Vegas Succinct Dictionary

DOI10.1137/20M1363649MaRDI QIDQ5080480zbMATH OpenOpenAlexFDO

Authors 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

dictionaryperfect hashingsuccinct data structure

Mathematics Subject Classification ID

Data structures (68P05)

Recommendations

• Nearly optimal static Las Vegas succinct dictionary
• A simple, fast, and compact static dictionary
• Low redundancy in static dictionaries with constant query time
• De Dictionariis Dynamicis Pauco Spatio Utentibus
• Deterministic dictionaries

Cites work

• Are Bitvectors Optimal?
• Bit-probe lower bounds for succinct data structures
• Cell-probe lower bounds for succinct partial sums
• Changing base without losing space
• How to Store a Random Walk
• scientific article; zbMATH DE number 1688373 (Why is no real title available?)
• scientific article; zbMATH DE number 6381684 (Why is no real title available?)
• scientific article; zbMATH DE number 3143969 (Why is no real title available?)
• scientific article; zbMATH DE number 6931784 (Why is no real title available?)
• scientific article; zbMATH DE number 2102768 (Why is no real title available?)
• scientific article; zbMATH DE number 7759279 (Why is no real title available?)
• Implicit O(1) Probe Search
• Low redundancy in static dictionaries with constant query time
• Membership in Constant Time and Almost-Minimum Space
• More haste, less waste: lowering the redundancy in fully indexable dictionaries
• Nonoblivious hashing
• On data structures and asymmetric communication complexity
• On the cell probe complexity of membership and perfect hashing
• Optimal succinct rank data structure via approximate nonnegative tensor decomposition
• Should Tables Be Sorted?
• Storing a sparse table
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• Succinct indexable dictionaries with applications to encoding \(k\)-ary trees, prefix sums and multisets
• Succinct sampling from discrete distributions
• Surpassing the information theoretic bound with fusion trees
• Tables should be sorted (on random access machines)
• The design of dynamic data structures
• The Spatial Complexity of Oblivious k-Probe Hash Functions
• Time-space trade-offs for predecessor search
• Universal classes of hash functions

Cited in

(1)

• Nearly optimal static Las Vegas succinct dictionary

This page was built for publication: Nearly Optimal Static Las Vegas Succinct Dictionary

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5080480)