k-Universal Hash Family hash functions h:U-[m] Linear congruential hashing: Represent UZ for sufficiently large prime p hab(x)=((ax+b)mod p)mod m .x={hbla∈Z,l{0,b∈Zn} Theorem: The linear congruential family is 2-wise independent. Degree-k polynomial in finite field with random coefficients ·Hashing between binary fields:GF(2)→GF(2) ha.b(x)=(a*x+b)>>(w-1)
k-Universal Hash Family • Linear congruential hashing: • Represent for sufficiently large prime • • • Degree- polynomial in finite field with random coefficients • Hashing between binary fields: (a*x+b)>>(w-l) U ⊆ ℤp p ha,b(x) = ((ax + b) mod p) mod m ℋ = {ha,b ∣ a ∈ ℤp∖{0}, b ∈ ℤp} k GF(2w) → GF(2l ) ha,b(x) = hash functions h : U → [m] Theorem: The linear congruential family ℋ is 2-wise independent
Flajolet-Martin Algorithm Input:a sequence...,E [N]C [2] Output:an estimation of= {x,为，x} 2-wise independent hash function h:[2]-[2] Fory E [2w],let zeros(y)=max{i 2y}denote of trailing 0's Flajolet-Martin Algorithm: let R max zeros(h(x;)); 1≤isn return 2=2R; 2scor2xcs
Flajolet-Martin Algorithm Input: a sequence Output: an estimation of x1, x2,…, xn ∈ [N] ⊆ [2w] z = {x1, x2, …, xn} • 2-wise independent hash function • For , let denote # of trailing 0’s h : [2w] → [2w] y ∈ [2w] zeros(y) = max{i : 2i | y} Flajolet-Martin Algorithm: let ; return ; R = max 1≤i≤n zeros(h(xi )) Z ̂ = 2R Pr [ Z ̂ < z C or Z ̂ > C ⋅ z ] ≤ 3 C