# Ball*-tree: Efficient spatial indexing for constrained nearest-neighbor search in metric spaces

arXiv: https://arxiv.org/abs/1511.00628 · HTML: https://mlsanity.com/paper/1511.00628/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Nov 2015.

## Built on by (most cited first, 9 of 9)

- [A Comprehensive Survey on Vector Database: Storage and Retrieval Technique, Challenge](https://mlsanity.com/paper/2310.11703/) (2023)
- [A Survey on Knowledge-Oriented Retrieval-Augmented Generation](https://mlsanity.com/paper/2503.10677/) (2025)
- [RoarGraph: A Projected Bipartite Graph for Efficient Cross-Modal Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2408.08933/) (2024)
- [Down with the Hierarchy: The 'H' in HNSW Stands for "Hubs"](https://mlsanity.com/paper/2412.01940/) (2024)
- [Scope2Screen: Focus+Context Techniques for Pathology Tumor Assessment in Multivariate Image Data](https://mlsanity.com/paper/2110.04875/) (2021)
- [AI Art Curation: Re-imagining the city of Helsinki in occasion of its Biennial](https://mlsanity.com/paper/2306.03753/) (2023)
- [Improving Domain Generalization on Gaze Estimation via Branch-out Auxiliary Regularization](https://mlsanity.com/paper/2405.01439/) (2024)
- [Wittgenstein's Family Resemblance Clustering Algorithm](https://mlsanity.com/paper/2601.01127/) (2026)
- [Lorica: A Synergistic Fine-Tuning Framework for Advancing Personalized Adversarial Robustness](https://mlsanity.com/paper/2506.05402/) (2025)

## Abstract (arXiv)

Emerging location-based systems and data analysis frameworks requires efficient management of spatial data for approximate and exact search. Exact similarity search can be done using space partitioning data structures, such as Kd-tree, R*-tree, and Ball-tree. In this paper, we focus on Ball-tree, an efficient search tree that is specific for spatial queries which use euclidean distance. Each node of a Ball-tree defines a ball, i.e. a hypersphere that contains a subset of the points to be searched. In this paper, we propose Ball*-tree, an improved Ball-tree that is more efficient for spatial queries. Ball*-tree enjoys a modified space partitioning algorithm that considers the distribution of the data points in order to find an efficient splitting hyperplane. Also, we propose a new algorithm for KNN queries with restricted range using Ball*-tree, which performs better than both KNN and range search for such queries. Results show that Ball*-tree performs 39%-57% faster than the original Ball-tree algorithm.