Locality-sensitive hashing scheme based on p-stable distributions

By Mayur Datar, Nicole Immorlica, Piotr Indyk, Vahab S. Mirrokni. 2004

3,463 citations recorded by the source corpus.

Subfields: Aerospace Engineering, Artificial Intelligence, Computer Vision and Pattern Recognition, Information Retrieval & Search

How researchers see this paper

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

In Aerospace Engineering

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Information Retrieval & Search

Citations in the corpus

Aggregating Local Image Descriptors into Compact Codes (2012, methodology): “One of the most popular techniques is Euclidean Locality-Sensitive Hashing [36], which has been extended in [17] to arbitrary metrics.”
Product Quantization for Nearest Neighbor Search (2011, methodology): “In this case, one of the most popular ANN algorithms is the Euclidean Locality-Sensitive Hashing (E2LSH) [7], [11], which provides theoretical guarantees on the search quality with limited assumptions.”
Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS) (2014, background): “2 LSH for L2 Distance (L2LSH) [6] presented a novel LSH family for all Lp (p ∈ (0,2]) distances.”
CodeXGLUE: A Machine Learning Benchmark Dataset for Code Understanding and Generation (2021, methodology): “Deckard [39] computes vectors for structural information within ASTs and uses a Locality Sensitive Hashing (LSH) [14] to cluster similar vectors.”
Deep learning in neural networks: An overview (2014, methodology): “It outperformed previous searchers for similar documents, such as Locality Sensitive Hashing (Buhler, 2001; Datar, Immorlica, Indyk, & Mirrokni, 2004).”
Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality (2012, background): “In contrast, for the `2 norm, one can further reduce the exponent to 1/c 2 ([AI06], building on [DIIM04]).”
GraphCodeBERT: Pre-training Code Representations with Data Flow (2020, methodology): “, 2007) is to compute vectors for structural information within ASTs and then a Locality Sensitive Hashing (LSH) (Datar et al., 2004) is used to cluster similar vectors for detection.”
Propagation kernels: efficient graph kernels from propagated information (2014, background): “where pt,u is the node-label distribution of node u at iteration t and h (·) is a quantization function (Gersho and Gray 1991), more precisely a locality sensitive hash (lsh) function (Datar and Indyk 2004), which will be introduced in more detail in the next section.”
DECKARD: Scalable and Accurate Tree-Based Detection of Code Clones (2007, methodology): “Locality Sensitive Hashing (LSH) [7,9] is precisely what we need.”
Locally Optimized Product Quantization for Approximate Nearest Neighbor Search (2014, background): “Significant benefit is to be gained via multiple quantizers or hash tables as in LSH [6], at the cost of storing each point index multiple times.”
Inductive Hashing on Manifolds (2013, methodology): “With the success of LSH, random hash functions have been extended to several similarity measures, including p-norm distances [6], the Mahalanobis metric [17], and kernel similarity [16, 24].”
Variational Deep Semantic Hashing for Text Documents (2017, methodology): “html in the prior work [36]: Locality Sensitive Hashing (LSH)6 [2], Spectral Hashing (SpH)7 [38], Self-taught Hashing (STH)8 [41], Stacked Restricted Boltzmann Machines (Stacked RBMs) [28], Supervised Hashing with Kernels (KSH) [20], and Semantic Hashing using Tags and Topic Modeling (SHTTM) [36].”
VisualRank: Applying PageRank to Large-Scale Image Search (2008, methodology): “For our algorithm, approximation methods [38], [39], [37]”
Optimal Data-Dependent Hashing for Approximate Near Neighbors (2015, neutral): “Focusing on the Euclidean space, subsequent research showed that one can obtain a better exponent: ρ ≤ 1/c(2) [11, 3](2).”
Optimized Cartesian K-Means (2014, methodology): “Such approaches map data points to compact binary codes through a hash function, which can be generally expressed as b = h ( x ) ∈ { 0 , 1 } L , where x is a P -dimensional real-valued point, h ( · ) is the hash function, and b is a binary vector with L entries.”
Deep belief networks (2009, methodology): “Locality-Sensitive Hashing (LSH) [1] takes about 0.5 seconds to perform the same search using E LSH 0.1 software, provided by Alexandr Andoni and Piotr Indyk.”
Practical Federated Gradient Boosting Decision Trees (2019, methodology): “To obtain the similarity of any two instances in the joint data without exposing the raw data to the other parties, we adopt the widely used p-stable LSH function (Datar et al. 2004).”