On the k -Independence Required by Linear Probing and Minwise Independence
Mihai Pǎtraşcu, Mikkel Thorup · ACM Transactions on Algorithms · 2015
We show that linear probing requires 5-independent hash functions for expected constant-time performance, matching an upper bound of Pagh et al. [2009]. More precisely, we construct a random 4-independent hash function yielding expected logarithmic search time for certain keys. For (1 + ϵ)-approximate minwise independence, we show that Ω(lg 1/ϵ)-independent hash functions are required, matching an upper bound of Indyk [2001]. We also show that the very fast 2-independent multiply-shift scheme of Dietzfelbinger [1996] fails badly in both applications.