Can ANN search surpass the accuracy of NN search in large databases with high-dimensional representations?

Question

ANN search is known to outperform NN search in terms of efficiency and some techniques reduce storage space from compact representations. But what happens in terms of effectiveness? Is it possible to achieve the same performance without finding the nearest neighbor with exhaustive search?

Answer 1

I tried binary search and ann search on ip2location database. It has the same speed but with many optimizations. You can find a source code at https://ip2locationphp.codeplex.com/.

Answer 2

If by effectiveness, you mean accuracy (i.e. finding the exact nearest neighbor), then no. NN search will always find the exact NN, while ANN search will, at its best chance, find the exact NN, that is a tie at the result with NN search.

However, in a high dimensional space the curse of dimensionality lurks and the usual data structures and algorithms for 2D and 3D tend to be as slow as the brute force search, thus an ANN search is the way to go, when you (big) data live in a high dimensional space.