Ball Tree

定义 Definition

Ball tree（球树）是一种用于高维数据的空间索引/数据结构，常用于最近邻搜索（nearest neighbor search）与范围查询。它通过递归地把数据点划分到一系列“球体（ball，指以某个中心点为圆心、以半径覆盖一簇点的超球）”中，以加速查询。（在不同语境下也可能泛指用球形边界进行分割的树结构。）

发音 Pronunciation (IPA)

/ˈbɔːl triː/

例句 Examples

A ball tree can speed up nearest neighbor searches.
球树可以加速最近邻搜索。

In high-dimensional embeddings, a ball tree often outperforms brute-force search by pruning large regions that cannot contain the closest point.
在高维向量嵌入中，球树常常通过剪枝那些不可能包含最近点的大区域，从而比暴力搜索更快。

词源 Etymology

ball 在这里不是“球类运动”，而是几何意义上的“球体/超球（n-ball）”，表示用“中心 + 半径”定义的覆盖区域；tree 指分层的树状索引结构。合在一起，ball tree 即“用球形边界递归划分空间的树”。

相关词 Related Words

• Kd-Tree
• Vantage-Point Tree
• Metric Space
• Nearest Neighbor
• Range Query
• Clustering
• Indexing
• Curse Of Dimensionality

文学与著作中的用例 Literary Works

• Nearest Neighbor Queries（Monika Rauch Henzinger 等相关领域文献常引用的经典主题书名/方向著作中讨论近邻结构与查询方法）
• Foundations of Multidimensional and Metric Data Structures（Hanan Samet）中讨论多维/度量空间索引结构（相关章节常涉及与 ball tree 同类的度量树思想）
• Stephen M. Omohundro, “Five Balltree Construction Algorithms” (1989)（专门讨论球树构建方法的经典论文）
• scikit-learn 官方文档与用户指南（工程实践中最常见的球树实现与说明来源之一，介绍其在最近邻搜索中的用法与适用场景）