Almost Random Graphs with Simple Hash Functions

Abstract. We describe a simple randomized construction for generating pairs of hash functions which induce sparse bipartite graphs exhibiting a structure that is essentially random. The construction combines d-wise independent classes for d a relatively small constant with the well-known technique of random offsets. While keeping the space needed at O(n^z), for z<1 fixed arbitrarily, we obtain a much smaller 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 with the inner structure of the hash functions, as well as a new way of looking at the cycle structure of random 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 (2003) 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.

Notes

• Appeared in Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC) , ACM Press, pp. 629-638, 2003

• paper as pdf, postscript (© ACM Press)

• BibTeX entry