Space-partitioning trees

Types and behavior

KD-tree: Splits on a single coordinate (axis-aligned hyperplane), alternating dimensions. Works well in low dimensions; in high dimensions many splits are needed and the tree becomes deep and less selective. Build is O(n log n) in the best case; query is O(log n) to reach a leaf when no backtracking is needed.

Ball tree: Partitions by enclosing points in balls and splitting balls; can be better for some metrics (e.g. non-axis-aligned structure). Each node stores a centroid and radius; query descends by distance to child balls. Often used in scikit-learn for nearest-neighbor and kernel methods.

Random projection trees (e.g. Annoy): Split on a random direction (linear combination of coordinates); building many trees and querying all of them improves recall. Common theme: the partition is geometric and hierarchical, so query cost is O(depth) to reach a leaf, plus the cost of searching the leaf (and possibly backtracking). Multiple trees reduce variance and improve robustness to unlucky splits.

Query pipeline

At index time: recursively partition the dataset until leaves are small enough (e.g. bucket size < L). At query time: start at the root, decide which child the query vector lies in (e.g. which side of the hyperplane), descend until a leaf is reached, then compute distances to points in that leaf. For ANN, implementations often allow backtracking (visit sibling nodes) or searching multiple leaves (e.g. in Annoy, aggregate over many trees) to improve recall at the cost of latency.

Pipeline summary: embed query → descend tree(s) → reach leaf/buckets → compute distances (and optionally backtrack) → return top-k. No neighbor links are stored; only the partition geometry drives the path.

Trade-offs and limitations

Pros: Clear geometric interpretation; no per-point links (lower memory than graph indexes); deterministic partition structure; good for low-dimensional data and small-to-medium scale. Cons: In high dimensions, the number of cells grows and backtracking can visit many nodes, eroding the speed advantage over brute force (curse of dimensionality). Inserts and updates often require rebalancing or full rebuilds; many ANN tree implementations are static.

Compared to IVF: both partition space; IVF uses a fixed set of cells (e.g. Voronoi) and probes nprobe cells, while trees use a hierarchical split. Compared to HNSW: trees do not store explicit neighbor edges; graph indexes can achieve higher recall at low latency in high dimensions because navigation is driven by nearest-neighbor links rather than hyperplane sides.

Role in vector databases

Pure space-partitioning trees are less common in production vector DBs than IVF or HNSW because high-dimensional data often makes tree pruning less effective and build/update more brittle. They still appear in libraries (e.g. Annoy, scikit-learn’s BallTree) and in hybrid or educational settings.

Understanding them clarifies the difference between “partition by geometry” (trees, IVF) and “navigate by neighbor links” (graph indexes). Practical tip: for low-dimensional or small datasets, a KD-tree or ball tree can be sufficient and easy to reason about; for high-dimensional ANN at scale, prefer IVF or HNSW and tune nprobe or efSearch for your recall-latency target.