Enhancing Locality Sensitive Hashing with Peek-Probing and Nearest Neighbor Links
Aleksandar Stupar, Sebastian Michel · 2012
In this work, we consider search in high dimensional data and propose two optimization techniques for Locality Sensitive Hashing (LSH). LSH has been successfully applied to search in multi-media databases or to duplicate detection in large Web or XML collections. LSH maps objects from a high-dimensional feature space to a set of buckets, using a hash function likely to cause hash collisions for similar objects. The first enhancement of LSH is based on additionally introduced links for each point in the feature space. These links refer to the exact nearest neighbor. The second approach is coined Peek-Probing, where LSH buckets are only fully read if they indicate a certain amount of useful information. The techniques are fully orthogonal and, hence, can be used in a combined way for further improved performance. We study the suitability of our approaches based on a series of experiments using high-dimensional image features of different flavor. We report on performance numbers for our algorithms and baseline competitors when tuned to provide answers of a minimum accuracy. 1.