薛向阳，罗航哉，吴立德
(复旦大学计算机系，上海200433)
摘 要: 本文提出一种新的高维空间中点数据的索引方法，其基本原理是用格矢量量化(Lattice vector quantiza 2 tion )均匀划分数据空间、用倒排文件(Inverted File )存储格点、用T rie 树实现倒排文件的组织和存储、用T rie 并行搜索算法实现倒排文件的快速访问.和传统索引方法相比，新方法具有许多优点，例如它能以较低的复杂度建立索引结构、支持非常高维的数据索引、充分利用高维空间中点分布的稀疏性等.实验结果表明，在较高维数时,LIFT 性能优于传统索引方法. 关键词: 索引结构；相似性检索；矢量量化中图分类号: TP311 文献标识码: A 文章编号: 037222112(2001)022*******
LIFT :An Index Structure for H igh Dimensional Data
X UE X iang 2yang ,LUO Hang 2zai ,W U Li 2de
(Department o f Computer Science ,Fudan Univer sity ,Shanghai 200433,China )
Abstract : A new method for indexing large am ounts of points in high 2dimensional space is proposed.The basic principle is as follows :uniformly partition the data space by Lattice vector quantization ,store the lattice points by Inverted File ,organize the inverted file by T rie tree ,and fast access the inverted file by T rie parallel search alg orithm.We called this index structure LIFT.C om pared with the traditional index methods ,the LIFT can build the index structure with low com plexity ,support very high dimensionality ,and take advantage of sparsity of data points in high 2dimensional space ,etc.The experiments show that for high 2dimensional data ,the LIFT out 2per forms the well 2known R 2tree.
K ey words : index structure ;similarity retrieval ;vector quantization
1 引言
在基于内容的检索和数据挖掘等领域，经常需要在对象
集中查与某个给定对象“相似”的对象，这样的查过程叫“相似性检索”.通常，对象间的相似性不是由对象本身直接定义的，而是从对象中提取出“特征”，然后在对象的“特征”上定义相似性.大多数情况
下，特征用高维空间的点(或特征矢量)来描述，特征矢量之间的接近程度反映了对象内容的相似度大小，因此基于内容的检索就简化为空间中点的快速搜寻问题.
用R Q (Q o )表示查询结果集,Q o 表示查询对象，本文定义二类相似查询方法.一类叫“范围查询(range query )”: R Q
Range (Q o )={x |x ∈O ,D (f (x ),f (Q o ))ΦT}(1)其中T 为范围门限.另一类叫做“k 2近邻查询”,k 为给定的正
整数.k =1时的最近邻查询定义为:
R Q
1-Nearest (Q o )={x 0|x 0∈O ,Πy ∈O :D (f (y ),f (Q o ))
ΕD (f (x o ),f (Q o ))}
(2)
设R Q (k -1)-Nearest 是“(k -1)2最邻近查询”的结果，则“k 2最邻近查询”定义为:
R Q景秀中学
k -Nearest
(Q o )=R Q (k -
1)-Nearest
(Q o )∪{x 0|x 0∈O ′,Πy ∈O ′:
D (f (y ),f (Q 0))ΕD (f (x 0),f (Q 0))}
(3)
其中,O ′=O -R Q (k -1)-Nearest (Q 0),O 表示对象集合,f 表示对象到特征矢量的映射.本文只讨论索引结构，不考虑映射f.
实现相似查询的方法很多，最基本方法是“顺序扫描算法(SS A )”：顺序检查O 中每个对象，如果它符合相似性查询要求，则将该对象加入R Q (Q o )中.SS A 的CPU 和I/O 复杂度通常都很大，为了降低查
询开销，多年来，人们陆续提出多种支
持快速相似查询的索引结构，例如R 2树[1]、k 2d 2树[2]
、K 2D 2B 2
树[3]、T V 2树[4]、SS 2树[5]和SR 2树[6]
等.无论采用哪种索引结构和实现哪种相似性查询，其实现方法是基本一致的:(1)迅
速到R Q (Q o )的一个超集R Q super (Q o );(2)在R Q
super (Q o )上做
SS A 得到R Q (Q o ).因此，人们总是期望做到:(1)R Q super (Q o )包法制与经济
含R Q (Q o );(2)R Q super (Q o )足够小;(3)快速得到R Q super (Q o ).
然而，在实际应用中R Q super (Q o )经常大于R Q
(Q o )，特别是
当维数增加时,R Q super (Q o )迅速接近O ，这一现象叫做 “维数灾收稿日期:1999211201；修回日期:2000203206
基金项目：自然科学基金重点项目(N o.69935010)；国家8632317201207299；自然科学基金项目(N o.60003017)
第2期2001年2月
电 子 学 报
ACT A E LECTRONICA SINICA V ol.29 N o.2
Feb. 2001
难”，前面提及的索引结构几乎都存在这一问题.尽管VA2 File[9]能够一直保证R Q super(Q o)非常接近R Q(Q o)，但是其CPU 代价很大.本文则利用格矢量量化[14]、倒排文件和T rie数据结构[15]，构造出一种新的索引结构，力图在一定程度上克服维数灾难，同时确保较小的CPU代价.
2 LIFT的基本原理
211 用格矢量量化实现空间划分
格矢量量化就是将数据空间划分成同样大小的V onoroi 胞腔.对格A2来说，胞腔为正六边形；对格Z2来说，胞腔为正方形；对高维来说，胞腔通常是凸多面体.每个V onoroi胞腔的质心就是相应格的格点，如果任一矢量x落在某个V onoroi胞腔V i中，设其质心为l i，那么x就被量化为l i，即l i=LVQ (x)，这里LVQ(·)表示格矢量量化.由于格的良好代数性质，格矢量量化算法的复杂度通常很低[10,11].
假定数据库中有N个对象，每个对象对应一个唯一序号id，从每一个对象上提取出一个特征矢量，那么这N个特征矢量将组成数据集合DB={x i,i=1,2,…,N}.经过格矢量量化后，多个特征矢量可能会落在同一个胞腔中，量化为同一个格点.设量化后格点集合为DB vq={l k=LVQ(x i)|x i∈DB}，假设DB vq的大小为M，显然MΦN.
212 用倒排文件实现格点的存储21211 倒排文件
LIFT用倒排文件来组织和存储格点DB vq，它将格点看作倒排文件的键值，每个格点可能会对应若干个序号，见表1.表1 倒排文件存储格点
集合和图像序号
键值图像序号
l1id1,1,id1,2,…
l2id2,1,id2,2,…
……
l M id M,1,id M,2,…
快速访问倒排文件的方法很多，例如二分查法、Hash 和T rie等，本文采用T rie方法，因为它能够充分利用特征矢量在高维空间中分布的稀疏特性，实现快速搜索.
21212 T rie树的构造
为了快速访问倒排文件表，本文用T rie表示所有键值的集合DB vq={l i=(l i,j,j=1,2,…,n),i=1,2,…,M}，则T rie 的字母表为∑={λL,(λL+1),…,0,…,(λH-1),λH}，其中λL
=min
i,j (l i,j),λH=max
i,j
(l i,j)，因此有DB vqΑ∑n.事实上，基于
DB vq构造T rie树是一个递归过程.不妨假设当前正处理第d 维(1ΦdΦn)，再设SΑDB vq，于是为S建立一个T rie节点的过程如下:
(1)令|S|表示集合S中的元素个数.如果|S|>1，将S
按第d维分成(λH-λL+1)个子集:Sλ
L ,Sλ
L
+1,…,SλH-1,SλH,
其中S t={l i|l i,d=t}.再分别基于Sλ
L ,Sλ
L
+1
,…,Sλ
H
-1
,Sλ
H
按
照第(d+1)维来递归构造(λH-λL+1)个T rie节点.最后，建立一个中间节点将上述(λH-λL+1)个T rie子节点连接到中间节点的相应位置.
(2)如果S=<，则建立一个空节点.
(3)如果|S|=1，则建立一个终结节点.设l∈S为S的唯一元素,{id1,id2,…}为l所对应的图像序号集，将(l d+1, l d+2,…,l n)和序号{id1,id2,…}存储到此终结节点中.
用S=DB vq和d=1调用上面过程，就可以递归建立一个完整的T rie树，称之为T rie lift.至此，就完成了
用T rie重新组织和存储倒排文件表.
213 实现范围查询的基本原理
21311 范围查询的基本步骤
假设查询对象为Q O，查询矢量y=f(Q O).现在，基于公式(1)进行范围查询，范围门限为T，于是:
(1)用同样的矢量量化器对查询矢量y进行量化，得到: l O=LVQ(y).
(2)根据查询范围门限T，首先计算出δ=「T/T0 .
(3)决定需要搜索的超矩形窗口W Rect:
l Low=(max((l0,1-δ),λL),max((l0,2-δ),λL),…,
max((l0,n-δ),λL))
l High=(min((l0,1+δ),λH),min((l0,2+δ),λH),…,
min((l0,n+δ),λH))
其中,l Low和l High是超矩形窗口W Rect的两个对角顶点.
安康学院学报
(4)在倒排文件中，用T rie并行搜索算法(TPS A)搜索W Rect中所有格点，得到R Q super(Q o).
(5)根据公式(1)，对R Q super(Q o)进行顺序搜索，得到最终查询结果R Q Range(Q o).
21312 T rie并行搜索算法
算法复杂度主要取决于对倒排文件表的查速度.查倒排文件表最慢的方法是顺序扫描，它需要将格点l O和倒排文件表中键值进行逐个比较.事实上，随着维数增加，查询窗口W Rect中格点数目迅速增加，它可能会远远大于DB vq中格点数M.然而|W Rect∩DB vq|总是非常有限的，因为W Rect中有效格点非常稀少，最多也不会超过M.有很多算法用于快速访问倒排文件：二分查、Hash查和T rie树查等.本文采用T rie树方法的原因是：二分查和Hash查必须用W Rect中所有格点去搜索倒排文件，因此总复杂度为|W Rect|次倒排文件查，尽管W Rect中大量格点并不存在于倒排文件之中.
为了快速地搜索有效格点集合(W Rect∩DB vq)，得到R Q super (Q o)，我们提出T rie并行搜索算法(TPS A).TPS A是一个递归过程.用d表示当前正在处理的维，用R oot trie表示当前子树的根，那么:
(1)如果R oot trie为Null，则返回.
H无穷控制LMI(2)如果R oot trie是终结节点，设l′=(l d+1,l d+2,…,l n)为存储在R oot trie中的剩余部分，对于i=d+1,d+2,…,n均有l Low,iΦl iΦl High,i，则该终结节点中所有图像序号对应的矢量都加入R Q super(Q o).
(3)如果R oot trie是中间节点，则以R oot trie的第l Low,d个分支到第l High,d个分支为根，令dωd+1,，调用本递归过程，继续查.
令d=1,R Q super(Q o)的初值为NU LL,R oot trie等于T rie lift的根，调用上述递归过程，得到R Q super(Q o).在实验中，发现T rie 树中有大量空节点，为了进一步减少TPS A的复杂度，对原始T rie树又进行了改进，通过增加少量空节点指示信息(即指明空节点所处位置信息)，从而删除所有空节点，得到压缩的
391
第 2 期薛向阳:LIFT：一种用于高维数据的索引结构
T rie 树.然后，再对TPS A 略加修改，就可以在压缩后T rie 上进
行快速搜索，从而提高计算速度.
3 实验研究
用计算机模拟方法比较LIFT 和R 2树的索引性能，包括
I/O 代价和CPU 复杂度两个指标.其中,I/O 代价定义为RIO 2
Cost =|R Q super (Q o )|/|R Q
(Q o )|，它直接反映一个索引结构在一次查询过程中所涉及到的对象，是衡量I/O 代价的关键指标，理想情况下RIOCost =1;CPU 代价则是用Speed 2up =t SS A /t fast 测量，其中t SSA 表示SS A 算法实现一次查询所需要的时间,t fast 表示采用索引结构后实现一次查询所需要的时间，注意测量t SS A 和t fast 时，所有相关数据都在主存中，即这些数据和辅助存储器无关，因此Speed 2up 主要反映了一次查询所花费的计算复杂度.
在实验中，用随机数发生器产生(N +L Q )个高斯矢量，矢
量中每个分量是相互独立的，且都服从均值为0、方差为σ2
的高斯分布；然后，产生N 0个矢量，它们均匀分布于空间[-A ,
+A ]n 中；对每个高斯矢量，从N 0个均匀分布的矢量中随机
选取一个，两者相加；最终得到(N +L Q )个矢量，取其中N 个矢量作为数据集DB ，剩余L Q 个矢量用作为查询矢量
.
图1 (a )1024维时的I/O 代价; (b )1024维时的CPU
代价
图2 (a )不同数据库规模时的CPU 代价;
(b )不同数据库规模时的I/O
代价
图3 (a )不同维数时的CPU 代价;(b )不同维数时的I/O 代价首先比较LIFT 和R 2树的I/O 代价.图1(a )和(b )分别给出了R 2树和LIFT 的I/O 代价和CPU 性能(n =1024,N =
50000)，可以看到：不管查询范围T 如何变化,LIFT 的RIOCost
非常接近于1(即理想情形)，而R 2树的RIOCost 曲线随着T 变大而迅速增加;LIFT 的计算复杂度明显比R 2树低.图2(a )和
(b )给出了不同数据库规模时LIFT 和R 2树的索引性能(n =
256,T =41、44)，可以看出:(1)当数据库规模N 增加时,LIFT
的加速比Speed 2up 比R 2树增加快;(2)范围门限T 增加导致加速比降低;(3)不管T 和N 多大,LIFT 的RIOCost 始终接近于1，而R 2树的I/O 性能随着N 增加而变坏.图3(a )和(b )给
出不同维数时的索引性能：图3(a )表明LIFT 的加速比Speed 2up 几乎保持常数，而R 2树的加速比随维数增加而下降；图3(b )表明(1)LIFT 的RIOCost 还是接近于1;(2)R 2树的RIOCost 则表现出复杂的变化趋势，它首先快速增加，然后又迅速减少,“增加”恰好说明R 2树的I/O 性能随维数增加而迅速恶化，而“减少”的原因是在于：随着维数增加，数据点在空间中分布密度急剧减少，从而导致查询窗口中数据点急剧减少，导致RIOCost 在一定维数后迅速下降.最后，图4给出了构造LIFT 和R 2树这两种数据结构所需要花费的时间.可以看出：随着维数增加，构造R 2树的复杂度急剧增加；随着数据库规模增加，构造R 2树的复杂度也增加很多；而构造LIFT 的复杂度总是比构造R 2树要低
.
图4 (a )不同维数时构造索引结构的时间
(b )不同数据库规模构造索引结构的时间
上述模拟结果表明：和R 2树相比,LIFT 具有较低I/O 代价、较低CPU 代价和较低构造代价，支持很高维数的索引，在一定程度上克服了维数灾难.
4 结论
本文主要讨论了高维点数据的范围查询问题，提出了一种新的索引结构，称之为LIFT ，它用格矢量
量化对数据空间进行划分，用倒排文件组织格点，用T rie 和压缩T rie 重新组织倒排文件，用TPS A 实现范围查询.实验结果表明LIFT 无论在I/O 代价还是CPU 代价方面都比R 2树要好.将来研究工作集中在以下两个方面：用LIFT 实现最近邻查询；将LIFT 用于实际数据库之中.参考文献:
[1] G uttman A.R 2trees :A dynam ic index structure for spatial searching
[A].Proc.AC M SIG M OD Int.C on f.On M anagement of Data [C ],Boston ,M A ,1984:47-57.
[2] J L Bentley.Multidimensional binary search trees used for ass ociative
searching [J ].C ommunications of the AC M ,18,Sept.1975:509-
517.
[3] R obins on J.T.The K 2D 2B 2tree :A search structure for large multidi 2
mensional dynam ic indexes [A ].Proc AC M SIG M OD Int.C M anagement of Data [C],1981:10-18.
[4] K.2I.Lin ,H.V.Jagdish ,and C.Falouts os.The T V 2tree :An index
structure for high 2dimensional data [J ].V LDB Journal ,M arch 1994:517-542.
[5] White D.A.,Jain R.S im ilarity indexing with the SS 2tree [A ].Proc.
12th Int.C on f on Data Engineering [C],New Orleans ,LA ,1996.
[6] N.K atayama and S.Satoh.The SR 2tree :An index structure for high di 2
mensional nearest neighbor queries [J ].Int.Proceedings of the AC M SIG M OD International C on ference on M anagement of Data ,Tucs on ,
491 电 子 学 报2001年
Ariz on US A,1997:369-380.
[7] N.Beckmann and H.P.K riegel and R.Schneider and B.Seeger.The
R32tree:an efficient and robust access method for points and rectangles
[J].Proceedings of the SIG M OD C on ference,Atlantic City,N J,June
1990:322-331.
[8] S tefan Berchtold,Daniel A.K eim,and Hans2Peter K riegel.The X2tree:
an index structure for high dimensional data[A].Proceedings of the
22nd V LDB C on ference[C],1996:28-39.
[9] R oger W eber,Hans2J.Schek,S tephen Blott.A quantitative analysis and
performance study for sim ilarity search methods in high2dimensional
spaces[A].Proc.of the24th V LDB C on ference[C],New Y ork,US A,
1998.
[10] J.C onway and N.J.A.S loane.S phere Packings,Lattice and G roups
[M].New Y ork:S pringer2Verlag.1991.
[11] J.H.C onway and N.S loane.A fast encoding method for lattice codes
and quantizers[J].IEEE T rans In formation Theory,N ov.1983,29:820
-
824.
[12] M.Flickner,et al.Query by Image and Video C ontent:the QBIC Sys2
tem[M].IEEE C om puter,1995.
[13] Pentland,R.W.Picard,and S.Sclaroff.Photobook:T ools for content2
based manipulation of image databases[J].Int.Proc.SPIE S torage and
苏拉 沙玛
Retrieval for Image and Video Databases II,1994,2.
[14] X iangyang Xue,Hangzai Luo,Lide Wu.Index P oint Data Using Alge2
braic Lattic[J].SPIE E lectronic Imaging2000:S torage and Retrieval
for M edia Databases,San Jose,US A:3972:271-283.
[15] X iangyang Xue,Hangzai Luo,Lide Wu.Index point data using lattice
vector quantization and hash[A].International W orkshop on Very Low
进销存管理系统论文Bitrate Video C oding[C],V LBV’99,October29230,1999,K y oto Re2
search Park,K y oto,JAPAN.
作者简介:
薛向阳 1968年生，现为复旦大学计算机系副教授，研究兴趣包括：基于内容的图像视频信息检索、高维数据索引结构和视频压缩编码算法.
罗航哉 1977年生，现为复旦大学计算机系助教，在职研究生，研究兴趣包括：基于内容的图像视频信息检索和高维数据索引结构.
吴立德 1937年生，现为复旦大学计算机系教授，博士生导师，研究兴趣包括：自然语言处理、计算机视觉和多媒体信息检索.
591
第 2 期薛向阳:LIFT：一种用于高维数据的索引结构
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议