《度量空间中索引方法的研究》由会员分享，可在线阅读，更多相关《度量空间中索引方法的研究（3页珍藏版）》请在金锄头文库上搜索。
1、计算机科学2 0 0 2 V 0 1 2 9 N 9 8 ( 增刊)度量空间中索引方法的研究AR e s e a r c ho fI n d e xM e t h o d si nM e t r i cS p a c e周项敏王国仁于戈 ( 东北大学信息科学与工程学院沈阳1 1 0 0 0 4 )A b s t r a c tT h ei n d e xi so n eo ft h ek e yt e c h n o l o g i e si nt h em u l t i m e d i aa p p l i c a t i o n s I nt h i sp a p e r w ep r
2、o p o s ean e wm e t r i ci n d e xn a m e dM + 一t r e e I ti sb a s e do nt h eo t h e rm e t r i ci n d e xs u c ha sm v p t r e ea n dM - t r e e B ya d d i n gt h ek e yd i m e n s i o nt ot h ei n d e xe n t r i e s ，i ti st Or e d u c et h em u m b e ro fd i s t a n c ec a l c u l a t i o n sa
3、 n dI Oa c c e s s e sf o rt h es i m i l a r i t ym a t c ha n dp e r f o r mf i l t e r i n gt w i c ei nt h ei n t e r n a ln o d eo n l yb yd i s t a n c ec a l c u l a t i n g I te n s u r e st h eh i g hs p a c eu t i l i z a t i o nb yr e a s s i g n i n gt h ee n t r i e sb e t w e e nt h et
4、 w i nn o d e s T h ep r e l i m i n a r ye x p e r i m e n ts h o w st h a tt h ek e yd i m e n s i o nh a sag o o df i l t r a t i o nu t i l i z a t i o nr a t i o I ti st Ob ea ne f f e c t i v ew a yo fd e c r e a s i n gd i s t a n c ec a l c u l a t i o n sa n dI Oa c c e s s e s A n a l y s
5、i ss h o w st h a tM + 一t r e ei sa ne f f e c t i v ei n d e xt e c h n i q u e K e y w o r d sM u l t i d i m e n s i o n a li n d e x ，M e t r i cs p a c e ，K e yd i m e n s i o n ，R a n g es e a r c h ，k N N s e a r c h1引言在基于内容的相似性检索技术中，索引技术占有非常重要的地位。建立高效的索引结构始终是一个迫切的任务。近些年来，m e t r i ct r e e s
6、 迅速发展起来，如v p t r e e ，m v p t r e e 3 ，M t r e e 4 3 等。与R 一t r e e系列 1 3 不同，它们考虑对象之间的距离，而不是它们之间的相对位置。这类索引树利用三角不等式关系，缩小查找空间，滤掉不符合要求的数据，达到减少距离计算量的目的。在这篇论文中，我们对v p t r e e ，m v p t r e e ，M t r e e 等一系列m e t r i ct r e e s 以及T V t r e e 2 1 进行了详细的分析，提出了一种新的索引方法M + - t r e e 。M + 一t r e e 是M t r e e ，二元
7、m v p t r e e 以及T V t r e e 的结合，它在M t r e e 的基础上，加入二元m v p t r e e 的两 次过滤思想，且引入了关键维技术和关键维转移的思想。在T V t r e e 中实验表明：在数据分布不均匀的情况下，T V t r e e 的查找效率非常高。实际应用中，图像数据库中图像特征分布通常是不均匀的，且图 像特征中各个维对查询的作用不同，因此引入关键维技术是非常可行的，它对减少距离计算非常有用。我们又设计了M + - t r e e 的结点结构、建树算法、分裂算法、R a n g eQ u e r y 算法及K N N S e a r c h 算法
8、。 由于加入了关键维，中间结点中每个入口项对应两个子结点分支，增加了结点扇出，降低了树的高度。在分裂算法中，为了保证结点不出现下溢，保证空间利用率的高效性，引入了孪生兄弟间数据调整机制，从而在扇出增加的同时，保证分裂的合理性。接着又对该索引结构性能进行分析。 下面介绍相关工作；提出M + - t r e e 的结构以及相关的算法；对M + - t r e e 进行性能分析；最后总结全文。2 相关工作度量空间中的索引方法非常多，其中M t r e e 是目前一种最为理想的索引结构。M + - t r e e 是在M t r e e 的基础上，结合二元m v p t r e e 的两层过滤思想和T
9、 V t r e e 的降维思想，提出的一种新索引技术。它是对M t r e e 的进一步完善。下面介绍与M + - t r e e 密切相关的几种索引方法。v p t r e e 是一种分层的索引结构。在每一层中， 用一个受益点将数据空间分成球形分片。根据入口 项与结点受益点间距离，将结点空间分割为若干子空间。v p t r e e 利用逐步过滤、逐渐缩小查询空间的方法，实现多媒体信息的相似性查询。v p - t r e e 高度较高，距离计算过多。m v p t r e e 改进了v p t r e e 的设计方法，它将受益点由v p t r e e 的一个改进为多个，增加了树的扇 出，大
10、大降低了树的高度，而且，在叶子结点保存了路径和距离信息，减少了查询距离计算，提高了查找性能，但它和v p t r e e 一样，都是静态的索引结构，不能对索引信息进行即时更新，要想保持查询的高效性，必须对索引结构进行定期更新，这是一件非常繁琐的事情。* ) 本文得到教育部高等学校骨干教师资助计划及沈阳市基金资助。周项敏硕士。研究方向为多媒体数据库2 6 5 同以上索引相比，M t r e e 是一种全新的索引结构，它是一种分页的平衡树结构，它采用自底向上的建树方法，引入结点上移和分裂机制，实现了索引结构的动态化，在进行查询时，充分采用三角不等式过滤机制，减少了距离计算。它最早考虑距离计算复杂性
11、，但子空间重叠太多。5M + 一t r e e ：一种新的高维索引方法5 1M + - t r e e 的设计思想 M + - t r e e 的设计思想来源于对二元m v p t r e e 分片方法的改进和对M t r e e 分片方法与结点结构的改进。二元m v p t r e e 利用两个受益点将数据空间 一次分为四个子空间，实现同一中间节点的二次过滤，但m v p t r e e 在同一中间节点需要进行两次距离计算，由于特征的高维性，距离计算的代价非常高， 如果减少在中间节点中同受益点间的距离计算，将查找的主要计算过程放在叶子结点，这将会避免不 必要的距离计算。M + - t r e
12、 e 对二元m v p t r e e 分片方 法的改进在于，它用一次距离计算两次过滤效果替 代了m v p t r e e 中的两次距离计算两次过滤效果。 M + 一t r e e 将对二元m v p t r e e 分片方法的改进 与M t r e e 的动态化结合起来，目的在于保持动态化的特性，减少距离计算的次数。它用一个圆和一个关键维实现在同一中间节点对数据空间的二次过滤，即在不需要增加I O 和距离计算的情况下，再次缩小数据查询空间。 关键维即在距离计算过程中，对相似度影响最大的维。由于数据的空间分布的影响，特征的各个维 对查询影响程度不同，其中方差最大的维对相似度的影响最大，采用方
13、差最大的维进行分裂，既可保持 空间分割的最优化，又可以在利用关键维进行过滤时，增强过滤效果。5 2M + - t r e e 与M t r e e 对数据空间的划分M + - t r e e 与M t r e e 对数据空间的划分的不同 在于：M + - t r e e 一次将数据空间分裂为四个子空间，如图1 ，2 所示。 囫畸囵目图2M + 一t r e e 的空间划分5 5M + - t r e e 的结点结构M + - t r e e 的叶子结点中存储所有需要索引的数2 6 6 据库对象，而中间结点存储的是中间结点对象。中间 结点的入口项结构如图4 所示。其中：O r 为中间结点 对象的
14、特征值，R ( O r ) 为中间结点对象的半径，D( O r ，P ( O r ) ) 为结点O r 与其父结点之间的距离，p t r ( e n t r y ) 为父结点中指向该结点的入口项的地址。D N o 为关键维号，P t r ( T 1 ( o r ) ) 为指向左分支根结点的指针，M t 一为左分支的所有对象中关键维的最大 值，P t r ( T 2 ( O r ) ) 为指向右分支根结点的指针，M 。t n i 。 为右分支的所有对象中关键维的最小值。其中每个 中间结点入口项的左分支中任意对象关键维的值都小于右分支中任意对象关键维的值。IO ，数据库对象特征值lIO l d (
15、 O j )对象标识符ID ( O it P ( O j ) )O ，与父结点间的距离I图3 叶子结点入口项结构图4 中间结点入口项结构5 4M + - t r e e 树结构M + - t r e e 树结构如图5 。其中：矩形为中间结点，黑色的圆形为入口项，每个中间结点入口项对应两个人分支，椭圆形为叶子结点，每个叶子结点入口项对应一个数据库对象。图5M + 一t r e e 总体结构5 5M + - t r e e 的建树过程在建树过程中主要完成对象的插入、结点溢出处理。当O ，插入数据库时，首先由根结点开始，找到 应插入的叶子结点，如该叶子结点为f u l l ，看其孪生 兄弟结点是否满
16、( 同一入口项的左右分支成为孪生兄弟) ，如果未满，则调整两个孪生兄弟结点中对象的分布，并将O ；插入合适的位置，同时修改其父结点中相应的入口项值。否则，进行分裂操作。下面是插入和分裂算法。I n s e r t ( N ：n o d e ，e n t r y ( O - ) ：M + - t r e e e n t r y( 假设N 是结点的所有入口项的集合；i fNi sn o tal e a f 。t h e n l e tN h = e n t r i e ss u c ht h a td ( O ，) O ，；i fN “西t h e nl e te n t r y ( O ? ) N d ( O ? ，O 。) i sm i n i m u m ；e l s e l e te n t r y ( 1 3 , “ ) N ，d ( 0 7 O 。) 为最小值，l e tr ( O ? ) = d (
