标题：相似性查找的高效度量索引
本文作者来自浙江大学

编者的总结

1. 本文达成的目的是度量空间（仅定义域和距离，距离满足三角不等式）上的相似性查找，包括KNN和range query，都是精确的。
2. 方法上，分两步走。第一步选取部分pivots点，通过和这些pivots的距离引入到向量空间中。再将这些向量空间中的点通过空间填充曲线排成全序。最后利用B+树的形式和R树的剪枝思想完成存储和查询。
3. 在同等的问题背景下，在文章发表年份2014年，这份工作的实验效果是远超其他方法的。

编者的思考

1. 对于空间填充曲线，比如希尔伯特曲线，如何衡量他在本文中的应用的紧密型。数据集中近似的数据是否真的都存在附近的区域中，这一点没有实验表明。只看到希尔伯特曲线比z型曲线要好。
2. 没有看到近似答案的效果如何。比如数据规模超大（超过1M个对象），精确计算没必要的情况，本方法的效率如何，效果如何？

Abstract

本文解决在度量空间中，进行相似性查找的问题。核心难点在于多种多样的数据类型和相似度量标准上。
本文提出SPB-Tree(Space-filling curve and Pivot-based B+-tree)解决方案：

1. 基于称为pivot的小集合，减少距离计算；
2. 基于空间填充曲线，聚集组织数据，提高存储效率；
3. 底层使用B+树以及MBB(minimum bounding box)作为索引。

本文的设计很容易集成到现有的DBMS上。

I. INTRODUCTION

这里的度量空间不特指某种数据类型和相似性度量方式，只要度量满足三角不等式即可。比如向量的cos夹角，字符串的编辑距离。
对于度量空间上的相似访问，主要有两派方法。一派是搞分区，把全空间分成一些紧密的分区，查询时剪枝掉不可能的分区；另一派是基于pivot，主要是利用三角不等式的下界性进行裁剪。具体来说，给定两个点q,o, 根据三角不等式，一定有，p是一个pivot。因此产生一个下界性，可以用于剪枝。
对于这两派方法，基于pivot的距离计算数量少，但是首先需要大量空间保存预计算的距离，而且会带来较多的随机I/O，因为数据不能好的聚集存储。反之，基于pivot方法的缺点正是分区方法的优点。

作者的方法，就是要结合两派方法的优势。挑战有以下3个：

1. 如何支持高效检索。其实就是减少I/O和减少距离计算次数（CPU）。作者的方法是基于非常小而高效的一个pivot集，同时用一个空间填充曲线聚集数据。
2. 如何尽量减少索引构建、存储、维护代价。作者的方法是用空间填充曲线对预计算的距离数据降维，然后存进B+树。
3. 如何高效管理大量负责对象（DNA，图像等）。作者的方法是索引和数据分开存，非物化的方式，保证索引效率。数据放进独立的随机访问文件（RAF）中，索引对数据的MBB构建。

III. PROBLEM FORMULATION

度量空间由(M,d)构成，M是对象的域，d是距离函数。
d满足，对称性（a,b与b,a距离相同），非负性，唯一性（距离为0的只有自己），三角不等是。

查询有两种，range query和knn。

本征维数由

image.png

IV. THE SPB-TREE

A. Construction Framework

正如图1中所示，索引构建分三步走。
第一步：用一些精心挑选的pivots，把对象映射到向量空间去。因为向量空间才可以用几何方法，坐标系等概念。
第二步：用空间填充曲线把向量空间中的点映射到单维空间中的整数。
第三步：用B+树索引这些整数的MBB。也因此，数据的bulk-loading，增删操作都依赖于B+树。

image.png

• Pivot Mapping
  这一步是在度量数据集上选择一组点，作为pivots，对于原数据集某一个点，依次和每一个pivot计算距离，得到的一个距离向量，就是向量空间中的坐标。如下图。也就是说，pivot的个数，就是向量空间的维数。
  

  image.png
  
  对于向量空间中的距离计算，采用的是范数，也就是取各个维度差的绝对值的最大值，因为三角不等式，所以无论哪个维度（即哪个pivot），其距离都不会超过两个对象原本在度量空间中的距离。因此，度量空间中的距离是向量空间中距离的下界。随着pivot数量选的越来越多，这个下界会越来越紧（可能不变）。

• Space-Filling Curve Mapping
  空间填充曲线可以将多维数据点降成一维全序的。
  但是这也有条件，多维数据点必须是离散的整数。而很多度量空间的距离不是整数，而是连续的实数，此时怎么办？
  作者的方式是-近似。即给定一个参数，所有距离都除以然后向下取整，得到离散整数距离。举个例子，如果，那么这个近似就是向下取整。
  参数很关键。取的太小，整个向量空间范围太大，太稀疏，搜索空间就会很大；去的太大，很多点就分不开了，会在向量空间的一个格子里碰撞，最后增大距离计算量。
  

  image.png

B. Pivot Selection

对于Pivots如何选取，首先给出一个衡量Pivots质量的公式。
OP是一个给出的一组对象对集合，就用这个对pivots的质量做度量，衡量下界的紧密型。这个precision越接近1越好。

image.png

具体选取多少个pivots呢，由本征维数给出的，上面给出过公式。这个本征维数是作者直接拿过来用的，之前应该有对其的证明。无论如何，pivots的个数就确定了。
但是即使确定了pivots个数，排列组合所有可能的pivots计算量也是爆炸。考虑到性质良好的pivots通常是数据集中的异常点，所以作者首先用一个HF算法（之前一篇论文里的算法）选取出一组给定数量的异常点，再用贪婪算法选出从这组异常点中逐个选出能使收益最大的点作为pivot，直到选够为止。

image.png

还有一点要注意的是，pivots理论上也未必是数据集上的点，所以之后的插入和删除也无需改变选出来的pivots。

C. Indexing Structure

总体来说，索引结构包含三个部分，pivots表，B+树，RAF。

image.png

RAF按照空间填充曲线的映射值（SFC）来进行单维排序，pivots表不必多说，重点说一下这个改造的B+树。B+树的叶子节点很容易理解，节点里面每一个条目对应着SFC（key）和文件位置指针。有所改造的是中间节点，这些中间节点里的条目不止记录了SFC(key)和下一级节点的指针，还记录了对应叶子节点的MBB，也就是找到叶子节点中所有对象在向量空间中的MBB，记录左下和右上两个顶点的值。

image.png

V. SIMILARITY SEARCH

A. Range Query

假设query的对象为q，查找距离范围r以内的所有点。
首先定理1（必要条件）：如果d(q,o)<r，也就是说在度量空间中距离<r，那么在向量空间中，。这个很好理解，因为向量空间中有距离的下界性，向量空间里距离不足r，度量空间里才有可能距离不足r。

根据这个定理，我们就可以把刚才的B+树当R树用。首先在向量空间中找到q的位置，以r为距离画个方框，称为RR(r)。把B+树从根节点开始进入一个队列。依次出队，如果出队的是中间节点，就遍历它的每一个条目，如果对应的MBB和RR(r)有交集，就放入队列，否则剪枝掉。
如果出队的是叶子节点，我们就要将MBB(N)和RR(r)交集中的数据点，依次带回度量空间中进行计算。

这个距离计算量也是颇大的，我们引入定理2进一步对此进行剪枝。

定理2（充分条件）：对于一个对象o，一个query对象q，如果存在一个pivot ，满足，根据三角不等式，必然有。

因此对于备选的点，我们可以在向量空间中和query点的各个维度加和，如果一个维度不超过r，则不必计算，直接按阳性处理。

对于定理2也无法满足的点，只能硬算距离了。

image.png

B. k Nearest Neighbour Search

kNN相比之下要更tricky一点。
首先给出定理3（必要条件）：如果B+树中间节点的一个entry，即MBB，和query对象点在向量空间中的最小距离，也比当前BSF要大的话，那这个entry可以被剪枝掉。
因此我们的算法通过维护一个最小堆和最小堆中的最大值来计算KNN，堆的排序准则就是向量空间中的最小距离。首先入堆根节点，出堆，如果是中间节点或者叶子节点，然后对每个entry，如果不被定理3剪枝，就入堆；如果是叶子节点的entry，就在度量空间中计算真实距离，更新KNN。如果出堆的节点最小距离已经>KNN中的所有距离了，算法终止。
可以证明的是，这个堆的算法，只会去计算向量空间中这个范围内的点。其他范围的点会因为最小距离太大放到堆的后面，最终被early abondon而不会执行，这个容易理解，不再证明了。可以确定的是，算法的效率是足够的，因为计算的范围其实只有很小一部分（图中灰色方框范围）。

image.png

这种方法也存在问题。问题就是，一个叶子节点中的多个entry会被多次访问入堆，造成随机I/O。K小一些还好，可以用缓存来缓解这个问题。K大一些，缓存也不够了，那就在叶子节点时，如果最小距离合格，算法不会终止，就不再入堆叶子节点的entry，直接把叶子节点的所有entry算一遍，一起更新KNN，这样虽然多算了一些距离，但是避免了大量的随机I/O，整体上效率还是提升了的。

C. Cost Models

根据概率给出了range query，KNN的距离计算次数和I/O次数（包括B+树页面访问和RAF页面访问）

VI. EXPERIMENTAL EVALUATION

A. Effect of Parameters

首先是希尔伯特曲线和z型曲线的PK，各方面比较下来还是希尔伯特曲线比较好。作者给出的原因是连续性，另一方面聚集性也更好一些。

image.png

接下来是Pivots选择的PK。

1. 首先是pivots越多，距离计算越少，这是肯定的，因为下界越来越紧，剪枝越来越多。但是page access和总的查询时间要么恒定，要么不变，说明下界效果基本已经稳定收敛了，更多的pivots只会带来更多的存储代价，而不是收益。这个拐点就在所谓的本征维数。
2. 第二就是本文的HFI方法，比其他pivots选取都要好。原因就是HFI目标导向明确，就为了下界紧密而设计的。
   
   image.png
   
   
   image.png
   
   然后是cache size的抉择。
   cache size越大，页面访问越少，总的query time也在变少，在32页左右收敛，因此cache是必要的。
   
   image.png
   
   正如前文所说，KNN的K太大时，用贪婪算法更好，比如下表中的DNA数据集，页面访问量，贪婪算法少了一大截。
   
   image.png
   
   最后来看看，实数距离公式中，参数的影响：
   比较小时，整个向量空间域都比较稀疏，剪枝会更高效一些，距离计算少，但是页面访问量会增加，query time是比较高的。随着增加，整体时间会逐渐收敛。
   
   image.png

B. Comparisons with Other MAMs

效率对比上来看，本文方法SPB-Tree有绝对优势。

1. 构建速度快，主要是归功于B+树；

2. 存储开销小，主要归功于维度削减和空间填充曲线。

   
   
   image.png
3. 对于页面访问量减少，有两个原因。一个是无论索引还是数据，存储都比较紧密，所以访问较少；另一个，由于索引只存单维的顺序，所以索引变得很小。

4. 对于距离计算少，主要归功于pivot选择的好，下界够紧密。

   
   
   image.png

C. Scalability of the SPB-tree

可扩展性基本上是线性的。

image.png