Approximately minwise independence with twisted tabulation

TY - GEN

T1 - Approximately minwise independence with twisted tabulation

AU - Dahlgaard, Søren

AU - Thorup, Mikkel

N1 - Conference code: 14

PY - 2014

Y1 - 2014

N2 - A random hash function h is ε-minwise if for any set S, |S| = n, and element x ∈ S, Pr[h(x) = min h (S)] = (1 ± ε)/n. Minwise hash functions with low bias ε have widespread applications within similarity estimation. Hashing from a universe [u], the twisted tabulation hashing of Pǎtraşcu and Thorup [SODA'13] makes c = O(1) lookups in tables of size u1/c. Twisted tabulation was invented to get good concentration for hashing based sampling. Here we show that twisted tabulation yields Õ(1/u1/c-minwise hashing. In the classic independence paradigm of Wegman and Carter [FOCS'79] Õ(1/u1/c-minwise hashing requires Ω(log u)-independence [Indyk SODA'99]. Pǎtraşcu and Thorup [STOC'11] had shown that simple tabulation, using same space and lookups yields Õ(1/n1/c-minwise independence, which is good for large sets, but useless for small sets. Our analysis uses some of the same methods, but is much cleaner bypassing a complicated induction argument.

AB - A random hash function h is ε-minwise if for any set S, |S| = n, and element x ∈ S, Pr[h(x) = min h (S)] = (1 ± ε)/n. Minwise hash functions with low bias ε have widespread applications within similarity estimation. Hashing from a universe [u], the twisted tabulation hashing of Pǎtraşcu and Thorup [SODA'13] makes c = O(1) lookups in tables of size u1/c. Twisted tabulation was invented to get good concentration for hashing based sampling. Here we show that twisted tabulation yields Õ(1/u1/c-minwise hashing. In the classic independence paradigm of Wegman and Carter [FOCS'79] Õ(1/u1/c-minwise hashing requires Ω(log u)-independence [Indyk SODA'99]. Pǎtraşcu and Thorup [STOC'11] had shown that simple tabulation, using same space and lookups yields Õ(1/n1/c-minwise independence, which is good for large sets, but useless for small sets. Our analysis uses some of the same methods, but is much cleaner bypassing a complicated induction argument.

U2 - 10.1007/978-3-319-08404-6_12

DO - 10.1007/978-3-319-08404-6_12

M3 - Article in proceedings

SN - 978-3-319-08403-9

T3 - Lecture notes in computer science

SP - 134

EP - 145

BT - Algorithm Theory – SWAT 2014

A2 - Ravi, R.

A2 - Gørtz, Inge Li

PB - Springer

T2 - 14th Scandinavian Symposium and Workshops on Algorithm Theory

Y2 - 2 June 2014 through 4 June 2014

ER -