  Similarity search in high-dimensional spaces is an important task for many
multimedia applications. Due to the notorious curse of dimensionality,
approximate nearest neighbor techniques are preferred over exact searching
techniques since they can return good enough results at a much better speed.
Locality Sensitive Hashing (LSH) is a very popular random hashing technique for
finding approximate nearest neighbors. Existing state-of-the-art Locality
Sensitive Hashing techniques that focus on improving performance of the overall
process, mainly focus on minimizing the total number of IOs while sacrificing
the overall processing time. The main time-consuming process in LSH techniques
is the process of finding neighboring points in projected spaces. We present a
novel index structure called radius-optimized Locality Sensitive Hashing
(roLSH). With the help of sampling techniques and Neural Networks, we present
two techniques to find neighboring points in projected spaces efficiently,
without sacrificing the accuracy of the results. Our extensive experimental
analysis on real datasets shows the performance benefit of roLSH over existing
state-of-the-art LSH techniques.

Databases;Multimedia