  Finding nearest neighbors in high-dimensional spaces is a fundamental
operation in many multimedia retrieval applications. Exact tree-based indexing
approaches are known to suffer from the notorious curse of dimensionality for
high-dimensional data. Approximate searching techniques sacrifice some accuracy
while returning good enough results for faster performance. Locality Sensitive
Hashing (LSH) is a very popular technique for finding approximate nearest
neighbors in high-dimensional spaces. Apart from providing theoretical
guarantees on the query results, one of the main benefits of LSH techniques is
their good scalability to large datasets because they are external memory
based. The most dominant costs for existing LSH techniques are the algorithm
time and the index I/Os required to find candidate points. Existing works do
not compare both of these dominant costs in their evaluation. In this
experimental survey paper, we show the impact of both these costs on the
overall performance of the LSH technique. We compare three state-of-the-art
techniques on four real-world datasets, and show that, in contrast to recent
works, C2LSH is still the state-of-the-art algorithm in terms of performance
while achieving similar accuracy as its recent competitors.
