sign in
english version rss feed

inria-00567191, version 1

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

Loïc Paulevé () 1, Hervé Jégou () 2, Laurent Amsaleg () a2

Pattern Recognition Letters 31, 11 (2010) 1348-1358

Abstract: 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-dimensional 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.

  • Icone de different_hash_function.png
  • Domain : Computer Science/Information Retrieval
    Computer Science/Computer Vision and Pattern Recognition
    Computer Science/Databases
  • Keywords : Search methods – Image databases – Quantization – Database searching – Information retrieval – LSH
 
  • inria-00567191, version 1
  • oai:hal.inria.fr:inria-00567191
  • From: 
  • Submitted on: Friday, 18 February 2011 16:34:49
  • Updated on: Saturday, 19 March 2011 00:24:05
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...