Improved Densification of One Permutation Hashing

Understand

The existing work on densification of one permutation hashing reduces the query processing cost of the $(K,L)$-parameterized Locality Sensitive Hashing (LSH) algorithm with minwise hashing, from $O(dKL)$ to merely $O(d + KL)$, where $d$ is the number of nonzeros of the data vector, $K$ is the number of hashes in each hash table, and $L$ is the number of hash tables.

• While that is a substantial improvement, our analysis reveals that the existing densification scheme is sub-optimal.
• In particular, there is no enough randomness in that procedure, which affects its accuracy on very sparse datasets.
• In this paper, we provide a new densification procedure which is provably better than the existing scheme.