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 permu- tation hashing [24] reduces the query processing cost of the (K, L)-parameterized Locality Sen- sitive 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 analy- sis reveals that the existing densification scheme in [24] is sub-optimal. In particular, there is no enough randomness in that procedure, which af- fects its accuracy on very sparse datasets. In this paper, we provide a new densification pro- cedure which is provably better than the existing scheme [24]. This improvement is more signifi- cant 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 ex- isting 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 permu- tation hashing [24] reduces the query processing cost of the (K, L)-parameterized Locality Sen- sitive 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 analy- sis reveals that the existing densification scheme in [24] is sub-optimal. In particular, there is no enough randomness in that procedure, which af- fects its accuracy on very sparse datasets. In this paper, we provide a new densification pro- cedure which is provably better than the existing scheme [24]. This improvement is more signifi- cant 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 ex- isting 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 permu- tation hashing [24] reduces the query processing cost of the (K, L)-parameterized Locality Sen- sitive 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 analy- sis reveals that the existing densification scheme in [24] is sub-optimal. In particular, there is no enough randomness in that procedure, which af- fects its accuracy on very sparse datasets. In this paper, we provide a new densification pro- cedure which is provably better than the existing scheme [24]. This improvement is more signifi- cant 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 ex- isting 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