One Permutation Hashing

By Ping Li, Art B. Owen, Cun-Hui Zhang. 2012

141 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

Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS) (2014, methodology): “ng future area. One good example is to ﬁnd special ALSH schemes for binary data by exploring prior powerful hashing methods for binary data such as (b-bit) minwise hashing and one permutation hashing [3, 24]. • Fast hashing for MIPS: Our proposed hash function uses random projection as the main hash”
Learning to Hash for Indexing Big Data—A Survey (2015, methodology): “By converting rank lists to a triplet tensor matrix, listwise hashing is designed to preserve the ranking in the Hamming space [76].”
Densifying One Permutation Hashing via Rotation for Fast Near Neighbor Search (2014, methodology): “The original one permutation hashing paper (Li et al., 2012) proved the following unbiased estimator of R ˆ R OP H,ub = N mat k − N emp (9) N emp = k−1 ∑ j=0 1 { OP H j (π(S 1 )) = E and OP H j (π(S 2 )) = E } N mat = k−1 ∑ j=0 1 { OP H j (π(S 1 )) = OP H j (π(S 2 )) ̸ = E } which unfortunately is…”
Consistent Weighted Sampling Made Fast, Small, and Easy (2014, methodology): “While our algorithm can be used with any unweighted similarity estimation scheme, using it with the one permutation hashing scheme of [17] will give us unweighted sets of expected size at most β−1 Lk t−τ , .”
In Defense of Minhash over Simhash (2014, methodology): “6 Conclusion Minwise hashing (MinHash), originally designed for detecting duplicate web pages [3, 10, 15], has been widely adopted in the search industry, with numerous applications, for example, large-sale machine learning systems [23, 21], Web spam [29, 18], content matching for online advertising”
Beyond Pairwise: Provably Fast Algorithms for Approximate k-Way Similarity Search (2013, background): “One permutation hashing [22] provides the hope of reducing many permutations to merely one.”
Improved Densification of One Permutation Hashing (2014, methodology): “The ˚ : (cid:127) (cid:218) ) 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 1 1 0 1 0 0 1 1 0 ˚ : (cid:127) (cid:219) ) 0 0 0 0 0 1 1 1 0 0 0 0 1 0 1 0 1 1 0 0 0 0 0 0 Figure 1: One permutation hashes [18] for vectors S 1 and S 2 using a single permutation π .”
A Survey on Learning to Hash (2016, background): “computation of hash functions [71], [74], [54], [130].”
Coding for Random Projections (2013, methodology): “This is inspired by the work on linear learning with b-bit minwise hashing (Li et al., 2012; Shrivastava & Li, 2014).”
Mining of Massive Datasets (2011, methodology): “The paper on Google’s MapReduce is [10].”
Hashing for Similarity Search: A Survey (2014, methodology): “One-permutation hashing [73], also uses one permutation, but breaks the space into K bins, and stores the smallest nonzero position in each bin and concatenates them together to generate a sketch.”
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).”