计算机研究与发展
ISSN 100021239/CN 1121777/TP
Journal of Computer Rearch and Development 42(12):2213～2218,2005
收稿日期:2004-02-27；修回日期:2004-11-03
基金项目：国家自然科学基金项目(60402007,60373020)；国家“八六三”高技术研究发展计划基金项目(2002AA10301125)；上海市科技发展
基金项目(03DZ15019,03DZ14015)；教育部科学技术研究重点基金项目(104075)
VA 2T rie ：一种用于近似k 近邻查询的高维索引结构徐光启简介
董道国 刘振中 薛向阳
(复旦大学计算机科学与工程系 上海 200433)(rod 1dong @gmail 1com )
VA 2T rie :A N e w and E ff icient High Dimensional Index Structure for Approxi 2mate k N earest N eighbor Q uery
Dong Daoguo ,Liu Zhenzhong ,and Xue Xiangyang
(Depart ment of Com puter Science and Engineering ,Fudan U niversity ,S hanghai 200433)
Abstract Since 1990’s ,great progress has been made in the area of content 2bad multimedia information retrieval 1A very challenging problem emerged at the same time :how to organize high dimensional vectors so that efficient similarity query could be realized 1Many index structures have been propod to solve this problem ,such as R 2Tree and its variants ,VA 2File ,A 2Tree etc 1From the published results ,it can be con 2cluded that most of the methods could achieve good query performance when the dimensionality is less than 201However ,the performance suffers greatly as the dimensionality increas 1To obtain efficient sim 2ilarity query in higher dimensional spaces ,a new index structure called VA 2Trie is introduced 1The key idea behind VA 2Trie is adopting the idea of quantization to compress the vectors and then employing the Trie structure to organize and manage the approximations 1The experimental results show that VA 2Trie outper 2forms A 2Tree and quential scan in high dimensional spaces 1K ey w ords index structure ;similarity query ;information retrieval
摘 要 近年来，随着多媒体信息检索技术的不断发展，如何实现高维特征矢量的快速相似性查询成为
一个重要的研究课题1为此，人们提出了许多索引结构，包括:R 2Tree 及其变种、对矢量进行量化近似的VA 2File 、引入量化思想的A 2Tree 等等1从公开发表的成果看，这些索引结构在较低维数时，都能够表现出较好的查询性能；而当维数增加时，性能则急剧恶化1为了在更高维数下实现快速相似查询，可采用VA 2File 和A 2Tree 中的近似思想，并借助Trie 结构来组织和管理压缩后的近似矢量，即所谓的VA 2Trie 1实验结果表明，在高达128维时VA 2Trie 仍有查询加速，其性能远好于A 2Tree 1
关键词 索引结构；相似性查询；信息检索中图法分类号 TP311113413
1 引 言
在基于内容的多媒体信息检索等应用中，经常需要从多媒体数据库中查找与给定对象最相似的k
个对象，这就是k 近邻查询1通常，首先提取每一个
多媒体对象的特征矢量，形成矢量库，多媒体对象之
间的相似程度就用相应特征矢量间距离来度量,k 近邻查询就是从矢量库中搜索到k 个与查询矢量最近的特征矢量1实现k 近邻查询最简单的方法是顺穿针引线游戏规则
序扫描(scan )，但当数据量较大时,Scan 需要耗费大
量的磁盘开销和CPU 代价，为了提高效率，必须借助于高效的索引结构1
R 2Tree 类索引结构是最受关注的一类高维索引结构120世纪80年代Guttman 首先提出了R 2Tree [1]，它利用树结构管理数据，每个内部节点为该节点中所有数据的最小外接矩形(MBR )，真实数据
仅出现在叶子节点中1但R 2Tree 内部节点之间存在着严重的重叠区域和死区域现象，影响了R 2Tree 的效率1为此，人们相继提出R +2Tree [2],R 32Tree [3],SR 2Tree [4]等，但是这些树形索引结构随着数据维数
的增加，查询性能迅速下降1除采用树形索引结构之外,Weber 等人在文献[5]中提出了VA 2File ，它利用量化的方法得到近似矢量，并将这些近似矢量按照顺序排列形成VA 2File ，通过减少矢量的存储空间来减少查询期间的磁盘开销1此后,Sakurai 等人将量化近似思想与树结构结合起来，提出了A 2Tree [6]，大大提高了R 2Tree 类索引结构中间节点的扇出度，减少了内部节点的数量以及树的高度，获得了更高的查询性能增益1
基于上述各种索引结构的k 近邻相似查询都致力于获取精确的k 个查询结果，然而大多数实际
应用中并不需要得到最精确的k 近邻，因此用太高的搜索代价过分追求精确的k 近邻查询结果是值得商榷的，如果能够在查询代价与查询结果质量之间取得较好折中，可以更好地满足大多数应用的需求
1本文正是在“近似”k 近邻查询可以满足大多数应用需求的前提下，提出了一种新的高维索引结构VA 2Trie ，它的主要思路是吸取VA 2File 和A 2Tree 中近似量化的思想以实现矢量的大幅度数据压缩；然后引入数据结构Trie 来组织和管理近似矢量，并通过近似范围查询实现快速的近似k 近邻查询1本文余下部分是这样组织的：第2节描述了VA 2Trie 的结构和构造算法；第3节是基于VA 2Trie 的近似k 近邻查询算法；第4节详细叙述并分析了实验结果；最后给出了本文的结论1
2 VA 2T rie 组成以及构造方法
211 VA 2T rie 的组成
VA 2Trie 分为2层：上层是由VA 2Trie 的内部
节点组成的Trie 层；下层是由叶子节点组成的VA 层1叶子节点中保存着所有近似矢量数据，并以磁盘页形式存储，图1为VA 2Trie 的示意图
1
qq空间登入Fig 11 The structure of VA 2Trie 1
图1 VA 2Trie 的结构示意图
21111 Trie 层
根据Trie 结构本身的特点，如果数据空间的每一维等分为m 个量化区间，则Trie 层中每个节点都应该包含m 个孩子，其中根节点表示近似矢量数据的第0维，根节点的孩子表示第1维，依此类推，对d 维数据构建的Trie 应该具有d 层1这样得到的Trie 层具有数量非常多的路径分支，但在高维空间中，只有比例极少的网格中可能包含有数据1为此，我们采用以下两点策略:Trie 层中不保存不包含
任何数据的路径；对包含数据的路径，假如到某一维后，所有的数据均出现在同一个网格中，该维之后的路径信息就不再保存1一个Trie 层节点由至多m 个这样的数据项组成:(i nterval ,poi nter )，其中i n 2
terval 表示节点对应维的量化区间,poi nter 为指向
清晨听到公鸡叫下层节点的指针121112 VA 层
VA 层中包含一系列保存着近似矢量的VA 层
节点，每个节点对应于磁盘中的一个或多个磁盘页,
4
122计算机研究与发展 2005,42(12)
由于高维数据的无序性，将近似矢量有效地组织到固定大小的节点中以提高查询效率是非常困难的，因此VA2Trie只是将它们顺序保存在节点中1一个VA层节点由多个这样的数据项组成:(va,oi d list),va表示一个近似矢量,oi d list表示所有近似矢量为va的对象i d序列，由于近似矢量相同的对象可能不止一个，在某些特殊情况下，可能出现oi d list包含的对象i d过多而一个磁盘页的空间无法存放，此时需要将节点增大整数倍个磁盘页大小直到能够容纳下为止1
212 插入和删除
向VA2Trie中插入一个高维矢量是非常简单的，首先得到待插入矢量的近似数据，然后根据近似数据从Trie层根节点出发，沿着相应的路径插入到VA层1插入时存在两种情况:消防安全警示语
四年级竖式
(1)Trie层中已经包含新插入的近似数据对应的路径，即VA2Trie中已经具有同该数据在一个网格中的矢
量，此时只需将对象i d添加到VA层对应数据项的oi d list中，如果VA层节点发生了溢出，必须将数据项的va及其oi d list转移到一个有足够空间的VA层节点中;
(2)新插入数据的路径不存在，则需要加入新的Trie层节点以满足第211节中所描述的Trie层特点，同时将近似数据和对象i d添加到还有剩余空间的VA层节点中1
从VA2Trie中删除一个对象，首先进行一次精确查询，然后将对象i d从节点中删除，如果此时该对象对应的近似数据中不再存在其他对象i d，即oi d list为空，则将该数据项从VA层节点中删除1
3 近似k近邻查询
针对VA2Trie的结构特点，我们选择利用范围查询间接实现k近邻查询的方法，其思路是对查询矢量进行范围查询，通过逐步扩大查询范围直到查询结果集大小超过k个为止，其中距离查询矢量最近的k个就是k近邻1为了说明VA2Trie的k近邻查询算法，首先给出它的近似范围查询算法1
311 近似范围查询算法
对于给定的查询矢量query vector，范围查询不是基于矢量本身，而是基于其近似矢量query va实现的，因此查询范围并不是原始数据的距离，而是近似矢量的距离1对近似矢量query va和查询范围[range l,range u)，从Trie层的根节点出发，按以下算法查找实现范围查询:
Algorithm A ppRangeQ uery(query va,range l, range u)
1)cur node=Root;Π3cur node为当前节点,
初始为根节点3Π
di m i nf o={};di m=0;Π3di m i nf o为当
前路径所得到的信息,di m为当前维度3Π
QueryResult={};Π3查询结果，初始为空3Π
2)FOR(cur node中的每一个数据项trie entry)
①di m i nf o=di m i nf o+
t rie ent ry.i nterval;
cur distance=dist(query va[011dim],
di m i nf o);
②IF(cur distance>range u)
由于前di m维信息得到的距离已经超过查询范围，该路径不需继续查找 EL SE
cur node=t rie enry.poi nter;
IF(cur node IS Trie Node)
di m++;goto2);
EL SE IF(cur node IS VA Node)
goto3);
3)IF(cur node尚未在该查找过程中访问)
FOR(cur node中的每一个数据项va
ent ry)
cur distance=dist(query va,
va ent ry.va);
IF(cur distance≥range u)
超过查询范围;
EL SE IF(cur distance>range l)
Q ueryResult+=va ent ry.oi d list1
从上述范围查询算法可以看出，查询过程中所计算的是近似矢量之间的距离，并没有计算原始矢量之间的距离，得到的距离结果是近似的，因此这一算法实现的是近似范围查询1
312 初始查询范围的确定
如前所述，基于范围查询实现k近邻查询只需逐渐增大查询范围，直到查询结果超过k个为止，因此初始查询范围的选择是提高查询效率的关键，过小或过大都将影响查询效率1为了能快速有效的
5122
董道国等:VA2Trie：一种用于近似k近邻查询的高维索引结构
根据查询矢量得到相应的初始查询范围,VA2Trie 中需维护一个不同k值的查询范围列表:
(1)对于高维空间中均匀分布的数据，根据其分布特性，理论上任何一次可以恰好得到k近邻的查询范围应该相差不大，因此可以采用简单的顺序扫描方法进行一定数量的查询，取第k近邻距离的平均值作为此后每次k近邻查询的初始查询范围，根据k的取值不同可以得到一个查询范围列表，形式如下:
{(k0,range0),(k1,range1),(k2,range2),…, (k i,range i)}1
(2)在真实的应用中，高维矢量数据往往不是均匀分布的，不过经常是成簇聚集的，而且每一簇数据的分布特征各不相同1这种情况下，我们建议首先对数据聚类,，然后从每一类中选出一定数量的矢量进行简单的顺序扫描查询，取第k近邻距离的平均值作为该类k近邻查询的初始查询范围，根据k取值不同可得到每一类的查询范围列表1此时,VA2Trie需要维护一个类中心列表以及各个类中心所对应的查询范围列表，形式如下: Center0:{(k00,range00),(k01,range01),…,
(k0i,range0i)};
Center1:{(k10,range10),(k11,range11),…,
(k1i,range1i)};
…
Center j:{(k j0,range j0),(k j1,range j1),…,
(k ji,range ji)}1
上述查询范围列表一般是在VA2Trie动态构造完成后离线获得的，只有经过了大量的插入和删除, VA2Trie中的数据在高维空间中的分布方式发生变化时，该列表才需要重新生成1
313 查询范围增大步长的确定
除了初始查询范围外，另一个影响k近邻查询中范围查询次数的重要因素是每次查询范围增大的步长的确定1在实际应用中，虽然数据分布方式通常被认为是成簇分布的，但每一簇中的数据分布很难预测，无法从理论上给出步长的确定方法1为实现有效的查询，本文给出一种根据上次范围查询结果数量及查询范围列表来确定本次查询范围的方法：其思想是如果上次查询结果集中矢量数量L< k，则根据k与L的比值在范围列表中选择更大的k 所对应的范围进行新的查询，具体见第314节1314 近似k近邻查询算法
如前所述,VA2Trie的k近邻查询算法是基于范围查询实现的，在离线得到不同k值的近邻查询范围列表后，通过逐步在查询范围列表中选择更大的查询范围快速实现k近邻查询1由于VA2Trie的范围查询是在近似矢量上实现的，因此得到的k近邻也是近似的1具体算法如下:
Algorithm A ppkN N(query vector,k)
1)query vector→query va;Π3量化，得到近似
失量3Π
2)选择合适的查询范围列表:
①对均匀分布的数据，只有惟一的列表;
②对真实数据，根据query vector与各个中
心点的距离，选择距离最小的那个对应
的列表;
设得到的查询列表为
range list={(k0,range0),(k1,range1), (k2,range2),…,(k i,range i)};
3)K′=k,last range=0;
4)range=range list[K′];Π3选择查询列表
中K′对应的查询范围3Π
5)R=A ppRangeQuery(query va,last range,
关于花生的谜语
range);
6)IF(‖R‖<k)
K′=max(k
max(‖R‖,1)
×K′,K′+1);
last range=range;
转4);
EL SE
选择与query va距离最小的k个i d作为查询结果返回，查询结束1
4 实验结果
文献[6]指出A2Tree的查询性能超过了VA2 File和SR2Tree，因此本文主要比较了VA2Trie和A2Tree以及顺序扫描之间的查询效率1为了更客观比较它们的性能，我们选择查询的总时间代价作为评价指标，即实现一次查询所花费的磁盘代价与CPU代价之和1
测试数据选择了以下两种：一种是由随机数生成器产生的在高维空间中均匀分布的数据；另一种是从实际视频数据库中提取，视频数据来源是MPEG22
6122计算机研究与发展 2005,42(12)
格式的BBC 电视节目1矢量的维数分别选择16,32,48,64,96和128共6种，数据库规模均为500001411 VA 2T rie 与A 2T ree 的插入代价比较
由于VA 2Trie 的结构和插入非常简单，因此向VA 2Trie 插入一个数据的代价非常小，为了比较
VA 2Trie 和A 2Tree 的插入代价，我们实验时向已经
包含50000个数据的VA 2Trie 和A 2Tree 中分别插入1000个新数据，取平均插入时间作为比较参数，图2显示出在任何维数下VA 2Trie 插入一个数据的代价都远小于A 2Tree
1
Fig 12 Inrtion cost of VA 2Trie and A 2Tree 1(a )Real datat and (b )Uniform datat 1
图2 VA 2Trie 和A 2Tree 插入代价1(a )真实数据;(b )均匀分布数据
412 VA 2T rie 与A 2T ree 及Scan 的查询性能比较
首先，通过第312节中描述的方法，分别得到均
匀分布数据和真实数据所对应的查询范围列表，该列表得到后将可在此后的查询中重复使用，除非高维数据的分布方式发生明显变化，否则该列表不需重新生成，因此在进行查询性能比较时将不考虑查询范围列表的生成代价1
在实验中，我们选择k =20，对不同维数下的均
匀分布数据和真实数据分别进行了1000次20近邻查询，取平均总体查询时间作为查询代价，图3中显示了实验结果1可以看出A 2Tree 随着维数增大，性能迅速下降，当到达64维时其查询代价已经超过Scan ，而VA 2Trie 并没有呈现出随维数增大性能迅速下降的现象，当到达128维时，仍表现出远高于Scan 的查询性能
1
Fig 13 k NN query performance 1(a )Real datat and (b )Uniform datat 1
图3 k 近邻性能比较1(a )真实数据;(b )均匀分布数据
413 VA 2T rie 查询结果质量
对近似k 近邻查询，查询结果的质量和查询代价是评价索引结构及查询算法的两个重要因素，设
R k NN 为精确k 近邻,R A k NN 为近似k 近邻,q 为查询
矢量，式(1)(2)为衡量近似查询结果集质量的两个评价指标，其中ε可从整体上衡量结果集的质量,ρ为查询结果集的精度1
ε=
∑p ∈R A k NN
D (p ,q )-∑p ∈R k NN
D (p ,q )
出塞古诗王昌龄∑
p ∈R k NN
D (p ,q ),
(1)
ρ=
‖R A k NN ∩R k NN ‖
‖R k NN ‖
1
(2)
我们对不同维数下的VA 2Trie 分别进行了
1000次20近邻查询，得到其平均的ε和ρ，表1为实验结果1可以看出，在不同情况下ε都非常小，也就是说，近似查询结果集和精确查询结果集同查询数据之间的距离相差非常小，即相似程度非常接近；同时精度ρ也维持在较高的比例上(均超过了80%)，即精确结果集中的数据绝大多数都在近似结果集中，
在大多数应用本身就是一种“相似”查询的情况下，这样的查询质量显然是可以满足实际应用的1
7
122董道国等:VA 2Trie ：一种用于近似k 近邻查询的高维索引结构
