Dense peelable random uniform hypergraphs

DOI10.4230/LIPICS.ESA.2019.38MaRDI QIDQ5075777zbMATH OpenFDO

Authors Martin Dietzfelbinger, Stefan Walzer

Publication date 11 May 2022

Full work available at URL https://arxiv.org/abs/1907.04749

zbMATH Keywords

2-corehashingpeeling thresholdrandom hypergraphsretrievalsuccinct data structure

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Recommendations

• Mixed hypergraphs for linear-time construction of denser hashing-based data structures
• The multiple-orientability thresholds for random hypergraphs
• The Multiple-Orientability Thresholds for Random Hypergraphs
• Orientability of random hypergraphs and the power of multiple choices
• A new approach to the orientation of random hypergraphs

Cites work

• 3.5-Way Cuckoo Hashing for the Price of 2-and-a-Bit
• A new approach to the orientation of random hypergraphs
• A simple solution to the k‐core problem
• An Optimal Bloom Filter Replacement Based on Matrix Solving
• Balanced allocation and dictionaries with tightly packed constant size bins
• Bloomier Filters: A Second Look
• Constant-time retrieval with O( m) extra bits
• Cores in random hypergraphs and Boolean formulas
• Cuckoo hashing
• Efficient erasure correcting codes
• Fast scalable construction of ([compressed] static | minimal perfect hash) functions
• scientific article; zbMATH DE number 2042286 (Why is no real title available?)
• Load thresholds for cuckoo hashing with double hashing
• Load Thresholds for Cuckoo Hashing with Overlapping Blocks
• Maximum matchings in random bipartite graphs and the space utilization of cuckoo hash tables
• Mixed hypergraphs for linear-time construction of denser hashing-based data structures
• Probability and computing. Randomization and probabilistic techniques in algorithms and data analysis
• Sharp load thresholds for cuckoo hashing
• Simple and Space-Efficient Minimal Perfect Hash Functions
• Size and connectivity of the \(k\)-core of a random graph
• Some Open Questions Related to Cuckoo Hashing
• Space-Efficient Straggler Identification in Round-Trip Data Streams Via Newton’s Identities and Invertible Bloom Filters
• Succinct Data Structures for Retrieval and Approximate Membership (Extended Abstract)
• The \(k\)-orientability thresholds for \(G_{n,p}\)
• The 3-XORSAT threshold.
• The Multiple-Orientability Thresholds for Random Hypergraphs
• The random graph threshold for k-orientiability and a fast algorithm for optimal multiple-choice allocation
• The satisfiability threshold for k-XORSAT
• Tight thresholds for Cuckoo hashing via XORSAT (extended abstract)

Cited in

(6)

• scientific article; zbMATH DE number 7525476 (Why is no real title available?)
• Binary fuse filters: fast and smaller than xor filters
• Algorithms and Data Structures for Hyperedge Queries
• Count-min sketch with variable number of hash functions: an experimental study
• Peeling close to the orientability threshold. Spatial coupling in hashing-based data structures
• Ribbon: fast succinct static retrieval and approximate membership

Describes a project that uses

Uses Software

• BUbiNG
• GitHub

This page was built for publication: Dense peelable random uniform hypergraphs

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