Constructions of $k$-Min-Wise Hash from Bounded Independence

Abstract

Min-wise hashing and its $k$-min-wise extension are fundamental tools in sampling, sketching, and similarity estimation. A standard approach to constructing such families is bounded independence. For ordinary min-wise hashing, the required degree of independence is fully understood: $\hat{I}˜(\log 1/\hat{I}´)$-wise independence is both sufficient and necessary. For $k$-min-wise hashing, however, the best previous result only showed that $O(k\log \log 1/\hat{I}´+\log 1/\hat{I}´)$-wise independence suffices, with no matching lower bound. We give a tight characterization of the amount of bounded independence required for $k$-min-wise hashing, proving that $\hat{I}˜(k+\log 1/\hat{I}´)$-wise independence is both sufficient and necessary. This improves the previous upper bound and provides a matching lower bound. Consequently, the standard construction of bounded-independent hash families has seed length $O((k+\log 1/\hat{I}´)\log (N/\hat{I}´))$. In particular, for any polynomially small error $\hat{I}´$ and any $k=\hat{I}\text{c◯}(\log N)$, it achieves the optimal seed length $O(k\log N)$. We also study random affine hash functions over ${\mathbb{F}}_2$ and show that, despite being pairwise independent, they may incur multiplicative error $\hat{I}\text{c◯}(\log n)$ even for ordinary min-wise hashing.

Topics & keywords