| Almost random graphs with simple hash functions (2003) | |||||||||||||||||||
Abstract | |||||||||||||||||||
| We describe a simple randomized construction for generating pairs of hash functions h1, h2 from a universe U to ranges V = [m] = {0, 1,..., m − 1} and W = [m] so that for every key set S ⊆ U with n = |S | ≤ m/(1 + ɛ) the (random) bipartite (multi)graph with node set V ⊎ W and edge set {(h1(x), h2(x)) | x ∈ S} exhibits a structure that is essentially random. The construction combines d-wise independent classes for d a relatively small constant with the wellknown technique of random offsets. While keeping the space needed to store the description of h1 and h2 at O(n ζ), for ζ < 1 fixed arbitrarily, we obtain a much smaller (constant) evaluation time than previous constructions of this kind, which involved Siegel’s high-performance hash classes. The main new technique is the combined analysis of the graph structure and the inner structure of the hash functions, as well as a new way of looking at the cycle structure of random (multi)graphs. The construction may be applied to improve on Pagh and Rodler’s “cuckoo hashing ” (2001), to obtain a simpler and faster alternative to a recent construction of Östlin and Pagh (2002/03) for simulating uniform hashing on a key set S, and to the simulation of shared memory on distributed memory machines. We also describe a novel way of implementing (approximate) d-wise independent hashing without using polynomials. | |||||||||||||||||||
Details der Publikation | |||||||||||||||||||
| |||||||||||||||||||