Limited Independence Suffices for Large-k Min-wise Hashing

Abstract

Min-wise hashing and its $k$-min-wise variant are standard tools in similarity estimation, sampling, sketching, and streaming. A $k$-min-wise family requires every prescribed $r$-subset of a fixed set, for $r\le k$, to appear as the $r$ smallest hash values with approximately the fully random probability, up to multiplicative error $\hat{I}´$. Previous analyses show that $O(\log (1/\hat{I}´)+k\log \log (1/\hat{I}´))$-wise independence suffices. Consequently, for $k=\hat{I}˜(\log N)$ and $\hat{I}´=N^{-c}$, the standard polynomial construction uses $O(k\log N\log \log N)$ seed bits. Recent work of Chen, Huang, and Li achieves the optimal $O(k\log N)$ seed length for $k={\log }^{O(1)}N$, but only with almost-polynomial error $2^{-O(\log N/\log \log N)}$, leaving open whether polynomially small error is possible with the same seed length. We prove that the standard $s$-wise independent polynomial hash family is $k$-min-wise with multiplicative error $\hat{I}´$ for $s=O(k+\log (1/\hat{I}´)).$ Thus, when $k=\hat{I}\text{c◯}(\log (1/\hat{I}´))$, only $O(k)$-wise independence is required. In particular, for $k=\hat{I}˜(\log N)$ and $\hat{I}´=N^{-c}$, this gives an explicit family with seed length $O(k\log N)$, matching the support-size lower bound up to constant factors. The proof conditions on the prescribed bottom set and bounds the error only after averaging over the random threshold given by its largest hash value, rather than controlling every threshold separately.

Topics & keywords