# Improved Densification of One Permutation Hashing

arXiv: https://arxiv.org/abs/1406.4784 · HTML: https://mlsanity.com/paper/1406.4784/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Jun 2014.

## Built on by (most cited first, 6 of 6)

- [Differentially Private One Permutation Hashing and Bin-wise Consistent Weighted Sampling](https://mlsanity.com/paper/2306.07674/) (2023)
- [C-OPH: Improving the Accuracy of One Permutation Hashing (OPH) with Circulant Permutations](https://mlsanity.com/paper/2111.09544/) (2021)
- [BOLT: An Automated Deep Learning Framework for Training and Deploying Large-Scale Search and Recommendation Models on Commodity CPU Hardware](https://mlsanity.com/paper/2303.17727/) (2023)
- [A Fast Randomized Algorithm for Massive Text Normalization](https://mlsanity.com/paper/2110.03024/) (2021)
- [Fast Gumbel-Max Sketch and its Applications](https://mlsanity.com/paper/2302.05176/) (2023)
- [Minwise-Independent Permutations with Insertion and Deletion of Features](https://mlsanity.com/paper/2308.11240/) (2023)

## Abstract (arXiv)

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. 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.