An efficient searching algorithm for approximate nearest neighbor queries in high dimensions
Sakti K. Pramanik, Savelyev Alexander, Jinhua Li · 2003
We present an approximate nearest neighbor search algorithm that uses heuristics to decide whether or not to access a node in the index tree, based on three interesting data distribution properties. We demonstrate that the proposed algorithm significantly reduces the number of nodes accessed over the algorithms that have been proposed in earlier works. Also, it is demonstrated that the proposed algorithm can retain close to 100% of the K nearest neighbors in most cases.