K-d tree
Also known as kd-tree, k-dimensional tree. This is the canonical page; those names redirect here.
Pairings in the atlas
- Median-split axis cyclingcanonNearest-neighbor searchfull lesson ▸computational-geometry
- Surface-area heuristic splitsspecialistRay tracing accelerationcomputational-geometry
Rivals: other methods for the same problems
- Annoy
- Ball tree
- Best-bin-first search
- Bounding volume hierarchy
- CAGRA
- Cover tree
- Cross-polytope LSH
- DiskANN
- HNSW
- IVF-Flat
- IVF-PQ
- Iterative quantization
- K-d tree ray traversal
- Locality-sensitive hashing
- Multi-probe LSH
- NSG
- Navigable small world graph
- Optimized product quantization
- P-stable LSH
- Priority search k-means tree
- Product quantization
- RaBitQ
- Randomized k-d forest
- Residual quantization