基于小世界模型的高维索引算法

桂舒婷，郑 烇，周乐乐，刘 欣，王 嵩

GUI Shuting,ZHENG Quan,ZHOU Lele,LIU Xin,WANG Song

中国科学技术大学 信息科学技术学院 自动化系，合肥230027

School of Information and Technology,University of Science and Technology of China,Heifei 230027,China

1 引言

随着计算机和互联网技术的迅猛发展，人们可以访问到的数据量急剧膨胀，大数据时代已经来临，而如何有效地管理和检索这些海量数据变得至关重要。与此同时，由于检索精度要求的提高而引起查询所依据的特征向量维度的不断变高也给管理及检索带来了一系列的挑战[1]。高维索引（High-dimensional Indexing）作为其中的一项重要技术已成为当今的研究热点。

高维索引技术是研究通过建立索引结构来提高高维数据库检索效率的一门关键技术。作为基于内容检索和模式识别领域的一项关键技术，国内外很多研究机构自20 世纪70 年代便对其进行了研究。它涉及计算几何、数据库技术和模式识别等学科，并且已被推广到GIS，生物信息数据库，遥感光谱数据集等诸多研究领域[2]。在这些领域中，数据的维度普遍较高，且具有高度稀疏性，传统的索引结构如R 树系列[3]、近似向量算法[4]、降维检索和聚类检索等[5]面临严重的“维数灾难”问题。到目前为止，还没有出现一种获得公认并被大量推广运用的算法或解决方案。

本文提出一种新的高维索引算法，称之为逐跳逼近索引。该算法参考社交网络中的六度分隔理论，将高维向量空间建模为小世界模型网络，相似查询过程转换为从随机起始节点到目标相似区域的逐跳逼近，使得仅需访问少量节点即可快速准确地找到目标，从而在处理高维度和海量数据库检索中能达到良好的检索效果。

2 相关知识背景

2.1 主流高维索引技术

自20 世纪70 年代起，国内外研究者对高维索引技术进行了大量研究，主要方法集中在构建良好的索引结构和降低索引维度上。现有的高维索引技术主要分为两大类：树型结构和非树型结构。

基于树型结构的索引是研究最多的高维索引技术，主要分为向量空间和度量空间两大类。在向量空间高维索引中，树型索引结构按照节点的建立方式不同，又可以划分为数据点划分和空间划分。数据点划分的索引结构根据数据分布来分隔空间，其代表性算法有R 树及其变种R+树、R*树、X 树、SS 树及SR 树等[3]。空间划分则是对多维空间进行重复分割，分割成的不相连的子空间中的数据用节点来表示，如K-D 树、K-D-B 树以及四叉树等[6]。度量空间中树型结构也有很多经典算法，如M树及其变种[7]、VP 树及其变种、FQ 树等。除此之外，研究者对一些经典算法进行改进并提出了许多新型索引结构。比如孙劲光提出一种新的索引结构CKDB-Tree，采用一种新的分裂策略，在进行分裂时，引入插入安全点和删除安全点的概念，不仅考虑到将来的数据，而且对已经进行索引的数据也进行考虑[8]。总体来说，树型结构索引在低维度情况下性能优秀，但随着维度的增加，受空间重叠及过度划分影响使得索引性能呈指数性下降，最终甚至劣于顺序查找，产生“维数灾难”现象。

与此同时，许多研究者也对非树型结构进行了许多研究。其中包括不受维度限制且理想情况拥有O(1)时间复杂度的Hash 算法，比如早期的网格文件算法和目前研究较多的位置敏感哈希函数；以及利用降维的思想将高维数据映射到更低维空间，在低维空间继续处理的金字塔技术、一维转换降维、主成分分析降维以及聚类降维[5]等。

2.2 小世界理论及其应用

小世界理论（Small World Theory）由美国哈佛大学社会心理学家Stanley Milgram 在1967 年提出[9]，起初用于描述社会人际网络关系，后来发展运用至生物学、物理学、计算机科学等领域。其理论核心是：尽管现实世界网络节点数量庞大，看似连接松散，但从一个节点只需经过有限的几步跳跃就能到达任意其他节点。小世界理论的提出引发了研究者对网络的进一步描述和建模。

通常情况，网络可以分为两类：规则网络和随机网络[10]。对于规则网络，研究较多的网络模型是最近邻耦合网络（如图1（a）），即每一个节点只是和它周边的左右各k个邻居节点相连。而随机网络中典型模型是由Erodos和Renyi提出的ER 随机网络模型，其中的任意顶点以相同的概率相连。小世界网络是介于规则网络和随机网络的中间过渡形态，兼有两种网络的特性。经典的小世界模型有两种：NW 模型[11]在规则连接模型的基础上以概率p额外添加一批随机连接（如图1（b））；WS模型[12]则在规则连接模型的基础上将部分规则连接以概率p替换为随机连接（如图1（c））。

图1 近邻耦合网络、NW 模型网络和WS 模型网络

由于本文提出的逐跳逼近索引是按NW 模型的方法构造的，下面以NW 模型为主阐述小世界模型中近邻数量、聚集系数、特征路径长度等关键参数的一些特性。网络的近邻为直接与当前节点相连且距离相近的点；聚集系数用来反映节点与其邻居节点间相互连接的程度，其定义为邻居节点间实际存在的边数与最多能存在的边数的比值，即

特征路径长度指的是一个网络中两点之间最短路径长度（或称距离）的平均值，令N为网络中的总节点数，dij定义为连接节点i和j的最短路径上的跳（边）数，则特征路径长度为：

对于NW 模型，其聚集系数为：

两者的特征路径长度可表示为：

其中的f(u)为一普适标度函数，目前只有近似的估计值而还没有精确值的推算结果。

由上述式子容易验证，在p很小而N很大的实际情况中，WS 和NW的参数值极为接近[10]。Kleinberg 在理论上研究了WS 小世界网络的跳跃特性，证明了在简单栅格（Grid）网络模型中，从任何一个节点跳跃到其他任何一个节点，平均跳数存在一个对数级的上界[13]。这给一个很好的启示，即：如果把需要索引的数据看成空间的点（社交网络中的一个用户）所构成的复杂网络，将被检索的节点当成是一个需要在社交网络中找到朋友的用户，从它开始在海量节点网络中逼近跳跃，只需要非常有限的几跳（如2012 年时Facebook 中任意两个用户间平均仅需4.7 跳[14]）就能够到达目标节点，其检索效率仍非常高。

3 逐跳逼近索引算法

逐跳逼近索引是一种自组织的索引结构，仅维护各个局部区域点与点的邻近关系，具有类似于度量空间索引的性质，而未对高维数据空间做任何整体划分。基于逐跳逼近索引的高维向量查询则依靠局部点与点的关联，将查询过程的“关注点”逐步往查询命中区域移动或逼近，最终实现查询。该算法不受维度限制，当库容量增大时，图内部的连接将更加紧密，使得其上的逼近查询结果准确度和效率上升，尤其适用于大规模特征库。图2 为该算法示意图，图中节点0 为起始节点，通过四次跳跃到达了查询节点的相似判定范围内。

图2 逐跳逼近索引算法示意图

3.1 索引结构与生成

逐跳逼近索引首先要将特征数据库建模成一张图，图中的顶点V表示特征数据库中的一个特征向量；边E存在于两个邻近的特征向量，或被以一定概率选中的远程节点间。表1 为实验中逐跳逼近索引数据存储的部分数据示例，其中近邻节点为一定阈值范围内的近邻连接，在索引建立时生成，以距离和编号的二元组形式存储，按距离大小从小到大排列，其中节点间相似性度量的距离定义需根据实际应用场景而定，逐跳逼近索引结构仅维护节点间的距离关系，与具体的距离定义关系不大且具有一定适用面（满足三角不等式关系的连续距离函数大都适用）；而远程节点则为随机远程节点，在运行时动态生成，表中数据仅为示例。

实际上，上述逐跳逼近索引文件所表征的为图的基本信息，即整个索引的目的是构建当前特征库的图表示。而对具体的逐跳逼近索引，可以通过调节三个参数来影响特征库图。参数一是单个节点的最大度数限制，用于统一逐跳逼近索引的形式，便于存储管理。参数二是判定节点邻近的间距阈值，该阈值影响特征库图内部的连通性，减小该值将使特征库图中节点分散连通性变差，增大该值使索引的近邻数增多，索引变大。参数三则是随机远程连接数，该参数将改变在前面的规则图中引入了随机网络特征，能有效降低整个图的特征路径长度。

除表1 外，逐跳逼近索引还有另一个原理相同的改进版，该改进版中近邻节点数为指定固定数值，即每个节点中的近邻为与当前节点最近的若干个节点信息。这样改进之后的索引能够处理小库容量和特征库内数据分布不均匀引起的原始索引连通性较差的情况，所需付出的代价是生成和维护索引的时间将会增加，索引数据如图3 所示。

图3 改进逐跳逼近索引数据示例

3.2 查询算法

逐跳逼近过程分为两个阶段：第一阶段为快速逐跳逼近，目的尽可能快地为第二阶段提供在目标区域内的优质种子集。第二阶段为精确逐跳逼近，目的是找到尽可能多的目标匹配节点。其大致流程如图4 所示。

图4 逐跳逼近索引查询流程图

第一步，从特征库中随机选择若干节点作为初始种子节点，并根据其与目标节点的距离由近到远插入初始种子节点队列。逐跳逼近时，每次选择队首节点作为下一步逐跳逼近步骤的种子节点，读取数据点的逐跳逼近索引，并计算其邻居节点与目标节点间的距离关系，选择部分节点更新初始种子节点队列。

表1 实验逐跳逼近索引局部数据

第二步，循环重复第一步过程，下一步跳跃逼近总是从目前最接近目标的节点开始，直到跳到目标节点的匹配范围之内，并将此范围内的节点作为优质种子插入优质种子节点队列。这里的匹配范围，在范围查询里为范围查询的范围阈值；在近似kNN 查询里是预置范围阈值，该预置阈值由累计检索统计数据计算得出，在每次查询的过程中根据具体情况做适量调整。

第三步，当跳跃已经进入目标数据匹配范围，对优质种子计算其邻居节点与目标节点的距离，记录当前搜索到的匹配节点，同时用其邻居节点更新优质种子节点队列，循环重复该过程。对于范围查询，若不设置提前终止条件，逐跳逼近会进行到优先队列中全部种子节点处理完为止。对于近似kNN 查询，可根据需要设置终止上限数，用来控制对查询速度和结果准确性的偏向。

3.3 维护算法

当向特征库中添加一个特征向量时，对于逐跳逼近索引，添加的特征向量只影响其邻居节点，包括近邻节点和远程节点。对于近邻节点，只需要调用一次对要添加的特征向量的范围查询操作，然后读取并更新查找到的所有邻近向量的逐跳逼近索引项，并根据查找操作返回的邻近向量建立当前特征向量的逐跳逼近索引项；对于远程节点，由于其与现有数据不直接相关，故可按照索引生成算法直接生成。

当从特征库中删除一个特征向量时，其操作与添加操作基本对称。对于近邻节点，同样也是先调用一次范围查询操作，再更新所有找到的邻近向量和当前数据的逐跳逼近索引项中的所有邻近向量的逐跳逼近索引项，最后删除当前特征向量的逐跳逼近索引项；对于远程节点，直接删除其连接中的当前特征向量的逐跳逼近索引项。

对于改进的逼近索引算法，添加特征向量过程与上面一致。删除过程可先用一个标识位表明该节点已删除，不能作为结果返回，但保留此节点的跳越功能，积累到一定数量后作索引更换处理。

4 实验与分析

4.1 实验数据综述

本文测试所用的高维数据向量分为随机生成和实际数据两类：随机数据维度除对比和性能分析处外默认为10，取值均匀分布在0～255 之间，索引库容量除对比分析处外默认为5 000 000；实际数据为Corel 图像库的图像纹理特征描述符CoocTexture，其维度为16，库容量68 040，元素为有符号浮点数（数据见http：//kdd.ics.uci.edu/database/ CorelFeatures/CorelFeatures.html）。设 定每个节点最多记录25 个连接节点（20 个近邻节点，5 个远程节点），向量间的距离度量函数选用常见的L1 距离，测试结果均为50组随机生成目标向量实验结果的平均值。实验软硬件环境为Intel Core i3-2328M CPU@2.20 GHz，3 GB RAM，开发环境为Windows 7下的Visual Studio 2010。

在100 万及以上容量的均匀特征库中，由于图内连通性较好，本文两种索引没有明显性能差别，仅给出原始版本测试数据。对实际数据库的对比测试，由于特征库容量小且数据分布不均，原始版本索引不再适用，则给出改进版索引测试数据。

4.2 库容量变化对比测试

首先对本算法在各种库容量中的性能进行了整体测试，结果如图5 所示。当库容量线性增长时，相关kNN 查询的平均访问数据条数增长幅度逐步降低，其中5 000 000 库访问数据条数仅为1 000 000 库的两倍不到；且查询平均精确度有明显提升。整体来看，算法在大容量数据库中拥有更好的性能，适合处理海量数据库查询。

图5 不同库容量索引性能对比图

4.3 邻居节点数与近邻范围阈值

通过改变邻居数量和邻居距离阈值，本文测试了5 000 000 库的范围查找时间性能数据，如表2 所示。由实验数据可以看出，提高邻居节点的距离阈值，可以一定程度提高查全率，且在误差范围内对数据访问比例和查询时间没有影响。但当阈值超过一定值，查全率将与邻居节点数相关。同时，增加邻居数量，访问数据比例和查询时间增加，而平均查全率在一定范围内能显著提高，当增加到25%时，查全率的提高将变得缓慢，并慢慢趋于100%。

表2 对5 000 000 库的范围查找综合测试

4.4 到达目标区域跳跃步数统计

选择4.1 节中阐述的关键实验参数进行1 000 次范围查询测试，统计第一阶段的跳跃步数，其分布如表3所示。

表3 逐跳逼近索引实验查询跳数分布表

不难看出，以上测试中95%以上的查询均在6 跳以内就达到目标区域，即在图上一个节点平均只需不到6跳就可到达任意节点，这也与小世界理论的特征相符合。

4.5 优质节点入队阈值与相似判断阈值

参数相似判断阈值为判断当前特征向量是否为相似特征向量的距离阈值，它的大小决定返回结果的多少；入队阈值用于判断当前节点是否为优质节点（第一阶段游走中与目标足够接近的点），直接影响第一阶段游走结束时间，并显著影响第二阶段游走过程中访问的节点数量以及最终的查全率，其设置不能小于相似性判断阈值。图6 和图7 分别为相似判断阈值和入队阈值对实验结果的影响。

图6 范围查全率和数据访问比例随入队阈值变化图

图7 范围查全率和数据访问比例随相似判断阈值变化图

由图6 可以看出，在一定范围内加大入队阈值可以提高平均查全率，但会访问更多的数据，由此带来时间消耗。而对于每个特定的查询，相似性判断阈值已确定，与之对应的入队阈值也需进行调整，否则会导致查全率降低。如图7 所示，此时入队阈值设为190，当相似性判断阈值越高，平均查全率则降低，故在实验中，入队阈值的选择需要结合综合性能和相似性判断阈值来确定。

4.6 逐跳逼近转换节点数

逐跳逼近转换节点数是逐跳逼近从第一阶段转换为第二阶段的条件。由表4 可知，当该值较小时，第一阶段为第二阶段提供的优质种子少，需更多的逐跳逼近才能找到匹配的节点，而当该值较大时，第一阶段已经有足够的优质种子，第二阶段需要访问的条数相对就较少。同时可以看到，该参数对平均查全率基本没有影响，主要原因在于对相互连通较好的图，一般情况只需要一个优质种子就可以通过不断逐跳逼近找到所有匹配节点。

表4 对5 000 000 库的范围查找综合测试

4.7 性能对比与总结

分别对实际数据和随机生成数据比较了逐跳逼近索引算法（固定近邻数）与经典的iDistance 算法和VA-File 算法的综合性能，如表5 所示，其中的10 万容量库数据为自动生成的均匀随机数，68 040 容量库为Corel图库的CoocTexture特征描述符数据。

表5 本文算法与iDistance，VA-File 性能对比

根据表5及以上数据可以看出，在小库容量中，本文算法的数据访问比例会有一定增加，其主要原因在于访问跳数有一定的下限，对于小库容量，比例会有所上升。但与其他很多索引结构，比如iDistance 相比，其访问比例仍然较小。与VA-File 相比，本文算法访问比例稍有逊色，但近似向量在降低访问比例的同时使查询准确性损耗太大，故本文索引综合性能仍明显优于VA-File。

对于实际特征数据对比模块，数据的不均匀分布一定程度上增加了访问的跳数及访问数据比例，且对范围查全率有轻微影响，但整体来说影响不大，本文算法仍能有效处理。

5 结束语

本文针对高维索引问题，提出一种基于图的高维索引算法——逐跳逼近索引算法，及其一种改进版本，算法以小世界模型理论为基础，建立自组织索引结构，维护局部区域点与点在度量空间上的邻近关系，同时融入图上的跳跃逼近思想，从图中任意节点出发，每次仅利用当前节点的局部信息，选择与目标节点最近的节点作为下一跳节点，从而将查询过程的“关注点”逐步往查询命中区域逼近。

该算法结构简单，具有良好的可维护性和拓展性，同时基于其查询访问数据比例极小，且比例会因特征库容量增大，连通性加强而进一步降低，特别适合大特征库的相似性查询；此外，算法各部分仅依靠局部信息跳跃查找，特性极为适合应用于分布式场合，可进一步加强其进行大规模查询的性能。因而，对该算法的下一步研究工作主要为其在高维度大规模特征库中的分布式查询实验。

[1] 谢毓湘，吴玲达，栾悉道.基于内容的图像检索技术研究[J].计算机工程与应用，2002，38（1）：35-38.

[2] 张军旗.支持最近邻查找的高维空间索引[D].上海：复旦大学，2007.

[3] Li G，Tang J.A new R-tree spatial index based on space grid coordinate division[C]//Proceedings of the 2011，International Conference on Informatics，Cybernetics，and Computer Engineering（ICCE2011）.Berlin Heidelberg：Springer，2012：133-140.

[4] Lv T，Xie F R.HVA-Index：An efficient indexing method for similarity search in high-dimensional vector spaces[C]//2010 International Conference on Information Networking and Automation.IEEE，2010，2：152-157.

[5] Gunnemann S，Kremer H，Lenhard D，et al.Subspace clustering for indexing high dimensional data：a main memory index based on local reductions and individual multi-representations[C]//Proceedings of the 14th International Conference on Extending Database Technology.ACM，2011：237-248.

[6] Bentley J L.Multidimensional binary search trees used for associative searching[J].Communications of the ACM，1975，18（9）：509-517.

[7] Ciaccia P，Patella M.M-tree：An efficient access method for similarity search in metric spaces[C]//Proceedings of theInternational Conference on Very Large Data Bases.Morgan Kaufmann Pub，1997，23：426-435.

[8] 孙劲光，王淑娥.CKDB-Tree：一种有效的高维动态索引结构[J].计算机工程与应用，2009，45（30）：157-160.

[9] Travers J，Milgram S.An experimental study of the small world problem[J].Sociometry，1969，32（4）：425-443.

[10] 汪小帆，李翔，陈关荣.复杂网络理论及其应用[M].北京：清华大学出版社，2005.

[11] Newman M E J，Watts D J.Renormalization group analysis of the small-world network model[J].Physics Letters A，1999，263（4）：341-346.

[12] Watts D J，Strogatz S H.Collective dynamics of‘small-world’networks[J].Nature，1998，393（6684）：440-442.

[13] Kleinberg J.The small-world phenomenon：An algorithmic perspective[C]//Proceedings of the Thirty-second Annual ACM Symposium on Theory of Computing.ACM，2000：163-170.

[14] Johan U，Brian K，Lars B，et al.The anatomy of the Facebook social graph [J].The Anatomy of Facebook，2011：1-17.

[15] 蒋澜，朱明.基于DHT的高维数据相似性检索方法研究[J].小型微型计算机系统，2010，31（9）：1764-1769.