machine learning - Best Performance-Critical Algorithm for Solving Nearest Neighbor

Question

We have a list of x,y pairs. Every pair represents a point on a 2D space. I want to find the closest point from this list, to a specific point xq,yq. What is the best performance-critical algorithm for this problem? Lisp of points is not going to change; which means I do not need to perform insertion and deletion. I want just to find the nearest neighbor of a target xq,yq point in this set.

Edit 1: Thanks to all! As Stephan202 has guessed correctly, I want to do this repeatedly; like a function. An the list is not necessarily sorted (In fact I do not understand how can it be sorted? Like a table with a primary key of 2 columns a and y? If that helps then I will sort it).

I will construct the data structure based on the list one time, and then I will use this generated data structure in the function (if this process itself is relevant).

Thank you Jacob; It seems that KD-Tree data structure is a good candidate for being the answer (And I feel it is. I will update when I get some relevant results).

Edit 2: I have found that, this problem is named "nearest neighbor"!

Edit 3: First title was "In Search of an Algorithm (for Spatial-Querying and Spatial-Indexing) (Nearest Neighbor)"; I have chose a new title: "Best Performance-Critical Algorithm for Solving Nearest Neighbor". Since I do not want to perform insertion and deletion operation on my initial data and I want just the nearest one from them to a new point (which is not going to be inserted), I chose to (currently) working on KD-Trees. Thanks to all!

Answer 1

As Stephan202 noted, if you plan to find the closest-match for more than one point, you should use a tree.

I would recommend a KD-tree, whose implementation can be easily found in several packages like OpenCV 2.0. Or you could implement one yourself!

EDIT: I had asked a question about kd-tree implementations here - might be useful.

EDIT: KD-trees have been widely used successfully for NN searches :) - Also, if you're willing to accept approximate matches, you can use Fast Library for Approximate Nearest Neigbor (FLANN). The FLANN implementation is present in OpenCV 2.0.

If you don't want approximate answers you can tweak the FLANN parameters to search the entire tree.