Improving Locality Sensitive Hashing by Efficiently Finding Projected Nearest Neighbors
This work addresses a specific bottleneck in LSH for similarity search in high-dimensional spaces, which is incremental but improves efficiency for multimedia applications.
The paper tackled the problem of efficiently finding neighboring points in projected spaces for Locality Sensitive Hashing (LSH), a key bottleneck in similarity search, and introduced roLSH, which uses sampling and neural networks to achieve this without sacrificing accuracy, showing performance benefits over state-of-the-art LSH techniques in experiments on real datasets.
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.