Nearest-Neighbor Search Over Millions of Coordinates

“Find the closest store” is a linear scan until you put a structure in front of it. The interesting question is not that an index is faster; it is exactly what work the index removes, because that tells you when it will not help.

What the naive scan costs

The brute-force answer to “which of these n points is nearest to q” evaluates the distance function n times and keeps a running minimum. It is O(n) per query, and the constant is not small: a haversine call is four or five transcendental function evaluations, so ten million points is tens of millions of sin, cos and sqrt operations for one answer. At one query it is a noticeable pause; at a thousand queries a second it is a data centre.

The waste is obvious once stated. A point in Lisbon cannot be the nearest neighbour of a query in Helsinki, and you knew that before computing the distance. Every spatial index is a way of proving whole groups of points cannot win without examining them one at a time.

Grid, KD-tree, R-tree

• Uniform grid or geohash. Bucket every point by a fixed cell, then examine the query’s cell and its ring of neighbours. Trivial to build and to update, and it degrades exactly where real data is worst: a cell containing central London holds a million points while one over the North Sea holds none, so the worst-case bucket is still a linear scan. Hierarchical cell systems such as H3 fix the addressing and the ring arithmetic but not the density skew; you handle that by choosing resolution per region.
• KD-tree. Recursively split the point set by alternating axes at the median, giving a balanced binary tree of depth log₂ n. A query descends to the leaf containing q, then backtracks, pruning any subtree whose splitting plane is further from q than the best candidate found so far. Build is O(n log n); queries are O(log n) in expectation for low-dimensional, reasonably uniform data. It stores points, so it handles coordinates and nothing else, and rebalancing after inserts is awkward.
• R-tree. Stores minimum bounding rectangles rather than points, in a balanced tree where each node’s rectangle contains its children’s. That means it indexes lines and polygons, not just points, which is why it is what PostGIS, SQLite and most GIS software actually use. Bulk-loading with Sort-Tile-Recursive packing gives far less rectangle overlap than repeated insertion, and overlap is the thing that costs you: overlapping siblings mean a query must descend both.

The saving, derived at ten million points

Take n = 10,000,000 points and a single ten-nearest query. The arithmetic below counts distance evaluations and node visits, not milliseconds — no timing was run, and the point of counting operations is that it holds regardless of hardware.

naive scan
  distance evaluations = n = 10,000,000

KD-tree
  tree depth            = log2(10,000,000) = 23.3, so 24 levels
  descent to a leaf     = 24 node visits
  backtracking          = assumption: ~1,000 nodes visited for k=10 in 2-D
  total node visits     ~ 1,024

ratio  10,000,000 / 1,024  ~  9,800x fewer point comparisons

The backtracking figure is the assumption in that calculation and it is the one to be sceptical of. It is small when the data is two-dimensional and the query is inside the point cloud; it grows when the query is far outside the cloud, when k is large, and when the data is highly clustered so many subtrees remain candidates. A reasonable working range is a few hundred to a few thousand node visits, which puts the saving somewhere between three and five orders of magnitude — a range wide enough to be honest and narrow enough to make the decision.

The other half of the sum is the build. Sorting ten million points to construct the tree is O(n log n), roughly 233 million comparison operations, or about 23 naive queries’ worth of work. Above two dozen queries against a static dataset the index has paid for itself; below that, scan.

Getting the database to use the index

In PostGIS the index is a GiST index over the geometry or geography column, and the query that uses it for nearest neighbours is the distance-ordered form:

CREATE INDEX stores_geog_idx ON stores USING GIST (geog);

SELECT id, name, geog <-> ST_MakePoint(-0.1278, 51.5074)::geography AS m
FROM   stores
ORDER  BY geog <-> ST_MakePoint(-0.1278, 51.5074)::geography
LIMIT  10;

Three details decide whether this is an index scan or a sequential one. The ORDER BY ... LIMIT shape is what triggers index-assisted nearest-neighbour traversal; adding a WHERE ST_Distance(...) < 1000 filter instead does not use the index at all, because the planner cannot turn a function result into a bound — use ST_DWithin, which is index-aware, for that. And the operand types must match the indexed column exactly, since a cast on the column side disables the index.

The type choice matters more than it looks. On geography, the <-> operator returns metres on the spheroid. On geometry it returns distance in the units of the column’s SRID — degrees if that SRID is 4326, which is not a distance at all and will order results wrongly for the reasons set out in the page on planar distance over unprojected coordinates.

Where spatial indexes stop helping

• Dimensionality. KD-trees and R-trees rely on being able to prune with an axis-aligned bound, and that stops working as dimensions rise, because in high dimensions almost every point is roughly the same distance from the query. By a few dozen dimensions an exact index is no better than a scan. That is precisely why approximate methods such as HNSW exist, and why location embeddings need a different index from coordinates.
• The antimeridian and the poles. An index built on raw longitude treats +179.9° and −179.9° as the width of the world apart. Queries near the date line return the wrong candidate set and no error. Geography types and spherical cell systems handle it; degree-space rectangles do not.
• Nearest is not closest. The index answers a straight-line question. Across a river with no bridge for four kilometres, the geometrically nearest depot is the wrong depot. The usual pattern is to over-fetch — take the twenty nearest by index — and re-rank those with a real travel-time query, which keeps the expensive call count bounded.
• Write rate. A tree over constantly moving vehicle positions spends its life rebalancing. For live positions a coarse grid with cheap updates usually beats a tree, and the tree is kept for the static layer.