Friday, May 13, 2011

Hash, Hash and Hash

Universal Hashing
A probability distribution H over hash functions from U to $\{1, \ldots, M\}$ is uni-
versal if for all x = y in U , we have
Pr\{h(x) == h(y)\} \leq 1/M


(c,k)-Universal Hashing
$\{h_i\} h_i : U \to R$, for any distinct elements $x_1,\ldots,x_k \in U$, and $y_1,\ldots,y_k \in R$, we have
Pr\{h_i(x_1) = y_1,\ldots, h_i(x_k) =y_k\} \leq c/|R|^k

No comments: