# Approximately Minwise Independence with Twisted Tabulation

arXiv: https://arxiv.org/abs/1404.6724 · HTML: https://mlsanity.com/paper/1404.6724/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Apr 2014.

## Built on by (most cited first, 1 of 1)

- [On minimizers and convolutional filters: theoretical connections and applications to genome analysis](https://mlsanity.com/paper/2111.08452/) (2021)

## Abstract (arXiv)

A random hash function h is varepsilon-minwise if for any set S, |S|=n, and element x∈ S, Pr[h(x)=min h(S)]=(1±varepsilon)/n. Minwise hash functions with low bias varepsilon have widespread applications within similarity estimation. Hashing from a universe [u], the twisted tabulation hashing of Pvatracscu 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 tilde O(1/u1/c)-minwise hashing. In the classic independence paradigm of Wegman and Carter [FOCS'79] tilde O(1/u1/c)-minwise hashing requires Omega(log u)-independence [Indyk SODA'99]. Pvatracscu and Thorup [STOC'11] had shown that simple tabulation, using same space and lookups yields tilde O(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.