Locality sensitive hashing: A comparison of hash function types and querying mechanisms

By Loïc Paulevé, Herv'e J'egou, Laurent Amsaleg. 2010

314 citations recorded by the source corpus.

It is well known that high-dimensional nearest neighbor retrieval is very expensive. Dramatic performance gains are obtained using approximate search schemes, such as the popular Locality-Sensitive Hashing (LSH). Several extensions have been proposed to address the limitations of this algorithm, in particular, by choosing more appropriate hash functions to better partition the vector space. All the proposed extensions, however, rely on a structured quantizer for hashing, poorly fitting real data sets, limiting its performance in practice. In this paper, we compare several families of space hashing functions in a real setup, namely when searching for high-dimension SIFT descriptors. The comparison of random projections, lattice quantizers, k-means and hierarchical k-means reveal that unstructured quantizer significantly improves the accuracy of LSH, as it closely fits the data in the feature space. We then compare two querying mechanisms introduced in the literature with the one originally proposed in LSH, and discuss their respective merits and limitations.

Subfields: Aerospace Engineering, 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 Computer Vision and Pattern Recognition

In Information Retrieval & Search

Citations in the corpus

Billion-Scale Similarity Search with GPUs (2017, methodology): “ing a minimal accuracy loss results in orders of magnitude of compression [21]. The most popular vector compression methods can be classied into either binary codes [18, 22], or quantization methods [25, 37]. Both have the desirable property that searching neighbors does not require reconstructing t”
Learning Spread-Out Local Feature Descriptors (2017, methodology): “The drawback of using a new type of distance rather than Euclidean distance is that efficient large-scale nearest neighbor search method such as locality sensitive hashing (LSH) [15] can no longer be used.”
Polysemous Codes (2016, background): “Various partitioning methods have been proposed for the coarse level [42,4].”
Hashing for Similarity Search: A Survey (2014, methodology): “E8 lattice is used because its decoding is much cheaper than Leech lattice (its quantization performance is slightly worse) A comparison of LSH methods for the Euclidean distance is given in [108].”
Iterative Quantization: A Procrustean Approach to Learning Binary Codes for Large-Scale Image Retrieval (2013, unknown): “R ECENTLY, the vision community has devoted a lot of attention to the problem of learning similaritypreserving binary codes for representing large-scale image collections [4], [5], [13], [15], [20], [22], [23], [29], [31], [36], [39], [43], [45], [49], [50], [51].”
Indexing billions of images for sketch-based retrieval (2013, methodology): “Multi-Probe KLSH KLSH utilizes unstructured k-means quantizers as hash functions: hi(x)= arg min d(x, c i j), i = 1,. .”
Parallel search of k-nearest neighbors with synchronous operations (2012, background): “At the core of each main approach, however, is the exact kNN search over a smaller corpus, which is still large enough to take a significant or even dominant portion of the total kNN search time [14].”
K-Means Hashing: An Affinity-Preserving Quantization Method for Learning Binary Compact Codes (2013, methodology): “We point out that the terminology “hashing” in [22] refers to the classical hashing strategy of distributing data into buckets so that similar data would collide in the same bucket.”
The Faiss Library (2024, unknown): “However, we do not consider this scenario as the performance is generally inferior to that of learnt partitions [20].”
Scalable Mutual Information Estimation Using Dependence Graphs (2018, background): “There are various types of LSH functions [20–22], and all of them share the common property that they map similar items to the same bins with high probability.”
Locally Optimized Product Quantization for Approximate Nearest Neighbor Search (2014, background): “For instance, [17, 19] gain performance by multiple k-means quantizers via random reinitializing or partitioning jointly trained centroids.”