On the k-independence required by linear probing and minwise independence

TY - JOUR

T1 - On the k-independence required by linear probing and minwise independence

AU - Pǎtraşcu, Mihai

AU - Thorup, Mikkel

PY - 2016

Y1 - 2016

N2 - 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 Ω(lg1 ε)-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.

AB - 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 Ω(lg1 ε)-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.

KW - k-Independent hashing

KW - Linear probing

KW - Minwise independence

U2 - 10.1145/2716317

DO - 10.1145/2716317

M3 - Journal article

AN - SCOPUS:84947920506

SN - 1549-6325

VL - 12

JO - ACM Transactions on Algorithms

JF - ACM Transactions on Algorithms

IS - 1

M1 - 8

ER -