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

succinct data structurescompressed functionsminimal perfect hash functionsstatic functions

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

• 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?)
• Alphabet-independent compressed text indexing
• An Optimal Bloom Filter Replacement Based on Matrix Solving
• An almost optimal algorithm for unbounded searching
• 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
• 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

(9)

• A Modular Design for Hash Functions: Towards Making the Mix-Compress-Mix Approach Practical
• Fingerprinting-based minimal perfect hashing revisited
• Storing a Compressed Function with Constant Time Access
• Compactness of hashing modes and efficiency beyond Merkle tree
• Construct a perfect word hash function in time independent of the size of integers
• T5: Hashing five inputs with three compression calls
• scientific article; zbMATH DE number 7525475 (Why is no real title available?)
• scientific article; zbMATH DE number 7525476 (Why is no real title available?)
• scientific article; zbMATH DE number 7559133 (Why is no real title available?)

Describes a project that uses

Uses Software

• Sux4J
• BUbiNG
• METAFONT
• MapReduce

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)