2008/11/16 by Djamal Belazzougui, Paolo Boldi, Rasmus Pagh +1 · 1 citation
Computer Science · Biochemistry, Genetics and Molecular Biology · Mathematics · #Algorithms and Data Compression #Data Management and Algorithms #DNA and Biological Computing #Dynamic perfect hashing #Hash function #Perfect hash function #Lexicographical order #Monotone polygon #Computer science #Universal hashing #Hash table #K-independent hashing #Theoretical computer science #Data structure #Function (biology) #Discrete mathematics #Upper and lower bounds #Mathematics #Combinatorics #Algorithm #Double hashing #Programming language
paper · doi:10.1145/1963190.2025378
openalex publication_date 2008/11/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/11
Minimal perfect hash functions have been shown to be useful to compress data in several data management tasks. In particular, order-preserving minimal perfect hash functions (Fox et al. 1991) have been used to retrieve the position of a key in a given list of keys; however, the ability to preserve any given order leads to an unavoidable Ω( n log n ) lower bound on the number of bits required to store the function. Recently, it was observed (Belazzougui et al. 2009) that very frequently the keys to be hashed are sorted in their intrinsic (i.e., lexicographical) order. This is typically the case of dictionaries of search engines, list of URLs of Web graphs, and so on. We refer to this restricted version of the problem as monotone minimal perfect hashing . We analyze experimentally the data structures proposed in Belazzougui et al. [2009], and along our way we propose some new methods that, albeit asymptotically equivalent or worse, perform very well in practice and provide a balance between access speed, ease of construction, and space usage.