# MPI-I-2003-1-005

## 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.

Acknowledgement:** **

References to related material:

To download this research report, please select the type of document that fits best your needs. | Attachement Size(s): |

| 369 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: **http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/2003-1-005

**BibTeX**
`@TECHREPORT{``DietzfelbingerWoelfel2003``,`

` 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},`

`}`