| Theory and practise of monotone minimal perfect hashing (2009) | |||||||||||||
Abstract | |||||||||||||
| Theory and practise of monotone minimal perfect hashing / Djamal Belazzougui, Rasmus Pagh, Paolo Boldi, Sebastiano Vigna. - In: ACM-SIAM Symposium on discrete algorithms : January 4-6, 2009, New York Marriott Downtime, NY / ; Mathieu, Claire. - Philadelphia : SIAM, 2009. - p. 132-144. ((Intervento presentato al 10th. Workshop on Algorithm Engineering and Experiments (ALENEX), New York, USA, 2009.. 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 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 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, etc. We refer to this restricted version of the problem as monotone minimal perfect hashing. We analyse experimentally the data structures proposed in our paper "Monotone Minimal Perfect Hashing: Searching a Sorted Table with O(1) Accesses", and along our way we propose some new methods that, albeit asymptotically equivalent or worse, perform very well in practise, and provide a balance between access speed, ease of construction, and space usage. | |||||||||||||
Details der Publikation | |||||||||||||
| |||||||||||||