编者的总结：

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

编者的思考：

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

1 Introduction

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

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

相比之下，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，由分裂驱动的。
当一个节点满了，它就要分裂成两个同级的节点以平分这个节点的所有对象。那么对于它的父亲节点，也会增加一个条目表示这两个节点的父亲对象。这里面就涉及了一个问题，如何选择父亲对象，以及选好父亲对象之后，如何平分原有的节点中那些对象。这称之为分裂策略，下一节具体讲。