Improved Densification of One Permutation Hashing

By Anshumali Shrivastava, Ping Li. 2014

60 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Information Retrieval & Search, Algorithms & Complexity, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Information Retrieval & Search

In Algorithms & Complexity

In Signal Processing

Citations in the corpus

Distributed Hierarchical GPU Parameter Server for Massive Scale Deep Learning Ads Systems (2020, methodology): “As the name suggests, our idea was inspired by several well-known hashing methods, e.g., (Goemans & Williamson, 1995; Charikar, 2002; Charikar et al., 2004; Cormode & Muthukrishnan, 2005; Weinberger et al., 2009; Li et al., 2011; 2012; Shrivastava & Li, 2014; Li et al., 2019).”
Consistent Weighted Sampling Made Fast, Small, and Easy (2014, background): “Subsequent works [20, 21] have proposed modiﬁcations to address this issue.”