Locality-Sensitive Hashing for Chi2 Distance
Authors:
- 6 October 2011
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Pattern Analysis and Machine Intelligence
- Vol. 34 (2) , 402-409
Abstract
In the past 10 years, new powerful algorithms based on efficient data structures have been proposed to solve the problem of Nearest Neighbors search (or Approximate Nearest Neighbors search). If the Euclidean Locality Sensitive Hashing algorithm, which provides approximate nearest neighbors in a euclidean space with sublinear complexity, is probably the most popular, the euclidean metric does not always provide as accurate and as relevant results when considering similarity measure as the Earth-Mover Distance and χ2 distances. In this paper, we present a new LSH scheme adapted to χ2 distance for approximate nearest neighbors search in high-dimensional spaces. We define the specific hashing functions, we prove their local-sensitivity, and compare, through experiments, our method with the Euclidean Locality Sensitive Hashing algorithm in the context of image retrieval on real image databases. The results prove the relevance of such a new LSH scheme either providing far better accuracy in the context of image retrieval than euclidean scheme for an equivalent speed, or providing an equivalent accuracy but with a high gain in terms of processing speed.Keywords
This publication has 15 references indexed in Scilit:
- Scalable active learning strategy for object category retrieval2010
- Product Quantization for Nearest Neighbor SearchIEEE Transactions on Pattern Analysis and Machine Intelligence, 2010
- The Elements of Statistical Learning2009
- Combining visual dictionary, kernel-based similarity and learning strategy for image category retrievalComputer Vision and Image Understanding, 2008
- NV-Tree: An Efficient Disk-Based Index for Approximate Search in Very Large High-Dimensional CollectionsIEEE Transactions on Pattern Analysis and Machine Intelligence, 2008
- Locality-sensitive hashing scheme based on p-stable distributions2004
- Mean shift based clustering in high dimensions: a texture classification example2003
- Content-based image retrieval at the end of the early yearsIEEE Transactions on Pattern Analysis and Machine Intelligence, 2000
- The Earth Mover's Distance as a Metric for Image RetrievalInternational Journal of Computer Vision, 2000
- Support vector machines for histogram-based image classificationIEEE Transactions on Neural Networks, 1999