前言

如果你对这篇文章感兴趣，可以点击「【访客必读 - 指引页】一文囊括主页内所有高质量博客」，查看完整博客分类与对应链接。

最近邻搜索的目标是从 $N$ 个对象中，快速找到距离查询点最近的对象。根据需求的不同，该任务又分为「精准查找」与「近似查找」，并且查找的目标也分为「找到前 $K$ 个最近的对象」与「找到距查询点距离小于 $r$ 的对象」。处理此类任务的关键在于组织已有对象的数据结构，大致分为以下三类：

1. 树型结构：例如 Vantage-Point Tree (VP-Tree) [1]、M-Tree [2]、Cover Tree [3]、Faster Cover Trees [4] 等；
2. 图型结构：例如 Hierarchical Navigable Small World (HNSW) [5]、Locallyadaptive Vector Quantization (LVQ) [6] 等；
3. 哈希方法：例如 Locality Sensitive Hashing (LSH) 中的 SimHash、MinHash 等。

在当前时代下，如果你的对象就是向量，使用的距离度量也是常见度量（e.g., 欧式距离、余弦相似度等），可以直接调用一些成熟的向量数据库或最近邻检索算法库解决问题。

本文主要对一个经典的树型结构 M-Tree 进行介绍（已提出 20 多年，在数据库领域有大量应用），其特点是：

1. 支持任意满足对称性 (Symmetry)、非负性 (Non-negativity)、三角不等式 (Triangle Inequality) 的距离度量；
2. 支持整体数据结构的动态维护，即根据新对象的插入对整体结构做局部调整。

---

M-Tree 结构

M-Tree 中分为内部节点和叶节点，其中每个内部节点包含一个路由对象 (Routing Objects) $O_r$，并且动态维护该路由节点所覆盖的半径 $r(O_r)$，即 $O_r$ 对应子树中的所有点，距 $O_r$ 的距离小于等于 $r(O_r)$。维护每个内部节点的覆盖半径，可用于后续近邻查搜过程中的快速剪枝，避免遍历整棵树。

每个内部节点还需维护其与父节点 $P(O_r)$ 之间的距离（同样用于后续查搜时的快速剪枝），具体维护的信息如下所示：

与内部节点不同的是，每个叶节点无需维护其覆盖半径，并且该节点直接指向具体的数据点，具体维护的信息如下所示：

需要注意的是，所有的数据点都会出现在叶节点中，内部节点中的路由对象为一些 “关键” 数据点的拷贝。

---

M-Tree 查搜

近邻查搜通常分为两种，一种是 Range Queries，即对于待查询数据 $Q$，查找所有满足 $d(O_j,Q)\le r(Q)$ 的数据 $O_j$；另一种是 Nearest Neighbor Queries，即查找距查询数据 $Q$ 最近的前 $k$ 个数据点。

首先介绍 Range Queries，其查搜时有两种剪枝方式。假设当前查询节点为 $O_r$，其与查询点 $Q$ 之间的距离为 $d(O_r,Q)$，则 $O_r$ 子树内任意点 $O^{\prime }$ 满足（距离三角不等式）：
$$d(O^{\prime },Q)\ge d(O_r,Q)-d(O^{\prime },O_r)\ge d(O_r,Q)-r(O_r).$$

因此如果 $O_r$ 满足 $d(O_r,Q)>r(Q)+r(O_r)$，即 $d(O^{\prime },Q)>r(Q)$，则无需再遍历 $O_r$ 子树内的节点，此为第一种剪枝方式。

此外，假设 $O_r$ 的父节点为 $O_p$，其距 $Q$ 的距离为 $d(O_p,Q)$，则 $O_r$ 子树内任意点 $O^{\prime }$ 满足（距离三角不等式）：
$$d(O^{\prime },Q)\ge d(O_r,Q)-r(O_r)\ge |d(O_r,Q_p)-d(O_p,Q)|-r(O_r).$$

因此如果 $O_r$ 满足 $|d(O_r,Q_p)-d(O_p,Q)|>r(Q)+r(O_r)$，则可以直接将整颗 $O_r$ 子树剪枝，并且无需计算 $d(O_r,Q)$，此为第二种剪枝。

以下为 M-Tree 执行 Range Queries 的具体算法：

接下来是 Nearest Neighbor Queries，其剪枝思路与 Range Queries 类似，只是将查询范围 $r(Q)$ 换成了 $d_k$，即当前距 $Q$ 第 $k$ 小的距离。另外 d m i n ( T ( O r ) ) = max ⁡ { d ( O r , Q ) − r ( O r ) , 0 } , d m a x ( T ( O r ) ) = d ( O r , Q ) + r ( O r ) d_{min}(T(O_r))=\max\{d(O_r,Q)-r(O_r),0\},d_{max}(T(O_r))=d(O_r,Q)+r(O_r) dmin​(T(Or​))=max{d(Or​,Q)−r(Or​),0},dmax​(T(Or​))=d(Or​,Q)+r(Or​) 分别代表 $O_r$ 子树中距 $Q$ 可能的最小和最大距离，执行 Nearest Neighbor Queries 的具体算法如下所示：

---

M-Tree 构建

M-Tree 的构建为依次插入新的数据点，其中每个叶节点可以存储多个数据点，如果叶节点满了，则会进行节点分裂，进而动态地维护整颗树结构。

M-Tree 数据插入

在每一层插入新数据点时，首先选择不会使内部节点覆盖半径变大的节点，如果不存在这样的节点，则选择使覆盖半径变大幅度最小的节点，具体算法如下所示：

M-Tree 节点分裂

如果最后插入的叶节点满了，则需要进行分裂。具体分裂过程为：

1. 从当前节点 N 的所有数据点 + 新数据点 $O_n$ 中选出两个代表节点 $O_{p_1}$ 和 $O_{p_2}$，对应 Promote 操作；
2. 将这些数据点集合 $\mathcal{N}$ 分为距 $O_{p_1}$ 更近的 ${\mathcal{N}}_1$ 和距 $O_{p_2}$ 更近的 ${\mathcal{N}}_2$，对于 Partition 操作；
3. 将 N 中的路由节点替换为 $O_{p_1}$，并判断 N 的上层节点是否满了，如果没满则插入 $O_{p_2}$，否则继续向上进行分裂。

整体算法如下所示：

节点分裂之后，仍需维护新增节点的覆盖半径，具体如下：
r ( O p 1 ) = max ⁡ { d ( O r , O p 1 ) + r ( O r ) ∣ O r ∈ N 1 } . r\left(O_{p_1}\right)=\max \left\{d\left(O_r, O_{p_1}\right)+r\left(O_r\right) \mid O_r \in \mathcal{N}_1\right\}. r(Op1​​)=max{d(Or​,Op1​​)+r(Or​)∣Or​∈N1​}.

节点分裂策略

两个代表点的选择有多种策略，具体可以查看原文，此处介绍几种代表性策略：

1. m_RAD: 计算 $\mathcal{N}$ 中所有节点两两之间距离，选择最小化 $r(O_{p_1})+r(O_{p_2})$ 的代表点；
2. mM_RAD: 计算 $\mathcal{N}$ 中所有节点两两之间距离，选择最小化 max ⁡ { r ( O p 1 ) , r ( O p 2 ) } \max\{r(O_{p_1}),r(O_{p_2})\} max{r(Op1​​),r(Op2​​)} 的代表点；
3. m_LB_DIST: 将 $O_{p_1}$ 设置为原节点 $O_p$，选择距离 $O_p$ 最远的点作为 $O_{p_2}$.

---

代码实现

• 原作者代码实现 - C++
• Github 其他开源版本 - Python
• Github 其他开源版本 - C++ / Java / Python

---

参考资料

1. VLDB 1994 - Content-based image indexing.
2. VLDB 1997 - M-tree: An Efficient Access Method for Similarity Search in Metric Spaces.
3. ICML 2006 - Cover Trees for Nearest Neighbor.
4. ICML 2015 - Faster Cover Trees
5. TPAMI 2020 - Hierarchical Navigable Small World
6. VLDB 2023 - Similarity search in the blink of an eye with compressed indices