Approximately minwise independence with twisted tabulation

DOI10.1007/978-3-319-08404-6_12MaRDI QIDQ3188889zbMATH OpenOpenAlexFDO

Authors Søren Dahlgaard, Mikkel Thorup

Publication date 2 September 2014

Published in Algorithm Theory – SWAT 2014 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1404.6724

Mathematics Subject Classification ID

Data structures (68P05) Searching and sorting (68P10) Information storage and retrieval of data (68P20)

Abstract: A random hash function $h$ is $varepsilon$-minwise if for any set $S$, $|S|=n$, and element $xinS$, $Pr[h(x)=minh(S)]=(1pmvarepsilon)/n$. Minwise hash functions with low bias $varepsilon$ have widespread applications within similarity estimation. Hashing from a universe $[u]$, the twisted tabulation hashing of Pv{a}trac{s}cu and Thorup [SODA'13] makes $c=O(1)$ lookups in tables of size $u^{1/c}$. Twisted tabulation was invented to get good concentration for hashing based sampling. Here we show that twisted tabulation yields $ildeO(1/u^{1/c})$-minwise hashing. In the classic independence paradigm of Wegman and Carter [FOCS'79] $ildeO(1/u^{1/c})$-minwise hashing requires $Omega(logu)$-independence [Indyk SODA'99]. Pv{a}trac{s}cu and Thorup [STOC'11] had shown that simple tabulation, using same space and lookups yields $ildeO(1/n^{1/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.

Recommendations

• d-k-min-wise independent family of hash functions
• Exponential time improvement for min-wise based algorithms
• Exponential time improvement for min-wise based algorithms
• Exponential space improvement for min-wise based algorithms

Cited in

(4)

• Binary vectors for fast distance and similarity estimation
• Exponential space improvement for min-wise based algorithms
• scientific article; zbMATH DE number 7278047 (Why is no real title available?)
• Twisted tabulation hashing

This page was built for publication: Approximately minwise independence with twisted tabulation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3188889)