# How to find the closest vector to a given vector?

Let's say I have several points / vectors (in 2D to keep it simple, but could be of any dimension)

``````   [x1, y1]
[x2, y2]
[x3, y3]
....
[xn, yn]
``````

If I pick some point `[x', y']`, how do I find the closest point to it?

For a more concrete / practical example, imagine these are coordinates of houses. If I have thousands of houses in the database, I'd love to find the closest house to my house. Or more generally, I'd like to find the K closest houses to my house.

One brute-force way to do this is to cycle through each point and find its distance to your point/house and just pick the smallest one. But with thousands or even millions of data points it's not efficient at all.

Is there a faster algorithm at all? Or am I stuck trying to check each point one at a time?

• If the dimension is low, you can partition the space, e.g. using some kind of quad-tree in the 2D case. Commented Feb 26, 2016 at 11:18
• See for example k-d trees: Nearest neighbour search” on Wikipedia
– amon
Commented Feb 26, 2016 at 11:44
• stackoverflow.com/questions/3740657/… Commented Feb 26, 2016 at 12:48
• One very common optimization is to check the squared distance rather than the actual distance, avoiding a bunch of sqrt computations. Commented Feb 27, 2016 at 0:12