李焕军

摘 要 本文提出了一种新的同时优化I/O与计算的高维索引技术APMI。该索引技术在判断是否遍历当前区域之前，先判断该查询范围所扩展而成的超立方体是否与当前区域相交，以便减少无效的I/O开销；此外，在遍历每个索引节点数据点之前，通过三角剪枝方法筛除一部分数据点，以很小的计算开销进一步减少了数据访问量，进一步提升了总体效率。在大规模的真实数据集上的性能试验表明，APMI较现有代表性技术有较大性能提升。

【关键词】高维索引 性能优化 kNN检索

1 引言

随着多媒体数字娱乐设备和多媒体传感器设备的普及，图像、音频、视频等多媒体数据己成为人们日常生活中信息的重要来源，著名的IT咨询公司IDG的研究报告表明，视频，音频，图像等多媒体数据已经占到了当前信息数据总量的70%以上。如何对大规模多媒体数据进行有效的组织、分类和检索，从而帮助人们快速的查找到自己感兴趣的信息，已成为研究者们亟需解决的关键问题。其中，高维索引技术作为对大规模多媒体数据的内容进行检索的关键技术和重要手段，其重要性也变得越来越突出，其广阔的应用前景已为人们所公认，因而也成为学术界和产业界的研究热点。

根据索引结构，高维索引技术通常可以划分为三大类：基于划分的高维索引，基于度量（metric）的高维索引和基于近似方法的高维索引。其中，基于划分的高维索引技术可以进一步细分为基于数据划分和基于空间划分的高维索引技术。

在某些情况下，可能不能直接获取多媒体数据对象的特征向量，但是多媒体对象之间的距离关系仍然可以被获取到。基于距离度量（metric）的索引技术就是针对这种情况而提出的一类高维索引技术。其基本原理是：基于某些选择出来的参考点，根据数据对象到参考点之间的距离，将数据区域划分为若干个区域。然后，kNN检索的结果就可以根据给定的查询对象到数据对象以及参考点之间的距离来获得。代表性的索引技术包括M-Tree，MVP-Tree，iDistance等。

第三类常见的高维索引技术就是基于近似技术的索引方法。具体可以分为3类，包括：

（1）基于近似表示的特征向量的高维索引技术，如A-Tree技术；

（2）基于降维和维度转换方法的高维索引技术，如MMDR和DCR等。其中，后三者都是在进行维度转换后将新得到的维度用B+-Tree进行索引，然后在此基础上进行各种检索；

（3）基于Hash的方法，如TreeHB等。

传统的高维索引研究认为，当数据规模较大且维度较高时，I/O开销是最主要的性能瓶颈，因此，高维索引技术的研究者们都着重研发各种减少I/O开销的索引技术和检索方法。然而，已有工作证明[Hike]，对于海量多媒体数据，当多媒体特征向量的维度较高时，计算开销，尤其是各种距离计算开销也是不能忽略的，这些计算开销甚至可能成为高维数据查询处理过程中的重要瓶颈。

针对上述问题，本文提出了一种新的同时优化I/O与计算的高维索引技术APMI，以便提升高维数据检索效率。本文的主要技术工作如下：

（1）优化度量空间的索引结构，为每个叶子结点增加了一个属性，该属性记录该点到数据空间中心的距离；

（2）优化I/O开销：在判断是否遍历当前区域之前，先判断该查询范围所扩展而成的超立方体是否与当前区域相交，以便減少无效的I/O开销；

（3）优化计算开销：在遍历每个索引节点数据点之前，通过三角剪枝方法筛除一部分数据点，以很小的计算开销进一步减少了数据访问量，进一步提升了总体效率。

2 APMI索引的数据存储结构

APMI索引是一种基于度量，同时结合降维技术与聚类技术的高维索引技术，其在数据存储的组织结构上与iDistance等度量空间索引比较相似，在此不再赘述。其核心思想包括三点：

（1）数据空间内每个点的表征可以通过参考点来表示；

（2）根据数据空间内点离参考点的距离组织索引；

（3）索引基于B+-Tree，键值是与空间距离有关的一维数据。基于以上思想，该索引可以通过距离间的度量进行剪枝。

APMI索引在存储结构上相对于传统的度量空间索引技术的优化之处在于：为索引的每个叶子结点增加了一个属性，该属性记录该点到数据空间中心的距离。在进行数据检索时，剪枝算法通过该点到与中心点的距离、该点到参考点的距离、查询半径作为参数，以三角剪枝的达到降低计算开销的目的，进而提高查询效率。

APMI索引结构的一个简单的例子如图1所示。给定三个基于聚类的划分P1、P2、P3，其中心分别为O1、O2和O3，对于查询点q，P1、P2需要遍历，P3不需要。高维查询空间，通过APMI索引转换为一维键值的查询，其阴影部分即为查询空间。

3 基于空间划分策略的I/O开销优化

APMI索引的基于空间划分策略的I/O优化方案的主要技术特性是：在判断是否遍历当前区域之前，先判断该查询范围所扩展而成的超立方体是否与当前区域相交。具体的，在判断查询q与当前分区满足哪类候选剪枝情形之前，先判断q与查询半径r所形成的查询区域与分区是否存在无效I/O开销的可能。其剪枝算法如下：

图2是一个采用I/O优化的剪枝策略的实例。其中左图中给定了查询点q，查询半径r，且q包含于P3。同时，q与P2满足条件dist（O2，q）-r ≤ dist_max2。其中不过，q与r所形成的超球，与P2中O2所形成的超半球，其相交的这个分区页，只包含O2所在金字塔顶端的几个数据点。超过金字塔范围所形成的超半球，即使与q的查询范围相交，但由于这个区域本身不存在属于P2的任何数据点，所以查询相交的这个页面，对于整个查询过程来说，是无效的I/O开销。

图2的右图是采用了本文提出的面向I/O优化的剪枝策略的检索实例。其将图2左图中q与r所形成的圆扩展成正方形。不难看出正方形与P2不存在交叉，即满足PP算法中的剪枝情况，不必对原本需要查询的page进行查询，减少了一部分I/O的开销。

4 计算开销优化策略

对于基于度量空间的高维索引，存在一个普遍的问题，即所形成的超球体积会很大。如图3的左图所示：对于当前查询q与查询半径r所形成的查询区域，对于P2而言，可双向遍历到达；对于与P3而言，可向内遍历到达。不难发现，因超球的体积很大，其包含的数据点分布也非常散乱。其需要遍历的三个页面中的很多数据点，浪费了大部分的计算开销。

为解决此问题，本文提出一种基于三角不等式剪枝的算法：在遍历每个page中数据点之前，通过三角剪枝的方法筛除一部分数据点。该方案为每个叶子结点增加了一个属性，该属性记录该点到数据空间中心的距离。剪枝算法通过该点到与中心点的距离、该点到参考点的距离、查询半径作为参数，以三角剪枝的达到降低计算开销的目的，进而提高查询效率（如图2的右图所示）。

具体的，将为全部数据点增加一个属性字段（包括查询点q），记录该点到数据空间中心center的距离。假定采用欧氏距离作为度量标准，p为数据空间内某个与查询区域相交的索引节点页面中的数据点，则存在以下三角不等式规则，可作为剪枝依据：

dist（p，q）-dist（q，center） ≤ dist（p，center） ≤ dist（q，center） + dist（q，center）

当规定查询点q的查询半径r时，对于q查询半径内的所有候选点p，必须满足：

dist（p，center） ≤ r + dist（q，center）

否则，page内的点将被筛除，从而在仅进行三角剪枝这一计算开销极小的处理的前提下，进一步减少了数据访问量，提升了总体效率。

5 实验结果与分析

5.1 实验环境和设置

在本文的实验中，采用64位操作系统CentOS-6.4，内核版本为3.10.0。内存为16 Gb，处理器为2.4GHz的Intel Xeon E5645，磁盘为300Gb。实验中，将基于MSRA-MM 2.0数据集，将APMI与iDistance这种代表性的高维索引技术进行比较。实验中所用的高维特征向量数据包括128维小波纹理特征和256维RGB特征两种，它们均来自于根据Bing Images图片搜索引擎所收录的实际图片数据，数据总量为100万。其中的100张图片所对应的特征向量被选出来作为查询集。

在实验中，APMI和iDistance的参考点（reference point）的数量均设置为100；在128维和256维度数据的实验中，索引节点的页面大小分别设置为32 KB和64KB。

5.2 实验分析

在实验中，将比较分析数据量对基于APMI和iDistance索引的kNN检索的平均响应时间的影响。数据量的大小范围设置为20万-100万，k设置为100，实验结果如图4和图5所示。

实验结果表明，在查询的平均响应时间上，本文提出的基于APMI的kNN检索在计划所有的实验场景下都取得了最好的效果.唯一的例外是：当维度是256维且数据量小于400K时，基于APMI的kNN查询处理的响应时间略高于iDistance。在绝大部分时候，APMI的效率都要比iDistance好，这主要是由于iDistance将数据空间中的聚簇的中心选为“reference point”，而除此之外，APMI还将索引节点的中心作为某种意义上的“reference point”。因此，APMI在“reference point”的数量上通常会大于iDistance。此外，作为“reference point”的APIM的索引节点的中心通常只是用于代表较小范围内的数据对象，因此，它会使得kNN剪枝过程更为有效和准确。这是APMI在实验中通常更容易比iDistance中取得更好的I/O优化效率，能够节省更多的I/O开销的直接愿意之一。

此外，APMI索引沒有使用传统的计算开销较大的剪枝技术，而是采用了本文提出的计算开销很小的基于三角不等式进行剪枝的策略，在kNN剪枝前就减少了很多不必要的I/O和相应的计算，从而进一步的提升了总体效率，最终获得了更短的查询响应时间。

6 结语

传统的高维索引技术通常只针对I/O开销进行优化，而没有重复考虑到数据维度较高时，计算开销也会成为总体开销的重要组成部分这一情况。针对此问题，本文提出了高维索引技术APMI，通过优化度量空间的索引结构、设计面向I/O优化的剪枝策略、引入具有极低计算开销的三角剪枝方法等技术，从同时优化I/O与计算开销的角度减少数据访问量，提升总体效率。并在大规模真实数据集的基础上，验证了APMI技术的高效性。

参考文献

[1]P.Ciaccia，M.Patella，and P.Zezula. M-tree：An efficient access method for similarity search in metric spaces[C].Proc.VLDB，1997.

[2] T.Bozkaya，Z.?zsoyoglu.Indexing Large Metric Spaces for Similarity Search Queries [J].ACM Trans.Database Syst.1999，24（03）.

[3] H.V.Jagadish，B.Chin Ooi，K.L.Tan，C.Yu，R.Zhang.iDistance：An adaptive B -tree based indexing method for nearest neighbor search[J].ACM Trans.Database Syst.2005，30（02）.

[4] Y.Sakurai，M.Yoshikawa，S.Uemura， H.Kojima.The A-tree：An Index Structure for High-Dimensional Spaces Using Relative Approximation[C]. Proc.VLDB，2000.

[5] H.Shen，X.Zhou，A.Zhou.An adaptive and dynamic dimensionality reduction method for high-dimensional indexing[J].VLDB Journal.2007，16（02）.

[6] Z.Huang，H.Shen，J.Liu，X.Zhou. Effective data co-reduction for multimedia similarity search[C].Proc.SIGMOD，2011.

[7] 林朝晖，于俊清，何云峰，管涛，艾列富.高维分布式局部敏感哈希索引方法[J].计算机科学与探索，2013（09）.

作者单位

贵州航天电器股份有限公司 贵州省贵阳市 550009