Densifying One Permutation Hashing via Rotation for Fast Near Neighbor Search

By Anshumali Shrivastava, Ping Li. 2014

124 citations recorded by the source corpus.

Subfields: Information Retrieval & Search, Algorithms & Complexity

How researchers see this paper

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

In Information Retrieval & Search

In Algorithms & Complexity

Citations in the corpus

Practical and Optimal LSH for Angular Distance (2015, background): “(2)Note that if the data points are binary, more efficient LSH schemes exist [12, 13].”
A Survey on Learning to Hash (2016, background): “computation of hash functions [71], [74], [54], [130].”
Consistent Weighted Sampling Made Fast, Small, and Easy (2014, background): “Even when the sets involved are unweighted, our approach gives a simple solution to the densification problem that [20, 21] attempt to address.”
In Defense of Minhash over Simhash (2014, methodology): “Furthermore, the recent development of one permutation hashing [21, 27] has substantially reduced the preprocessing costs of MinHash, making the method more practical.”
Improved Densification of One Permutation Hashing (2014, methodology): “• Our detailed variance analysis of the hashes obtained from the existing densiﬁcation scheme [24] reveals that there is no enough randomness in that procedure which leads to high variance in very sparse datasets.”
Asymmetric Minwise Hashing for Indexing Binary Inner Products and Set Containment (2015, methodology): “In practice we will need many hashes for which we can utilize the recent line of work that make minhash and weighted minhash significantly much faster [29, 36, 38, 19].”
Deep Cross-Modal Hashing (2016, background): “…research community (Weiss et al., 2008; Raginsky & Lazebnik, 2009; Wang et al., 2010; Liu et al., 2011; Norouzi & Fleet, 2011; Norouzi et al., 2012; Rastegari et al., 2013; Yu et al., 2014; Liu et al., 2014; Shrivastava & Li, 2014; Andoni et al., 2015; Neyshabur & Srebro, 2015; Leng et al., 2015).”
Hashing for Similarity Search: A Survey (2014, methodology): “This issue is solved by performing rotation over one permutation hashing [118].”
One Permutation Hashing (2012, methodology): “For example, [24] discusses training datasets with (on average) n = 1011 items and D = 109 distinct features.”
Beyond Pairwise: Provably Fast Algorithms for Approximate k-Way Similarity Search (2013, background): “The most recent work [27] is able to fill the empty bins and works well for pairwise near neighbor search.”
Asymmetric Minwise Hashing (2014, methodology): “In practice we will need many hashes for which we can utilize the recent line of work that make minhash and weighted minhash signiﬁcantly much faster [36, 18].”