Monotone Minimal Perfect Hashing:
Searching a Sorted Table with O(1) Accesses
Djamal Belazzougui
∗
Paolo Boldi
†
Rasmus Pagh
‡
Sebastiano Vigna
†
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 us-
ing 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 ranking just 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 2
w
ele-
ments, O(n log log w) bits are sufficient to hash monotoni-
cally with evaluation 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 con-
sequence, 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 a trie in a very compact way, but admits er-
rors. 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 of
O(nw) bits. This implies an efficient index for searching a
blocked memory.
1 Introduction
This paper addresses a series of problems that lie at the con-
fluence of two streams of research: the study of minimal per-
fect hash functions, and the analysis of indexing structures.
A minimal perfect hash functions maps bijectively a set S
of n keys into the set { 0, 1, . . . , n − 1 }. The construction of
such functions has been widely studied in the last years, lead-
ing to fundamental theoretical results such as [12, 13, 15].
From an application-oriented viewpoint, order-
preserving minimal perfect hash functions have been used to
∗
Institut National d’Informatique, Oued Smar, Algiers, Algeria
†
Università degli Studi di Milano, Italy
‡
IT University of Copenhagen, Denmark
retrieve the position of a key in a given list of keys [11, 20].
We start from the observation that all existing techniques
for this task assume that keys can be provided in any order,
incurring an unavoidable (n log n) lower bound on the
number of bits required to store the function. However,
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 call the problem of mapping each key of a
lexicographically sorted set to its ordinal position monotone
minimal perfect hashing. This problem has received, to
the best of our knowledge, no attention in the literature.
However, as we will shortly explain, it is tightly connected
with other classical problems. It is, in a way, a very weak
form of ranking: for instance, partial ranking on a set S is
given by a function that returns the lexicographical position
of an element x of S, but returns −1 if x is not in S. Instead,
a monotone minimal perfect hash function is allowed to
return any result on elements not in S.
In a classical paper, Yao [27] showed that if one uses
no extra space in addition to a table of n > 2 keys from
an ordered universe u, and if u is sufficiently large, any
organization of the table requires log(n + 1) worst case
search time. In particular, sorting the table yields the best
possible search time. The lower bound holds even if we
are interested only in membership queries (“is x in the table
or not?”), and it extends to more general data structures
allowing pointers and repeated keys in n
O(1)
space. A
number of researchers have investigated the amount of extra
space needed to break Yao’s lower bound, using hashing
techniques to provide membership queries with O(1) table
accesses [9, 10, 25]. However, these schemes do not support
range queries (“Which are the keys in the range [` . . r]?”)
beyond the trivial reduction to membership queries that
requires linear time in the size of the range.
Here we consider the scenario where the table is sorted,
and ask the question: What is the space usage of index
structures that make it possible to search the table using O(1)
accesses in expectation? We consider two kinds of search for
a key x :
1. Membership searches where we must find the position
of x in the table, or report that x is not in the table, and
2. Predecessor searches where we must return the position
剩余9页未读，继续阅读
资源评论
weixin_38657848
- 粉丝: 5
- 资源: 906
