On Densification for Minwise Hashing


Publication date: July 22, 2019

Tung Mai, Anup Rao, Matt Kapilevich, Ryan A. Rossi, Yasin Abbasi-Yadkori, Ritwik Sinha

One Permutation Hashing (OPH) is a significantly more efficient alternative to the popular minwise hashing. To produce a sketch of size $k$, OPH requires just one hash function whereas the classical minwise hashing requires $k$ hash functions. However, OPH does not have the desirable locality sensitive hashing (LSH) property that is important for indexing. [Srivastava and Li 2014, ICML] proposed the novel idea of densification to produce LSH sketches from OPH sketches, and gave the first densification routine. In this paper, we give a necessary and sufficient condition for a densification routine to result in LSH sketches when applied to OPH sketches. Furthermore, we give a novel densification routine that for every input, takes $O(k \log k)$ time in expectation and achieves better variance than the previous best bound obtained by [Srivastava 2017, ICML]. The running time of the densification routine given in [Srivastava 2017, ICML] for worst case inputs is $O(k^2)$ in expectation.

Research Area:  Adobe Research iconAI & Machine Learning