BallTree：节点分割与索引构建

1. 基本概念

BallTree 是用于加速最近邻搜索（kNN）的树结构。

核心思想：

• 用“超球（ball）”表示数据区域
• 递归划分空间
• 利用球的边界进行剪枝

每个节点包含：

• center：球心
• radius：半径

2. 节点分割（Node Splitting）

2.1 常见分裂方式

（1）最远点对分裂

• 找到距离最远的两个点 p1, p2
• 用它们确定分裂方向

直觉：沿数据最大延展方向切分

（2）PCA 分裂

• 对数据做 PCA
• 使用第一主成分方向
• 更稳定，但更贵

2.2 划分步骤

Step 1：方向

v = p2 - p1

Step 2：投影

t(x) = (x - p1) · v

Step 3：排序切分

• 按 t(x) 排序
• 中位数切分：
  • 左子集
  • 右子集

3. 子球构建

3.1 球心

c = 均值(x)

3.2 半径

r = max ||x - c||

4. 索引构建（重点）

BallTree 是递归二叉结构。

4.1 构建流程

BuildTree(S):

• 如果 |S| ≤ leaf_size：

  • 返回叶子节点

• 选择分裂方式

• 将 S 划分为 S_left 和 S_right

• left = BuildTree(S_left)

• right = BuildTree(S_right)

• 计算当前节点 center 和 radius

• 返回节点

5. 节点结构

Node:

• center
• radius
• left
• right
• points（仅叶子节点）

6. 树结构

Root ├── Ball │ ├── Leaf │ └── Leaf └── Ball ├── Leaf └── Leaf

7. 为什么有效

7.1 空间聚类

相近点会被划到同一球

7.2 剪枝条件

如果：

d(q, center) - radius > best_dist

则整棵子树可以跳过

8. 总结

• BallTree = 球形递归划分结构
• 分裂方式：最远点对 / PCA
• 每个节点 = (center, radius)
• 核心作用：加速 kNN 查询

Annoy：核心思想与索引机制

1. 核心思想

Annoy（Approximate Nearest Neighbors Oh Yeah）通过构建多棵随机投影树来划分高维空间。

其核心目标是：

• 将相似向量尽可能划分到相同或相邻的分区中
• 通过多树结构提升近似最近邻检索效果

2. 索引构建过程

Annoy 使用多棵随机树（forest）进行索引构建。

2.1 构建方式

每棵树的构建过程如下：

• 对数据进行递归划分
• 每一步随机选择一个超平面进行分割
• 逐步将空间划分为多个子区域

2.2 分裂方式

• 随机选择两个点
• 用两点确定一个分割超平面
• 将数据划分到超平面两侧

特点：

• 完全随机化
• 不依赖全局最优划分
• 每棵树结构不同

3. 查询过程

查询时的流程：

• 对查询向量，在每棵树中分别进行遍历
• 收集落在不同分区中的候选点
• 在候选集合中计算真实距离并排序

4. 多树机制的作用

Annoy 的关键设计在于“多树投票机制”：

• 单棵树：结果不稳定（随机性较强）
• 多棵树：结果取交集或并集后筛选

作用：

• 提升检索稳定性
• 平衡精度与效率
• 降低单棵树划分误差

5. 总结

• Annoy = 随机投影树 + 多树集成
• 索引构建 = 随机超平面递归划分
• 查询过程 = 多树遍历 + 候选集合合并
• 优点：速度快、实现简单、适合大规模近似检索
• 缺点：精度依赖树数量与随机性