Improved Densification of One Permutation Hashing

Anshumali Shrivastava Cornell University, Ping Li Rutgers University
Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence, PMLR R12:686-695, 2014.

Abstract

The existing work on densification of one permutation hashing [24] 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 in [24] 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 [24]. This improvement is more significant for very sparse datasets which are common over the web. The improved technique has the same cost of O(d + KL) for query processing, thereby making it strictly preferable over the existing procedure. Experimental evaluations on public datasets, in the task of hashing based near neighbor search, support our theoretical findings.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR12-university14s, title = {Improved Densification of One Permutation Hashing}, author = {University, Anshumali Shrivastava Cornell and University, Ping Li Rutgers}, booktitle = {Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence}, pages = {686--695}, year = {2014}, editor = {Zhang, Nevin L. and Tian, Jin}, volume = {R12}, series = {Proceedings of Machine Learning Research}, month = {23--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r12/main/assets/university14s/university14s.pdf}, url = {https://proceedings.mlr.press/r12/university14s.html}, abstract = {The existing work on densification of one permutation hashing [24] 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 in [24] 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 [24]. This improvement is more significant for very sparse datasets which are common over the web. The improved technique has the same cost of O(d + KL) for query processing, thereby making it strictly preferable over the existing procedure. Experimental evaluations on public datasets, in the task of hashing based near neighbor search, support our theoretical findings.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Improved Densification of One Permutation Hashing %A Anshumali Shrivastava Cornell University %A Ping Li Rutgers University %B Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2014 %E Nevin L. Zhang %E Jin Tian %F pmlr-vR12-university14s %I PMLR %P 686--695 %U https://proceedings.mlr.press/r12/university14s.html %V R12 %X The existing work on densification of one permutation hashing [24] 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 in [24] 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 [24]. This improvement is more significant for very sparse datasets which are common over the web. The improved technique has the same cost of O(d + KL) for query processing, thereby making it strictly preferable over the existing procedure. Experimental evaluations on public datasets, in the task of hashing based near neighbor search, support our theoretical findings. %Z Reissued by PMLR on 04 October 2026.
APA
University, A.S.C. & University, P.L.R.. (2014). Improved Densification of One Permutation Hashing. Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R12:686-695 Available from https://proceedings.mlr.press/r12/university14s.html. Reissued by PMLR on 04 October 2026.

Related Material