标题：M-tree：度量空间里高效的相似性查找访问方法

编者的总结：

1. 本文的M-Tree是在度量空间中的索引，在剪枝方法上，和R树非常相似，都是大范围套小范围逐层剪枝；但是在结构上，和B树是很相似的，中间节点每一项都是一个特殊的参考对象，它指向一个下层节点，范围覆盖这个下层节点的所有对象。
2. 查询剪枝上，利用的是三角不等式，逐层剪枝掉不可能相交的范围。
3. 索引构建上，需要Top-down Insertion，但是索引的增长是Botton-Up式的分裂增长，和B树一致。
4. 分裂时的父对象（参考对象）选择和分布方式，可以极大地影响M-Tree的剪枝效果。

编者的思考：

1. Bulk-Loading方法缺乏，索引构建速度堪忧，也许可以考虑通过聚类算法首先找到合适的几个cluster作为初始化。

1 Introduction

度量空间，主要应用在各种多媒体数据，各种灵活的距离定义上。
已经有的是多维空间数据访问模式，比如R-Tree，但是仍有局限性：

1. 必须是向量空间；
2. 距离定义必须是范数式的。不能有不同维度之间的交差，也就是说，只有对应维度的差及其变形才可以贡献距离，不同维度的差不能贡献距离。

相比之下，Metric Tree就没有这两点限制。没有坐标系的概念，没有绝对坐标，只有相对距离。之前提出的Metric trees都是静态的，本文提一个动态的，不需要周期性重组的；基于磁盘页的，同时考虑CPU和I/O的一个度量索引，称为M-Tree。

2 Preliminaries

度量空间的定义
range query/ KNN
related work:

• FastMap：静态数据集，近似方法
• VP-Tree/MVP-Tree：树型分区，自顶向下非动态
• GNAT：二聚类式分区，自顶向下非动态

3 The M-tree

M-Tree是根据相对距离进行分区的，对象会被放进固定大小的节点里，这个节点就表示度量空间中的一个有限区域。

3.1 The Structure of M-tree Nodes

M-Tree的节点分为两类，一类是叶子节点，一类是中间路由节点。叶子节点索引具体的数据对象，中间节点索引路由对象。
每一个节点都有一个父亲对象，父亲对象对应的覆盖树的范围会包含其所有子节点覆盖树的范围。（一个大圆里面有若干个小圆）
下图是路由对象包含的具体几项信息：

• Or：路由对象也是一个数据对象，也有具体的值；
• ptr(T(Or))：覆盖树的根节点指针。覆盖树是指所有和Or距离不大于r(Or)对象的集合。
• r(Or)

• d(Or,P(Or))：Or和Or父亲对象的距离。

  
  image.png
  

  数据对象包含以下几项信息：

• Oj：该数据对象的值；
• oid：该数据对象id，用于在索引文件中查找；

• d(Oj,P(Oj))：该数据对象和父亲对象的距离。

  
  image.png

3.2 Processing Similarity Queries

处理查询的核心在剪枝上，怎样尽可能多地剪枝掉不可能出现结果的区域，也就是怎样减少访问的节点，怎样减少距离的计算（高代价操作）。
具体在实现上，是要利用度量空间中的三角不等式（父亲对象Op，Query对象Q，当前对象Or/Oj）进行剪枝。

image.png

3.2.1 Range Queries

从根节点开始自上而下，按照DFS的顺序搜索这棵树。分两种情况：

• 对于叶子节点，将每一项先利用三角不等式试图剪枝，失败就具体计算；

• 对于中间节点，考虑到Or的覆盖树中的数据对象和Or的距离不超过r(Or)，因而在三角不等式中引入r(Or)，放宽约束。

  
  image.png

3.2.2 Nearest Neighbor Queries

KNN查询利用优先级队列pq和BSF(kd)来进行剪枝。
pq的优先级排列标准是距离下界，也就是d(Or,Q) - r。这个是中间对象Or的覆盖树中的节点和Query的最小距离。
然后同样从根节点开始遍历M-Tree，还是分两种情况：

• 对于叶子节点，将每一项尝试剪枝，失败则计算距离，然后更新KNN；

• 对于中间节点，将每一项首先试图按下界和BSF剪枝，剪枝不成就加入pq；另外如果上界距离比BSF还要小，那么按匿名对象更新BSF。

  
  image.png

3.3 Building the M-tree

M-Tree的构建是Top-down Insertion的方式。秉持着尽量不增加Or，增加的话也要增加最少的原则进行逐个插入。

8c25279f1d19694513e13c8ad101f83.png

3.4 Split Management

插入可能导致叶子节点溢出，本节讲溢出分裂的问题。
插入虽然是Top-down Insertion的，但是M-Tree的增长是Bottom-Up，由分裂驱动的。
当一个节点满了，它就要分裂成两个同级的节点以平分这个节点的所有对象。那么对于它的父亲节点，也会增加一个条目表示这两个节点的父亲对象。这里面就涉及了一个问题，如何选择父亲对象，以及选好父亲对象之后，如何平分原有的节点中那些对象。这称之为分裂策略，下一节具体讲。

image.png

但是有一个点，无论何种分裂策略，这个父亲对象的r(Or)在分裂之后是确定的。
对于分裂节点是叶子节点：

image.png
对于分裂节点时中间节点：
image.png

4 Split Policies

先说目标，理想的分裂策略是让分裂出来的两个Region整体面积较小，overlap的部分也比较小。理由是这样的region是更紧凑的，那些没有数据对象的空间是尽量不会被覆盖到的；overlap部分较小是避免这部分query查询时候要多走一条路。

4.1 Choosing the Routing Objects

作者列举了几种分裂策略：

• m_RAD：尝试所有对象对的组合，选出r(Or1) + r(Or2)最小的那一对；
• mM_RAD: 尝试所有对象对的组合，选出max{r(Or1), r(Or2)}最小的那一对；
• M_LB_DIST：一个从之前的父亲对象继承下来，另一个选和这个父亲对象最远的那个对象；
• RANDOM：随机选两个；
• SAMPLING：抽一组样，在这组样里面用mM_RAD方法选择。

4.2 Distribution of the Entries

选好了父亲对象，接下来是如何将分裂节点的对象分区到两个父亲对象下面。作者也列举了几种策略：

• Generalized Hyperplane：对于每个对象，找离的近的父亲对象做父亲；
• Balanced：按照和父亲对象的距离，一人分一半。每一轮，每个父亲选择离自己最近的对象，直到所有对象被选完。