Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society


Almost random graphs with simple hash functions

Dietzfelbinger, Martin and Woelfel, Philipp

MPI-I-2003-1-005. March 2003, 23 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
We describe a simple randomized construction for generating pairs of
hash functions h_1,h_2 from a universe U to ranges V=[m]={0,1,...,m-1}
and W=[m] so that for every key set S\subseteq U with
n=|S| <= m/(1+epsilon) the (random) bipartite (multi)graph with node
set V + W and edge set {(h_1(x),h_2(x)) | x in S} exhibits 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 to store the description of h_1 and h_2 at O(n^zeta), for
zeta<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
"Ostlin 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.
References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
MPI-I-2003-1-005.ps369 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
URL to this document:

Hide details for BibTeXBibTeX
  AUTHOR = {Dietzfelbinger, Martin and Woelfel, Philipp},
  TITLE = {Almost random graphs with simple hash functions},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Stuhlsatzenhausweg 85, 66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-2003-1-005},
  MONTH = {March},
  YEAR = {2003},
  ISSN = {0946-011X},