Pseudo-random Hash Functions and the Bloomier Filter

The Bloomier Filter is a data stucture used to encode functions. The
encoding is very space-efficient, and achieves this efficiency by
allowing a small amount of error.  More specifically, a value in the
function's domain is always mapped correctly, but there is a small
probability that a value outside the domain will not be identified as
such.  The analysis of this probability (as presented in the paper
"Saving David Nelson with Bloomier Filters", by Chazelle et al),
assumes that the filter is constructed using a random hash function,
and notes that using a simple pseudo-random hash function may not
produce error rates as low.  For this project, I will analyze a number
of different pseudo-random hash functions to see which ones are best
suited for contstructing Bloomier filters.  The complexity of the
functions and the error rates of the resulting filters will both be
considerations.

Thomas Ventimiglia
Advisor: Bernard Chazelle