论文部分内容阅读
[摘 要]基于内容的图像检索是一种典型的相似检索问题，在海量高维的数据集中进行相似匹配，一般认为距离计算费用很高。因此，需要建立有效的索引结构，以减少每个查询中的距离计算次数。为此，针对K最近邻查询（KNN）算法，提出了一种新的高维空间数据索引方法——层次距离索引（Depth Distance Index Structure，DDIS）。详细讨论了这种索引结构的建立与检索等问题，并给出了相应的算法。实验结果显示了这种索引技术的有效性。
[关键词]高维索引结构；相似检索；层次距离索引结构；K最近邻查询
中图分类号：TP391.3 文献标识码：A 文章编号：1009-914X（2013）36-0450-03
0 引言
高维索引结构是基于内容的图像检索（Content-based Image Retrieval，简称CBIR）研究的一个基本问题。常用的高维索引结构包括R-Tree，及其变种R*-Tree、X-Tree，另外还有K-D-B-Tree，TV-Tree，SS-Tree和SR-Tree。这些索引树在维数较低的情况检索效率较好[1]，随着维数的增加它们的检索性能会急剧恶化。为解决上述缺点，随后出现了以降维映射为主的索引方法，包括Hilbert R-Tree，金字塔方法[1]和iDistance方法[2]等，其在高维空间中的检索性能明显优于树型结构。但它们具有以下几个缺点：（1）Hilbert R-Tree难以实现有效的KNN查询。（2）金字塔方法只能处理规则的超矩形查询，不适合KNN查询中常采用的超球形范围查询。（3）在数据集均匀分布的高维空间中，大部分数据点分布在超立方体的表面而非中心[3]，金字塔方法会导致某些页面数据很少或者很多，无疑将造成查询效率的下降。（4）采用多对一的映射方式会给查询过程中引入较多的误中点，增加距离计算次数，影响检索效率。
基于此，本文提出了一种新的基于降维的高维索引方法——层次距离索引（Depth Distance Index Structure，DDIS）。它非常适合KNN查询，能将那些因與查询对象的距离太远而不可能成为候选匹配的对象过滤掉，迅速得到较小的候选匹配集，从而尽可能减少每个查询所需的距离计算次数，提高检索效率；而且它的检索性能不受维度和空间数据分布形式影响。文章第2节详细讨论了DDIS索引结构的建立与检索等问题，并给出了相应的算法。第3节给出一系列的实验比较结果。第4节总结全文思想。
1 层次距离索引结构
1.1 索引结构的形式化定义
一个d维超平面包含（d-1）维超平面，轴为x0， x1， …， xd-1，对应金字塔的序号见表1。金字塔的序号由它的基来确定。假设高维数据空间归一化到边长为1的超立方体中，则两个相对金字塔的底平面均垂直于轴xi，可以用xi=0和xi=1来表示。图1显示了一个3维立方体，其中基x0=0和x0=1分别表示序号0和3，则相关金字塔定义为P0和P3。
定义1（点v的金字塔Pi）。 一个d维点v（坐标表示为v0，…，vd-1）定义位于金字塔Pi内，如果，其中， 。
定义2（点v的索引值keyv）。 任给一个d维点v，Pi是点v所属的金字塔，Oi为该金字塔圆心（即金字塔Pi基平面的质心），则点v的索引值为keyv=i*c+dist（v，Oi）。
其中，dist（v，Oi）为点v和所属金字塔圆心Oi之间的距离；c为扩展数据范围的常量，一般可取的上界。由于i是一个整数，dist（v，Oi）是[0，c]之间的一个实数，因此每个金字塔Pi覆盖的所有点将被映射到[i*c，（i+1）*c]区间中，任何两个金字塔Pi和Pj所覆盖的索引值集是互不相交的。
定义3（点v的深度hv）。 任给一个d维点v，Pi是点v所属的金字塔，点v的深度hv可以表示为hv=0.5-|0.5-vi mod d|。
1.2 索引结构的建立
DDIS索引结构的建立分五步进行。
（1）将d维空间分割成2d个金字塔，P0，P1，…，Pd-1，Pd，Pd+1，…，P2d-1，共享数据空间的中心点（0.5，0.5，…，0.5）作为顶点，（d-1）维超平面作为基。
（2）取每个金字塔基平面的质心为参考圆心，O0，O1，…，Od-1，Od，Od+1，…，O2d-1，即金字塔Pi的参考圆心为Oi。
（3）根据定义1确定数据点v所属金字塔序号为i，计算其与所属金字塔参考圆心Oi的距离，根据定义2确定索引值keyv。
（4）对所有数据点映射后的索引值key进行排序，迅速建立B+树，索引值key从小到大，依次保存在叶节点中。
（5）由于从高维向一维的映射并非一对一，高维空间中位置不同的点可能具有相同的索引值，例如同一金字塔中，与参考圆心距离相等的不同点具有相同的映射值key，因此每个叶节点不但要存储索引值key，还要保存所有具有相同key值的高维数据点，根据定义3确定数据点的深度，并据此由高到低依次存储在叶节点所指向的链表中。
例如图2所描述的2维空间中，包含4个金字塔P0、P1、P2、P3，它们以数据空间的中心点Q为顶点，以空间的一条边为基，参考圆心分别为O0、O1、O2、O3。如图所示，点q0与所属金字塔P0的参考圆心O0的距离为dist（p0，O0），它在该金字塔中的深度为h0。
DDIS索引方法需要以下两种数据结构。
（1）B+树。在我们实际应用中，每个叶节点与左右兄弟叶节点由双向指针相连，便于进行KNN查询时灵活确定检索范围；同时，同一叶节点中，具有相同索引值的高维数据点根据深度，依次存储在该叶节点所指向的链表中。
（2）结构数组。由结构数组保存2d个金字塔的参考圆心，以及它们各自数据空间中距离参考圆心最近的距离和最远的距离（即内、外超球体半径），由此确定各个金字塔中的数据空间。 1.3 KNN查询
设Oi为金字塔Pi的参考圆心，金字塔Pi中分布的数据点与Oi最近的距离为dist_mini，最远的距离为dist_maxi，查询点为q，查询半径为r，如图3所示。我们可以计算得到查询点q在金字塔Pi中的深度为hq，点q距离参考圆心Oi的距离为dist（q，Oi）。若金字塔Pi需要被检索，则DDIS索引结构中的检索范围为：（1）环形范围为[dist（q，Oi）-r，dist（q，Oi）+r]；（2）深度范围为[hq-r，hq+r]。图4给出了一个例子。设O1、O2、O3分别为金字塔P1、P2、P3的参考圆心，对于查询点q1而言，只需要检索金字塔P1；对于查询点q2而言，则需要检索金字塔P2和P3。
在索引结构DDIS中进行KNN查询时的步骤如下。
（1）确定需要检索的金字塔。计算查询点q与金字塔Pi的参考圆心Oi（i=0，1，…，2d-1）之间的距离dist（q，Oi），如果dist（q，Oi）-r≤dist_maxi，则金字塔Pi需要被检索，否则不需要。
（2）对B+树中的叶节点进行剪枝。如果金字塔Pi（0≤i≤2d-1）需要被检索，则计算金字塔Pi中的环形距离查询范围为： 。若金字塔Pi包含叶节点Ni0，Ni1，…，Nit，只要叶节点Nij（j=0，1，…，t）的索引值key不属于范围Ri1，我们就可以将Nij包含的所有对象从q的候选匹配集中去除掉。同理，可依次确定B+树中其它实际需要检索的叶节点，对范围外的进行剪枝。
（3）对叶节点中的候选对象进行过滤。如果叶节点Nij（0≤i≤2d-1，0≤j≤t）需要被检索，且查询点q在金字塔Pi中的深度为hq，则计算金字塔Pi中的层次深度查询范围为：。由此，我们就可以将叶节点Nij中包含的不属于范围Ri2的所有对象，从q的候选匹配集中去除掉。
（4）顺序扫描候选匹配集返回查询结果。经过以上两步的过滤后，对候选匹配集中的对象可采用顺序扫描方法，逐个计算与例子图像q的距离，并将距离最近的前k个对象放入返回给用户，查询结束。
采用这种检索算法，只需进行2d+u次距离计算（u为过滤后候选匹配集中对象的个数）和O（d）次简单运算。不难看出，只要满足2d+u≤n，就可以节省大量的距离计算费用，从而显著的提高相似检索的效率。
2 实验结果与讨论
2.1 实验描述
实验环境是奔腾IV 1.5G Hz CPU，256M内存，IBM 40G硬盤，Windows2000操作系统，使用Visual C++ 6.0进行算法实现。实验中，我们使用B+树作为金字塔方法、iDistance方法和DDIS方法的一维索引存储结构，并由计算机随机产生了8个均匀分布的模拟数据集DS1，DS2，DS3，DS4，DS5，DS6，DS7，DS8，维度分别为3d，8d，16d和30d，大小均为100 000。
2.2 DDIS的检索效率
实验中，我们首先选取三个数据集，数据集DS1包含100 000个均匀分布的8维向量，数据集DS2包含100 000个均匀分布的16维向量，数据集DS3包含100 000个均匀分布的30维向量。
图5（a）（b）分别给出了当KNN查询中k=10时，数据集DS1、DS2和DS3上顺序扫描算法和DDIS方法的检索性能比较（分别从“平均页面访问次数”和“平均CPU时间”两方面进行对比，且由于我们实现的是内存索引结构，所以这里并不考虑磁盘的I/O操作），查询半径r的最大值为0.5。对每个确定的查询半径，我们均随机选择50个查询数据点，计算这50个查询消耗的平均页面访问次数和平均CPU时间，以其作为性能评定指标。实验结果表明，在不同的维度下，DDIS的检索性能明显优于线性检索，特别是对于维度较高的数据集尤为如此。
2.3 性能对比分析实验
在性能对比分析实验中，我们将DDIS方法与金字塔方法和iDistance方法的检索性能进行了比较和分析。我们采用数据集DS4，包含100 000个均匀分布的30维向量，KNN查询中k=10。我们均随机选择100个查询数据点，计算这100个查询消耗的平均页面访问次数，并据此来比较各种方法的检索性能。查询结果的精确度使用KNN查询半径r（0≤r≤1）来调节，r越小精确度越低，r越大精确度越高。图6（a）（b）分别给出了数据集DS4上DDIS方法与金字塔方法、iDistance方法的检索性能比较。实验结果表明，DDIS的检索性能最好，顺序扫描的检索性能最差。且随着查询精确度的提高，三种索引结构：DDIS、金字塔和iDistance的平均页面访问次数随之增加，但它们的检索性能仍优于顺序扫描。
3 结束语
本文提出了一种新的适合KNN查询的高维索引方法——层次距离索引结构。它将均匀分布的高维数据空间划分成多个金字塔，然后按照一定的方式映射到低维，采用B+树存储索引关键字。实验结果表明，DDIS方法具有优良的检索性能，它的执行效率优于金字塔方法、iDistance方法和顺序扫描方法。DDIS还不受数据分布形式的限制，对于非均匀分布的数据空间，只需先将数据进行聚类，然后对每类使用DDIS建立索引，原理是相同的，对其的实验研究是我们进一步的工作目标。
参考文献（References）
[1] Berchtold S.，Bohm C.，Kriegel H. P.The pyramid-technique： towards indexing beyond the curse of dimensionality[C]. In： Proceedings of the ACM SIGMOD International Conference on Management of Data. Seattle， NJ，1998. 142～153.
[2] Cui Yu， Beng Chin Ooi， Kian Lee Tan， H. V.Jagadish. Indexing the distance： an efficient method to KNN processing[C]. In： PMG Apers， P Atzeni， S Ceri， et al eds. Proceedings of the 27th International Conference on Very Large Data Bases. San Francisco， CA： Morgan Kaufmann， 2001. 421～430.
[3] Jiyuan An， Yi Ping Phoebe Chen， Qinying Xu，Xiaofang Zhou.A new indexing method for high dimensional dataset[C].DASFAA 2005.385～397.
作者简介
陈军（1977-），男，湖北黄冈，工程师
万鸿雁（1970-），男，湖北黄冈，工程师
[关键词]高维索引结构；相似检索；层次距离索引结构；K最近邻查询
中图分类号：TP391.3 文献标识码：A 文章编号：1009-914X（2013）36-0450-03
0 引言
高维索引结构是基于内容的图像检索（Content-based Image Retrieval，简称CBIR）研究的一个基本问题。常用的高维索引结构包括R-Tree，及其变种R*-Tree、X-Tree，另外还有K-D-B-Tree，TV-Tree，SS-Tree和SR-Tree。这些索引树在维数较低的情况检索效率较好[1]，随着维数的增加它们的检索性能会急剧恶化。为解决上述缺点，随后出现了以降维映射为主的索引方法，包括Hilbert R-Tree，金字塔方法[1]和iDistance方法[2]等，其在高维空间中的检索性能明显优于树型结构。但它们具有以下几个缺点：（1）Hilbert R-Tree难以实现有效的KNN查询。（2）金字塔方法只能处理规则的超矩形查询，不适合KNN查询中常采用的超球形范围查询。（3）在数据集均匀分布的高维空间中，大部分数据点分布在超立方体的表面而非中心[3]，金字塔方法会导致某些页面数据很少或者很多，无疑将造成查询效率的下降。（4）采用多对一的映射方式会给查询过程中引入较多的误中点，增加距离计算次数，影响检索效率。
基于此，本文提出了一种新的基于降维的高维索引方法——层次距离索引（Depth Distance Index Structure，DDIS）。它非常适合KNN查询，能将那些因與查询对象的距离太远而不可能成为候选匹配的对象过滤掉，迅速得到较小的候选匹配集，从而尽可能减少每个查询所需的距离计算次数，提高检索效率；而且它的检索性能不受维度和空间数据分布形式影响。文章第2节详细讨论了DDIS索引结构的建立与检索等问题，并给出了相应的算法。第3节给出一系列的实验比较结果。第4节总结全文思想。
1 层次距离索引结构
1.1 索引结构的形式化定义
一个d维超平面包含（d-1）维超平面，轴为x0， x1， …， xd-1，对应金字塔的序号见表1。金字塔的序号由它的基来确定。假设高维数据空间归一化到边长为1的超立方体中，则两个相对金字塔的底平面均垂直于轴xi，可以用xi=0和xi=1来表示。图1显示了一个3维立方体，其中基x0=0和x0=1分别表示序号0和3，则相关金字塔定义为P0和P3。
定义1（点v的金字塔Pi）。 一个d维点v（坐标表示为v0，…，vd-1）定义位于金字塔Pi内，如果，其中， 。
定义2（点v的索引值keyv）。 任给一个d维点v，Pi是点v所属的金字塔，Oi为该金字塔圆心（即金字塔Pi基平面的质心），则点v的索引值为keyv=i*c+dist（v，Oi）。
其中，dist（v，Oi）为点v和所属金字塔圆心Oi之间的距离；c为扩展数据范围的常量，一般可取的上界。由于i是一个整数，dist（v，Oi）是[0，c]之间的一个实数，因此每个金字塔Pi覆盖的所有点将被映射到[i*c，（i+1）*c]区间中，任何两个金字塔Pi和Pj所覆盖的索引值集是互不相交的。
定义3（点v的深度hv）。 任给一个d维点v，Pi是点v所属的金字塔，点v的深度hv可以表示为hv=0.5-|0.5-vi mod d|。
1.2 索引结构的建立
DDIS索引结构的建立分五步进行。
（1）将d维空间分割成2d个金字塔，P0，P1，…，Pd-1，Pd，Pd+1，…，P2d-1，共享数据空间的中心点（0.5，0.5，…，0.5）作为顶点，（d-1）维超平面作为基。
（2）取每个金字塔基平面的质心为参考圆心，O0，O1，…，Od-1，Od，Od+1，…，O2d-1，即金字塔Pi的参考圆心为Oi。
（3）根据定义1确定数据点v所属金字塔序号为i，计算其与所属金字塔参考圆心Oi的距离，根据定义2确定索引值keyv。
（4）对所有数据点映射后的索引值key进行排序，迅速建立B+树，索引值key从小到大，依次保存在叶节点中。
（5）由于从高维向一维的映射并非一对一，高维空间中位置不同的点可能具有相同的索引值，例如同一金字塔中，与参考圆心距离相等的不同点具有相同的映射值key，因此每个叶节点不但要存储索引值key，还要保存所有具有相同key值的高维数据点，根据定义3确定数据点的深度，并据此由高到低依次存储在叶节点所指向的链表中。
例如图2所描述的2维空间中，包含4个金字塔P0、P1、P2、P3，它们以数据空间的中心点Q为顶点，以空间的一条边为基，参考圆心分别为O0、O1、O2、O3。如图所示，点q0与所属金字塔P0的参考圆心O0的距离为dist（p0，O0），它在该金字塔中的深度为h0。
DDIS索引方法需要以下两种数据结构。
（1）B+树。在我们实际应用中，每个叶节点与左右兄弟叶节点由双向指针相连，便于进行KNN查询时灵活确定检索范围；同时，同一叶节点中，具有相同索引值的高维数据点根据深度，依次存储在该叶节点所指向的链表中。
（2）结构数组。由结构数组保存2d个金字塔的参考圆心，以及它们各自数据空间中距离参考圆心最近的距离和最远的距离（即内、外超球体半径），由此确定各个金字塔中的数据空间。 1.3 KNN查询
设Oi为金字塔Pi的参考圆心，金字塔Pi中分布的数据点与Oi最近的距离为dist_mini，最远的距离为dist_maxi，查询点为q，查询半径为r，如图3所示。我们可以计算得到查询点q在金字塔Pi中的深度为hq，点q距离参考圆心Oi的距离为dist（q，Oi）。若金字塔Pi需要被检索，则DDIS索引结构中的检索范围为：（1）环形范围为[dist（q，Oi）-r，dist（q，Oi）+r]；（2）深度范围为[hq-r，hq+r]。图4给出了一个例子。设O1、O2、O3分别为金字塔P1、P2、P3的参考圆心，对于查询点q1而言，只需要检索金字塔P1；对于查询点q2而言，则需要检索金字塔P2和P3。
在索引结构DDIS中进行KNN查询时的步骤如下。
（1）确定需要检索的金字塔。计算查询点q与金字塔Pi的参考圆心Oi（i=0，1，…，2d-1）之间的距离dist（q，Oi），如果dist（q，Oi）-r≤dist_maxi，则金字塔Pi需要被检索，否则不需要。
（2）对B+树中的叶节点进行剪枝。如果金字塔Pi（0≤i≤2d-1）需要被检索，则计算金字塔Pi中的环形距离查询范围为： 。若金字塔Pi包含叶节点Ni0，Ni1，…，Nit，只要叶节点Nij（j=0，1，…，t）的索引值key不属于范围Ri1，我们就可以将Nij包含的所有对象从q的候选匹配集中去除掉。同理，可依次确定B+树中其它实际需要检索的叶节点，对范围外的进行剪枝。
（3）对叶节点中的候选对象进行过滤。如果叶节点Nij（0≤i≤2d-1，0≤j≤t）需要被检索，且查询点q在金字塔Pi中的深度为hq，则计算金字塔Pi中的层次深度查询范围为：。由此，我们就可以将叶节点Nij中包含的不属于范围Ri2的所有对象，从q的候选匹配集中去除掉。
（4）顺序扫描候选匹配集返回查询结果。经过以上两步的过滤后，对候选匹配集中的对象可采用顺序扫描方法，逐个计算与例子图像q的距离，并将距离最近的前k个对象放入返回给用户，查询结束。
采用这种检索算法，只需进行2d+u次距离计算（u为过滤后候选匹配集中对象的个数）和O（d）次简单运算。不难看出，只要满足2d+u≤n，就可以节省大量的距离计算费用，从而显著的提高相似检索的效率。
2 实验结果与讨论
2.1 实验描述
实验环境是奔腾IV 1.5G Hz CPU，256M内存，IBM 40G硬盤，Windows2000操作系统，使用Visual C++ 6.0进行算法实现。实验中，我们使用B+树作为金字塔方法、iDistance方法和DDIS方法的一维索引存储结构，并由计算机随机产生了8个均匀分布的模拟数据集DS1，DS2，DS3，DS4，DS5，DS6，DS7，DS8，维度分别为3d，8d，16d和30d，大小均为100 000。
2.2 DDIS的检索效率
实验中，我们首先选取三个数据集，数据集DS1包含100 000个均匀分布的8维向量，数据集DS2包含100 000个均匀分布的16维向量，数据集DS3包含100 000个均匀分布的30维向量。
图5（a）（b）分别给出了当KNN查询中k=10时，数据集DS1、DS2和DS3上顺序扫描算法和DDIS方法的检索性能比较（分别从“平均页面访问次数”和“平均CPU时间”两方面进行对比，且由于我们实现的是内存索引结构，所以这里并不考虑磁盘的I/O操作），查询半径r的最大值为0.5。对每个确定的查询半径，我们均随机选择50个查询数据点，计算这50个查询消耗的平均页面访问次数和平均CPU时间，以其作为性能评定指标。实验结果表明，在不同的维度下，DDIS的检索性能明显优于线性检索，特别是对于维度较高的数据集尤为如此。
2.3 性能对比分析实验
在性能对比分析实验中，我们将DDIS方法与金字塔方法和iDistance方法的检索性能进行了比较和分析。我们采用数据集DS4，包含100 000个均匀分布的30维向量，KNN查询中k=10。我们均随机选择100个查询数据点，计算这100个查询消耗的平均页面访问次数，并据此来比较各种方法的检索性能。查询结果的精确度使用KNN查询半径r（0≤r≤1）来调节，r越小精确度越低，r越大精确度越高。图6（a）（b）分别给出了数据集DS4上DDIS方法与金字塔方法、iDistance方法的检索性能比较。实验结果表明，DDIS的检索性能最好，顺序扫描的检索性能最差。且随着查询精确度的提高，三种索引结构：DDIS、金字塔和iDistance的平均页面访问次数随之增加，但它们的检索性能仍优于顺序扫描。
3 结束语
本文提出了一种新的适合KNN查询的高维索引方法——层次距离索引结构。它将均匀分布的高维数据空间划分成多个金字塔，然后按照一定的方式映射到低维，采用B+树存储索引关键字。实验结果表明，DDIS方法具有优良的检索性能，它的执行效率优于金字塔方法、iDistance方法和顺序扫描方法。DDIS还不受数据分布形式的限制，对于非均匀分布的数据空间，只需先将数据进行聚类，然后对每类使用DDIS建立索引，原理是相同的，对其的实验研究是我们进一步的工作目标。
参考文献（References）
[1] Berchtold S.，Bohm C.，Kriegel H. P.The pyramid-technique： towards indexing beyond the curse of dimensionality[C]. In： Proceedings of the ACM SIGMOD International Conference on Management of Data. Seattle， NJ，1998. 142～153.
[2] Cui Yu， Beng Chin Ooi， Kian Lee Tan， H. V.Jagadish. Indexing the distance： an efficient method to KNN processing[C]. In： PMG Apers， P Atzeni， S Ceri， et al eds. Proceedings of the 27th International Conference on Very Large Data Bases. San Francisco， CA： Morgan Kaufmann， 2001. 421～430.
[3] Jiyuan An， Yi Ping Phoebe Chen， Qinying Xu，Xiaofang Zhou.A new indexing method for high dimensional dataset[C].DASFAA 2005.385～397.
作者简介
陈军（1977-），男，湖北黄冈，工程师
万鸿雁（1970-），男，湖北黄冈，工程师