Kd-Tree

A kd-tree (k-dimensional tree, Bentley 1975) is a binary space-partitioning structure for points in $\mathbb{R}^d$ that makes nearest-neighbour queries sub-linear on average. It is the default answer to “find the closest point(s)” in low-dimensional geometric data — 3D point clouds above all — and, in randomized-forest form, a practical tool for approximate matching of high-dimensional float descriptors.

Construction

Each internal node splits the point set with an axis-aligned hyperplane:

Choose a splitting dimension — classically cycling through dimensions by depth ( $x, y, z, x, \dots$ ), or better, the dimension of largest variance/spread of the points in the node.
Choose the splitting value — typically the median coordinate, which guarantees a balanced tree of depth $O(\log n)$ .
Recurse on the two halves until nodes hold fewer than a leaf-size threshold of points.

Building costs $O(n \log n)$ with median-of-medians or presorting; the tree stores each point once.

Nearest-neighbour search

A query $\mathbf{q}$ first descends to the leaf containing it ( $O(\log n)$ comparisons) and takes the best point found there as the current candidate with distance $r_{\text{best}}$ . Then the search backtracks: at each node on the way up, the other subtree must be visited only if the splitting plane is closer than the current best, i.e., if

|q_k - s| < r_{\text{best}}

where $q_k$ is the query’s coordinate in the node’s split dimension $k$ and $s$ the split value — geometrically, only if the hypersphere of radius $r_{\text{best}}$ around $\mathbf{q}$ crosses the plane. Otherwise the whole subtree is pruned. The same scheme yields k-nearest-neighbour queries (keep a heap of the best $k$ ) and radius searches.

In low dimensions ( $d \lesssim 10$ ), pruning is effective and the average query cost is $O(\log n)$ .

The curse of dimensionality

As $d$ grows, distances concentrate — the nearest and farthest neighbours become relatively similar in distance — and the pruning sphere intersects almost every splitting plane, so the search degenerates toward a full linear scan while paying tree-traversal overhead. As a rule of thumb, exact kd-tree search needs $n \gg 2^d$ to beat brute force; SIFT’s 128 dimensions are far beyond the exact-search regime. Two remedies define modern practice:

Best-bin-first (BBF) (Beis & Lowe, 1997): explore nodes in order of their distance to the query using a priority queue, and stop after a fixed budget of leaf examinations, returning the best candidate found. This turns the kd-tree into an approximate method with a tunable accuracy/speed dial — introduced precisely for SIFT matching.
Randomized kd-tree forests: build several trees with randomized split-dimension choices (among the top-variance dimensions) and search them through one shared priority queue; a neighbour “hidden” behind a bad split in one tree is found via another. This is one of FLANN’s core indexes.

Note that kd-trees compare raw vectors under L2 — for binary descriptors under Hamming distance, LSH or HBST are the appropriate structures.

Where kd-trees appear in SLAM

ICP and point-cloud registration: the correspondence step — nearest model point for every scene point, every iteration — is a batch of 3D NN queries; PCL, Open3D, and libpointmatcher all use kd-trees (FAST-LIO2 builds an incrementally-updatable variant, ikd-Tree, to avoid rebuilding as the map grows).
Descriptor matching: approximate NN over SIFT/SuperPoint-style descriptors in SfM and relocalization pipelines (via FLANN).
Map queries: radius searches for local map extraction, normal estimation neighbourhoods, keyframe position lookups, and mesh/surfel neighbour searches.

Why it matters for SLAM

Nearest-neighbour search is one of the most-executed primitives in a SLAM system — inside every ICP iteration of a LiDAR or RGB-D pipeline, inside every matching stage of a feature pipeline, inside mapping operations like normal estimation and downsampling. Knowing the kd-tree’s mechanics tells you when it is the right tool (3D points: superb; 128-D descriptors: only in approximate/forest form; binary descriptors: wrong tool) and explains the design of the libraries built on top of it (FLANN’s indexes, PCL’s search module, ikd-Tree). It is also a recurring systems bottleneck: rebuild-vs-update strategies for a growing map directly shape the architecture of real-time LiDAR odometry.