2008.09.09 | Peter Bro Miltersen

ALCOM-seminar: Rasmus Pagh, ITU

Searching aSorted Table with O(1) Accesses
OR
Bee-Trees: How to find your way with a very little Brain

Tagline:
"I am a Bear of Very Little Brain, and long words bother me." – Winnie the Pooh

Abstract:
A minimal perfect hash function maps a set S of n keys into the set {0, 1, . . . , n −1 } bijectively Classical results state that minimal perfect hashing is possible in constant time using a structure occupying space close to the lower bound of log e bits per element. Here we consider the problem of monotone minimal perfect hashing, in which the bijection is required to preserve the
lexicographical ordering of the keys. A monotone minimal perfect hash function can be seen as a very weak form of index that provides just ranking on the set S (and answers randomly outside of S ). Our goal is to minimise the description size of the hash function: we show that, for a set S of n elements out of a universe of 2w elements, O (nlog log w) bits are sufficient to hash monotonically in time O (log w). Alternatively, we can get space O (n log w) bits with O (1) query time. Both of these data structures improve a straightforward construction with O (n log w) space and O (log w) query time. As a consequence, it is possible to search a sorted table with O (1) accesses to the table (using additional O (n log log w) bits). Our results are based on a structure (of independent interest) that represents very compactly a trie, but allows for errors. As a further application of the same structure, we show how to compute the predecessor (in the sorted order of S ) of an arbitrary element, using O (1) accesses in expectation and an index of O (n log w) bits, improving the trivial result ofO (nw) bits. This implies an efficient index for searching a blocked memory.

Joint work with Djamal Belazzougui,Paolo Boldi, and Sebastiano Vigna.
To appear at SODA '09.

Host: Peter Bro Miltersen