whitetree: dynamic exact kNN without rebuilds, 40-300x faster than sklearn BallTree
monononon34 · reddit · 2026-09-14
The author open-sourced whitetree, a library for exact Mahalanobis nearest-neighbour search on streaming low-dimensional data: whiten with the Cholesky factor of covariance, then keep multiple scipy cKDTrees with a geometric size ratio of 32 so inserts/deletes never force full rebuilds.
Key measured findings:
- Static queries are 40-300x faster than sklearn's BallTree(mahalanobis) and 7-60x faster than FAISS Flat at 500k points.
- Textbook Bentley-Saxe decomposition fails on cKDTree: query has a fixed per-call cost, so the number of trees visited matters; the ratio-32 scheme retains 47-97% (batch) / 20-80% (single-query) throughput.
- FAISS's native PCAMatrix whitening hurts recall (0.841 at condition number 1e8, NaN with large DC offset), but the same whitened data scores 1.000 via IndexFlatL2 — the problem is whitening estimation, not search.
- Whether a dynamic index pays off depends on update/query interleaving: per-batch rebuilds beat whitetree in batch workloads (2.2s vs 14.9s), but in strict insert/delete/query interleaving whitetree hits 1100 steps/s vs 20 for FAISS IDMap2 (O(n) removeids).
Pure numpy/scipy, single-writer multi-reader, tombstone deletes, results exactly match a static cKDTree. Code and design notes on GitHub.
More from Research
- Johns Hopkins preprint finds 3,022 recursive splice sites in the human genome — anshulkundaje · 2026-09-14
- Shanghai team open-sources NCP-ArchPreview, an 8.9B model that predicts concepts instead of tokens — wonderwomancode · 2026-09-14
- Muon-trained models leave a distinctive spectral signature in their weights — QuanquanGu · 2026-09-14
- Expressive power isn't what gradient descent finds: why RNN cells excel at state-tracking generalization — mike64_t · 2026-09-14
- Google AI x Econ team finds field evidence that prior expertise drives learning from AI-assisted work — soumitrashukla9 · 2026-09-14
- Graph theory from hometown streets: navigation, genome assembly and Hamiltonian paths — TivadarDanka · 2026-09-14