Nearest-neighbor search

Read these first if they are new to you

Distance between two points Basic

The idea in one paragraph

Given a set of points and one new point, the query, nearest-neighbor search finds the point in the set that is closest to the query. The simplest method measures the distance from the query to every point and keeps the smallest. That method, called brute force, is always right. Its cost grows with the number of points: twice the points, twice the work, for every query. With millions of points and millions of queries, that becomes too slow, which is why faster methods such as KD-trees exist.

Brute force measures every distance and keeps the smallest

The query is the point you ask about. Its nearest neighbor is the point of the set with the smallest distance to it. Brute force, also called linear search, computes all those distances and picks the smallest. It needs no preparation, and it never misses.

The nearest point, found by checking every point

The five starting points are the ones in the worked example below. Drag the query (the cross) until its nearest neighbor changes from B to C. Then add points and watch the count of distances.

points in the set 5

One line per distance. Brute force draws a line to every point, so the work grows in step with the number of points.

Worked example: five points and one query

The points are A (1, 4), B (3, 3), C (5, 4), D (2, 0) and E (7, 1). The query is q = (4, 2).

Square the gaps in x and in y, and add them. For A: (1 − 4)² + (4 − 2)² = 9 + 4 = 13.
The others: B gives 1 + 1 = 2, C gives 1 + 4 = 5, D gives 4 + 4 = 8, E gives 9 + 1 = 10.
The smallest is 2, so B is the nearest neighbor, at distance √2 ≈ 1.41.
Sorting all five gives the three nearest: B, C, D.

Step 3 takes a square root only once, at the end. The square root never changes which number is smaller, so comparing the squared distances picks the same point and saves work.

brute_force.py

import numpy as np

pts = np.array([[1.0, 4.0], [3.0, 3.0], [5.0, 4.0], [2.0, 0.0], [7.0, 1.0]])
q = np.array([4.0, 2.0])

d2 = ((pts - q) ** 2).sum(axis=1)   # squared distance to every point
print(d2)
print(d2.argmin())                  # index of the nearest point
print(np.argsort(d2)[:3])           # the 3 nearest, closest first

[13.  2.  5.  8. 10.]
1
[1 2 3]

pts - q subtracts the query from every row by broadcasting. argmin gives the position of the smallest value, and argsort lists positions from smallest to largest.

Two variations come up often. The k nearest neighbors are the k closest points, here the first k of the sorted list. A radius search returns every point within a given distance.

The work grows with points times queries

One query against N points costs N distances. Often every point is also a query, for example to find each point's closest neighbor in its own cloud. Then N queries cost N × N distances.

Points `N`	Distances for `N` queries	Time at 10⁹ distances per second
1,000	10⁶	1 millisecond
100,000	10¹⁰	10 seconds
1,000,000	10¹²	about 17 minutes

Ten times the points means a hundred times the work. A KD-tree sorts the points into boxes once, so that each query can skip most of them.

What this page leaves out

Two points can be equally close; brute force then returns whichever comes first. The rate of a billion distances per second is a round number for illustration: real speed depends on the machine and the code. For data with hundreds of dimensions, libraries often use approximate search, which is much faster but can miss the true nearest point. This page covers exact search only.

Check yourself

Your turn: the points are (0, 0), (4, 1) and (2, 5), and the query is (3, 2). Which point is nearest? Use squared distances.

Answer
(4, 1). The squared distances are 9 + 4 = 13, 1 + 1 = 2 and 1 + 9 = 10.
A brute-force search of 50,000 points takes 2 ms per query. About how long would it take with 200,000 points?

Answer
About 8 ms. Four times the points means four times the distances.
Why is it safe to compare squared distances instead of distances?

Answer
Distances are never negative, and for numbers that are not negative, a larger number always has a larger square. So the order, and the smallest, stay the same.

Go further

Optional background.

Nearest Neighbors: Brute Force scikit-learn user guide Article Intermediate

A short, correct account of when brute force is fine and when tree methods win.
Nearest neighbor search: Linear search Wikipedia Article Intermediate

The brute-force method in context, followed by an overview of faster exact and approximate methods.

Where this shows up

Units that build on this one

KD-trees: nearest neighbors fast Intermediate