Ball Tree

Ball Tree 是一种用于加速向量检索的空间划分树结构，特别适用于中低维稠密向量，在某些情况下比 KD-Tree 更稳定。

📌 原理简介

Ball Tree 与 KD-Tree 类似，都是通过树结构加速最近邻查询。但它不是按维度划分空间，而是将数据划分为包围球（ball）：

1. 每个节点表示一个“球形区域”，包含其所有子节点；
2. 每次划分时，将数据划为两个簇，每个簇建立一个球（中心 + 半径）；
3. 递归构建子节点，直到达到叶子条件（如点数少于阈值）。

✏️ 查询过程

查询时，通过与球的距离关系进行“剪枝”，避免不必要的遍历：

• 若当前球与查询向量的最小可能距离大于已知最近点的距离，则该球下所有点都可跳过；
• 否则递归查找子球，直到到达叶节点。

✅ 优点

• 不依赖坐标轴顺序，适用于任意维度（比 KD-Tree 更鲁棒）；
• 更适合欧氏距离下的球形分布数据；
• 支持任意距离函数（只要满足三角不等式）；
• 在中维（20~100维）场景中性能优于 KD-Tree。

⚠️ 局限性

• 在高维空间依然存在维度灾难；
• 构建时间通常比 KD-Tree 慢；
• 性能受数据分布影响较大（球重叠过多会影响剪枝效果）。

🧪 示例（scikit-learn）

from sklearn.neighbors import BallTree
import numpy as np

# 构造数据
data = np.random.random((1000, 10))  # 1000 个 10 维向量
tree = BallTree(data, leaf_size=40, metric='euclidean')

# 查询最近邻
query = np.random.random((1, 10))
dist, ind = tree.query(query, k=3)
print("最近邻索引:", ind)
print("距离:", dist)

🆚 KD-Tree vs Ball Tree

KD-Tree 和 Ball Tree 都是用于加速最近邻搜索的空间划分数据结构，适用于中小规模、低至中维度的向量检索。它们的主要区别如下：