CODEWITHSUNDEEP
data-structuresnearest-neighbordimensionkdtreeapproximate-nn-searching
justHelloWorld
justHelloWorld

Reputation: 6844

Which of these structures are for exact Nearest Neighbor and which ones for approximate version?

LSH is a popular algorithm for ANN.

k-d Tree is maybe the most popular solution for exactly solving NN.

However, reading this survey I found these structures and I don't understand which ones are for solving NN or ANN:

I didn't found any survey dedicated to ANN, so I think that all of these are for NN and for metric spaces (they cannot be used for non-metric spaces).

Upvotes: 1

Views: 1286

Answers (1)

gsamaras
gsamaras

Reputation: 73444

First, let me confirm that quadtree, Ball tree, R-tree and M-tree can be used for Nearest Neighbor Search (NNS).

Now if a structure can support NNS, then it can support approximate Nearest Neighbor search.

Take for example the kd-tree, which you might know better; it collects point-candidates that may be the answer to a query. If you check all the possible candidates, then you can answer the exact Nearest Neighbor query. If you check some of the candidates, then you can answer the approximate Nearest Neighbor query.

Hope that helps! :)

Upvotes: 3

Related Questions