Fast scalable construction of ([compressed] static | minimal perfect hash) functions

DOI10.1016/J.IC.2020.104517MaRDI QIDQ776836zbMATH OpenOpenAlexWikidataFDO

Authors Marco Genuzio, Giuseppe Ottaviano, Sebastiano Vigna

Publication date 13 July 2020

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ic.2020.104517

zbMATH Keywords

compressed functionsminimal perfect hash functionsstatic functionssuccinct data structures

Mathematics Subject Classification ID

Data structures (68P05) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Recommendations

• Fast and scalable minimal perfect hashing for massive key sets
• scientific article; zbMATH DE number 1688373
• Simple and Space-Efficient Minimal Perfect Hash Functions
• Experimental and Efficient Algorithms
• scientific article; zbMATH DE number 1875411

Cites work

• Alphabet-independent compressed text indexing
• An almost optimal algorithm for unbounded searching
• An Optimal Bloom Filter Replacement Based on Matrix Solving
• Closed-form Expressions for the Moments of the Binomial Probability Distribution
• Compressed static functions with applications
• Dependent Sets of Constant Weight Binary Vectors
• Exact and approximate membership testers
• Fast prefix search in little space, with applications
• Generating a canonical prefix encoding
• Hash, Displace, and Compress
• scientific article; zbMATH DE number 1688373 (Why is no real title available?)
• scientific article; zbMATH DE number 3954145 (Why is no real title available?)
• scientific article; zbMATH DE number 3956969 (Why is no real title available?)
• scientific article; zbMATH DE number 3986610 (Why is no real title available?)
• scientific article; zbMATH DE number 503245 (Why is no real title available?)
• scientific article; zbMATH DE number 7051248 (Why is no real title available?)
• scientific article; zbMATH DE number 6469129 (Why is no real title available?)
• Maximum matchings in random bipartite graphs and the space utilization of cuckoo hash tables
• Satisfiability thresholds beyond k-XORSAT
• Sharp load thresholds for cuckoo hashing
• Storing a Compressed Function with Constant Time Access
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• Succinct Data Structures for Retrieval and Approximate Membership (Extended Abstract)
• The 3-XORSAT threshold.
• The satisfiability threshold for k-XORSAT
• Theory and practice of monotone minimal perfect hashing
• Tight thresholds for Cuckoo hashing via XORSAT (extended abstract)

Cited in

(10)

• Compactness of hashing modes and efficiency beyond Merkle tree
• Construct a perfect word hash function in time independent of the size of integers
• Storing a Compressed Function with Constant Time Access
• A Modular Design for Hash Functions: Towards Making the Mix-Compress-Mix Approach Practical
• Dense peelable random uniform hypergraphs
• scientific article; zbMATH DE number 7525476 (Why is no real title available?)
• Constant-time retrieval with O( m) extra bits
• T5: Hashing five inputs with three compression calls
• Fingerprinting-based minimal perfect hashing revisited
• Ribbon: fast succinct static retrieval and approximate membership

Describes a project that uses

Uses Software

• MapReduce
• Sux4J
• METAFONT
• BUbiNG

This page was built for publication: Fast scalable construction of ([compressed] static | minimal perfect hash) functions

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