### Theory and practice of monotone minimal perfect hashingTheory and practice of monotone minimal perfect hashing

Access Restriction
Subscribed

 Author Belazzougui, Djamal ♦ Boldi, Paolo ♦ Pagh, Rasmus ♦ Vigna, Sebastiano Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2011 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data Subject Keyword Monotone minimal perfect hashing ♦ Succinct data structures ♦ Very large databases Abstract 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 $Ω(\textit{n}$ log $\textit{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. ISSN 10846654 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2008-11-01 Publisher Place New York e-ISSN 10846654 Journal Journal of Experimental Algorithmics (JEA) Volume Number 16 Page Count 26 Starting Page 3.1 Ending Page 3.26

#### Open content in new tab

Source: ACM Digital Library