（计算机应用技术专业论文）高维数据索引结构研究.pdf

复旦大学博士毕业论文；膏l l 敦撰索引结构研究董道田 摘要 随着互联网和多媒体技术的迅速发展，人们可以访问到的多媒体数据急剧增 长，如何实现多媒体数据对象的相似检索成为一个非常重要的研究课题。通常， 人们利用特征提取算法从多媒体数据对象中提取出特征矢量，然后利用特征矢量 之间距离表示多媒体对象之间相似度。相似性检索的实现就是通过计算查询矢量 与数据库中矢量之间距离以找出满足条件的对象。当数据库中矢量很多时，简单 的顺序扫描搜索将导致极大查询代价，无法满足用户需求。为了有效实现快速相 似性检索，就必须借助于高效的高维数据索引结构。 在最近几十年中，人们提出了很多高维数据索引结构，其中大多是树形结构， 如r - t r e e 、r - t r e e 等，这些索引结构在维数升高时性能会急剧下降，即所谓的 “维数灾难”，为此，有人提出了通过近似压缩矢量来减少磁盘i o 代价的 v a - f i l e ，但仍不能为高维数据的相似性检索提供良好的查询性能。针对高维数 据索引结构的现状，我们在该领域进行了深入研究，取得了一定的成果。 首先，我们提出了四种新的索引结构：1 ) a n g l e - t r e e ：用高维空间中单位超 球面上的超弧对空问进行划分，并借助于树形结构实现索引，可有效支持以矢量 之间夹角余弦为相似度度量的查询方式；2 ) v a r - t r c e ：将k f i l e 与r - t r e c 有 机结合起来，用r - t r e e 来管理和组织近似矢量数据，并借助r t r e e 类相似查询 算法实现基于、强r t b e 的查询：3 ) v a - t r i e ：利用t i l e 结构来索引、，a f i l e 中 近似矢量，有效实现了高维数据的相似性检索；4 ) o f j l c ：将v a - f f l e 中近 似矢量插入到近似文件中合适位置，使得在高维空问中相邻数据尽量存放在近似 文件的相近位置上，从而在查询过程中仅访问部分近似矢量，就可快速得到质量 很高的相似查询结果。 其次，在高维数据索引结构研究基础上，本文分别给出了基于v a - f i l c 和 o v a - f i l e 的、以高维矢量序列为查询对象的视频片断相似查询方法，以有效利 用高维索引结构同时支持视频信息检索中的镜头检索和视频片断检索。 最后，结合一个实际的多媒体信息检索系统，进一步阐述高维索引结构在实 际系统中的应用。我们利用o v a - f i l e 管理来自于海量视频数据的高维矢量，基 于镜头和视频片断相似查询模型实现了视频数据的快速相似性检索。 关键字：信息检索、索引结构、相似查询、多媒体数据库 中图分类号：t p 3 1 1 1 复旦大学博士毕业论文高赡t 据囊弓l 结构研究 董道墨 t o d a y , m o l ca n dm o r em u l t i m e d i ai n f o r m a t i o ns o u r c c sa r ea v a i l a b l ei nd i g i t a l f o r md u et ot h ed e v e l o p m e n to fc o m p u t e ra n di n t e r n e t mi s s u et os p e e du pt h e s i m i l i a r i t yq u e r yo fm u l t i m e d i ao b j e db e c o m e sm u c hi m p o r t a n t m o s t l y , s i m i l a r i t y c a l ln o tb em e a s u r e do nt h em u l t i m e d i ao b j e c t sd i r e c t l y , b u tr a t h e r , o na b s t r a c t i o n so f o b j e c t st e r m e df e a t u r ev e c t o r s t h ed i s t a n c e so fw h i c ha r cu s e dt or e p r e s e n tt h e s i m i l a r i t y t h eb r u t ef o r c ea p p r o a c hf o rs i m i l a r i t yq u e r yi st os e q u e n t i a l l ys c a oa l lt h e f e a t u r ev e c t o r s i nt y p i c a lm u l t i m e d i aa p p l i c a t i o n s ，d a t a b a s e su s u a l l yc o n t a i nal a r g e n u m b e ro ff e a t u r ev e c t o r s ，a n ds e q u e n t i a ls c a nw i l li n c u re x t r e m e l y h i g hd i s kf oc o s t m a n yi n d e xs t r u c t u r e sh a v eb e e np r o p o s e dt os o l v et h i sd i f f i c u l tp r o b l e m ，s u c h a sr - t r e ea n di t sv a r i a n t s ，v a - f i l e ，p y r a m i d - t e c h n i q u ee t c f r o mt h e p u b l i s h e d r e s u l t s ，i tc a nb ec o n c l u d e dt h a tm o s to ft h e s em e t h o d sc o u l da c h i e v eg o o dq u e r y p e r f o r m a n c e w h e nt h e d i m e n s i o n a l i t y i sl e s st h a n2 0 h o w e v e l ，t h e q u e r y p e r f o r m a n c ew i l ls u f f e rg r e a t l ya st h ed i m e n s i o n a l i t yi n c r e a s e s ，w h i c hi ss o - c a l l e d “t h ec i l r s eo fd i m e n s i o n a l i t y ， i nt h i s d i s s e r t a t i o n ，w ef i r s t i n t r o d u c e df o u rn o v e l h i g l a - d i e m s i o n a l i n d e x s t r u c t u r e st oo v e r c o m et h ec u r s eo fd i m e n s o n a l i t y ：1 ) a n g l e - t r e e ，w h i c hc a ns u p p o r t t h ek i n do fs i m i l a r i t ys e a r c hw h o s es i m i l a r i t yi sm e a s u r e db yt h ec o s i n eo ft h ea n g l e b e t w e e nt w ov e c t o r s ；2 ) v a r t r e e ，w h i c hi n t e g r a t e s 、，a f i l ea n dr - t r e e , a n d e m p l o y sr t r e et om a n a g ea p p r o x i m a t i o nv e c t o r s ；3 ) v a - t r i e ，t h ek e yi d e ab e h i n d w h i c hi s a d o p t i n g t h ei d e ao fq u a n t i z a t i o nt oc o m p r e s st h ev e c t o r sa n dt h e n e m p l o y i n gt h et r i es t r u c t u r et oo r g a n i z ea n dm a n a g et h ea p p r o x i m a t i o n s ；4 ) o v a - f i l e ， w h i c hi n s e r t st h ea p p r o x i m a t i o n so f 嫒麟i n t oas u i t a b l ep o s i t i o ns ot h a tt h e a p p r o x i m a t i o n sc l o s et oe a c ho t h e ri nd a t as p a c ea r ep l a c e di nn e i g h b o r i n gp o s i t i o n s o fa p p r o x i m a t i o nf i l e b a s e do nv a - f i l ea n do v a - f i l e , w ep r o p o s e dt w of a s t v i d e o ：l i pq u e r y a l g o r i t h m s ，w h i c he n a b l ev a - f i l ea n do v a - f i l et os u p p o r tb o t hv i d e os h o ts i m i l a r i t y q u e r ya n dv i d e oc l i ps i m i l a r i t yq u e r y f i n a l l y , w ep r e s e n t e dt h ea p p l i c a t i o no fo u rp r o p o s e di n d e xs t r u c t u r eo v a - f i l e i nam u l t i m e d i ai n f o r m a t i o nr e t r i e v a ls y s t e m ，w h i c hh a sb e e np u ti n t op r a c t i c a lu s e i n t h i ss y s t e m ，o v a - h i ew a se m p l o y e dt om a n a g ea n di n d e xl a r g es c a l eh i g hd i e m s i o n a l f e a t u r ev e c t o r se x t r a c t e df r o mv i d e od a t a b a s e k e y w o r d s ：i n f o r m a t i o nr e t r i e v a l ，i n d e xs t r u c t u r e ，s i m i l a r i t yq u e r y , m u l t i m e d i a d a t a b a s e 复旦大学博士毕业论文膏睡段据素引结构研究 董道田 1 1 研究背景及意义 第一章简介 随着高速传输和高效存储技术的发展大量信息以计算机可读的形式存在， 其中不仅包括文字和声音，更主要的是图形、图像和视频等多媒体视觉信息。面 对日益增多的可访问到的多媒体信息，为了不迷失在其中，人们往往会提出快速 查询的需求，例如： 数码相机的普及，使我们可以浏览到大量的各种各样的图像，而当某用 户需要一些“太阳从海平面上升起”的图片时，简单的通过测览的方式 得到这些图片必将花费大量的时间和精力，此时用户可能希望通过提交 一幅该内容的图片以查询到与其相似的图片，以快速得到结果： 通过各种途径可访问到的数字电视节目日益增多，人们总希望从中快速 得到自己感兴趣的节目，例如有人希望通过提交一幅n b a 的比赛图片快 速查找到近期内所有n b a 比赛节目：而另一些则希望获得所有近期与美 国白宫有关的新闻片断。 类似的查询请求还有很多，它们被通称为相似性检索，即从数据库中查找出 与给定的查询对象最为相似的一些( 或一个) 对象。当数据库的数据量很大时， 如何实现快速的相似性查询成为多媒体信息检索等应用领域的关键问题。 对于多媒体信息，计算机很难像人类一样判断多媒体对象之间是否相似，因 此人们往往需要从多媒体对象中提取其特征，不同的应用中所采用的特征不尽相 同，但大都是一个高维的矢量，即所谓的特征矢量，这些特征矢量之间的距离被 用来近似表示多媒体对象之间的相似程度。利用特征矢量实现相似查询最简单、 最直接的方法是顺序扫描( s c a n ) ：即依次读取特征数据库中的每个特征矢量 并计算与查询矢量之间的距离，选择符合条件的矢量所对应的对象作为查询结 果。然而当特征矢量数据量较大时，整个特征数据库就必须存储在磁盘中，因此 s c a n 算法需要耗费大量的磁盘开销和c p u 计算代价，难以满足用户对查询响 应时间的要求，为了能够快速有效的实现高维矢量的相似查询，必须借助于高效 的索引结构及查询算法。 自2 0 世纪7 0 年代开始，随着c a d 、g i s 及医药影像等应用的出现，逐渐提出 对多维数据和高维数据相似查询的需求，对于高维数据，由于其自身的无序性、 复且大学博士毕业论文：毫鞋致据童引结构研究蕾道田 复杂性等特点，使得b + 1 m 等传统关系型数据库中的索引结构无法适用，为此 人们开始了高( 多) 维数据索引结构的研究，在过去的几十年中，大量的高维数 据索引结构被相继提出，其中大都为树形索引结构，如k - d - t r y i 、k - d - b t r e e 2 、 r - t r e e 3 、r + - t r e e 4 、r 。- t r e e 5 、s s - t r e e 6 、s r - t r e e 7 、x - t r e e 8 、t v - t r e e 9 】、 i q - t r e e 1 0 、a - t r e e 1 1 等，但当数据维数较高时，它们都很难表现出令人满意 的查询性能，即面临所谓的维数灾难。除了树形结构外，v a - f i l e 1 2 】、l p c f i l e 1 3 】 等采用了量化压缩的方法来减少查询过程中的磁盘访问代价，但其近似文件仅仅 是近似矢量的简单排列，其查询性能加速限制在很小的范围内，仍难以满足实际 应用的需要。 多媒体信息的海量以及人们对多媒体信息检索需求的急剧增大，使得快速的 相似性检索显得日益重要，面已有的高维数据索引结构仍难以满足实际应用的需 要，为此，深入的进行高维数据索引结构及相关的相似性查询算法的研究具有重 要的研究意义和实用价值。 1 2 研究目标及主要贡献 正如前面所述，面对目前海量的多媒体信息及检索应用，已提出的索引结构 仍难以满足实际需求，本文就是在此背景下，通过以下几个研究思路以期望提出 更为有效的高维数据索引结构及相应的查询算法： 不同的应用场合下，高维矢量的相似度度量方法不尽相同，我们试图提 出一些索引结构班支持尚未有索引结构支持的相似度度量方法； 将r - t r e e 类索引结构与v a f n e 中提出的近似矢量的想法结合起来，以 期同时拥有两类结构的优点； 用传统的结构，如t i l e ，来管理v a - f i l e 中的近似矢量，以大大提高查询 性能： 将、，a f i l e 中的近似矢量采用特定的插入算法，使得在高维空间中相邻 的矢量尽量存储在近似文件的相邻位置，在查询时通过仅访问部分近似 矢量就可得到查询结果。 在上面这些研究思路的指导下，本文提出了数种高效的、新的高维数据索引 结构，并将其中的一些结构应用于实际系统之中。下面是本文的主要贡献： 1 ) 提出a n g l e t r e e ，以支持以矢量夹角余弦为相似度度量的相似查询： 2 ) 利用r t r e e 类结构管理v a f i l e 中的近似矢量，提出v a r t r e e ： 2 复且大学博士毕业论文t 膏i 数据素引鳍构研究董道田 3 ) 利用陆管理v a - f l l e 中的近似矢量，提出v a - t r i e ； 4 ) 对v a - f i l e 中近似矢量的存储顺序进行有效组织，提出o v a - f i l e ； 5 ) 在o f n e 和o v a - f i l e 基础上，实现视频片断( 由多个特征矢量组成查 询对象) 的相似检索； 6 ) 开发出一实用的多媒体信息检索系统，并将高维数据索引结构应用其中。 1 3 论文结构及主要内容 本文主要介绍本人在高维数据索引结构领域的研究成果及应用，将按照以下 结构组织和论述： 第一章简介：主要阐述高维数据索引结构的研究背景及意义，以及本文的主要 研究目标和贡献，并给出文章的结构： 第二章高维数据索引结构综述：系统论述了耳前高维数据索引结构研究的现 状，包括高维数据的特点、高维索引结构的特点、高维数据的相似性查 询、矢量空间索引结构和度量空间索引结构，从该章的叙述中可对高维 数据索引结构的研究有个清晰的了解； 第三章高维数据索引结构研究：详细介绍了本人在该领域的研究成果，包括四 种索引结构a n g l e - t r e e 、v a r t r e e 、v a - t r e e 及o v a - f i l e 。 第四章基于高维数据索引结构的视频片断检索方法研究：在索引结构v a - f i l e 和o v a - f i l e 的基础上，提出了两个实现以高维矢量序列作为查询样本 的视频片断检索算法； 第五章高维数据索引结构应用：描述了一个已经进入实际应用的多媒体信息检 索系统。并着重介绍了高维索引结构在其中的应用。 第六章总结和展望：这部分对本文的工作进行了总结，介绍了本文的创新之处 以及下一步工作的研究思路。 3 复旦大学博士毕业论文：高维数据索引结构研究董道国 第二章高维数据索引结构综述 近年来，商维数据库的应用得到快速的发展，如海量的多媒体数据库、生物 信息学中庞大的d n a 数据库等，这些信息一般使用特征抽取等方法映射为高维 数据，然后通过计算这些高维数据之间距离实现相似性查询。例如，对于图像数 据，往往采用颜色直方图来表征一幅图像，当需要从数据集查找到与给定图像相 似的图像时，通过计算颜色直方图之间的距离实现查询。在这种背景之下，高维 数据索引结构和适用于高维索引结构的相似查询算法得到了人们的极大重视，而 在已提出的众多高维索引结构中，有的特定工作在向量空间中，而有的是针对度 量空间而设计。在本章我们将对高维索引结构研究的现状进行较为详细的介绍， 包括：高维数据及商维索引结构的特点、高维数据库的查询方式、向量空间与度 量空间中高维索引结构的异同及它们中有代表性的索引结构简介、以及相似性查 询算法等。 2 1 高维数据及索引结构的特点 所谓高维数据，是指高维空间中的数据，例如二维空间中的点、线段、矩形， 三维空间的球、立方体以及高维空间中的点数据等。一般来说，高维数据有以下 一些特点 1 4 ： 1 ) 复杂的结构：对于高维数据，它有可能是一个高维空间的点数据，也有 可能是复杂的多边形或多面体，一般不能象传统的关系型数据库一样用 固定大小的条目来保存。 2 ) 动态的特性：在插入和删除的过程中，还往往伴随着对数据本身的修改。 3 ) 数据的海量：高维数据库往往是比较大的，例如，一般的地图大概需要 几千兆字节的存储空间。 4 ) 多样化的操作：对高维数据库而言，没有标准操作，往往要根据实际应 用的需要确定。 5 ) 时间代价大：尽管对高维数据库的操作所花费的时间各不相同，但一般 远高于传统的关系型数据库的操作。 6 ) 不能排序：无法对空间数据进行线性排序以使得那些在高维空间中相邻 的数据仍然能够相邻。 4 复且大学博士毕业论文；高维数据素引结构研究 董道圈 正是由于高维数据具有以上各种特点，所以要求索引结构也相应具有以下一 些特征 1 4 ： 1 ) 动态构造：由于数据可以在数据库以任意顺序插入或删除，其索引也应 该与之保持一致，即索引结构也必须支持动态的插入和删除。 2 ) 3 ) 4 ) 5 ) 6 ) 7 ) 二级三级存储管理：尽管主存容量日益增大，仍不能将一个完整的数 据库保存在主存中，因此索引结构要充分考虑到二级以及三级的存储管 理。 支持尽量多的操作：不能以牺牲其它的操作而支持某一种特定的操作。 独立于输入数据及插入顺序：支持各种高维数据以及任意的插入顺序。 可增长性：索引结构要能够适应数据库大小的增长。 时间的有效性：查找速度必须是快速的。 空间的有效性：一个索引结构相对于其原数据应是比较小的，要保证一 定的空间利用率。 8 ) 并行性及可恢复性。 2 2 高维数据查询方式 根据应用领域豹不同，高维数据库的查询方式也各不相同。对于给定的数据 库d b ，常用的查询方式有 1 4 ： 1 ) 精确匹配查询( e m q ：e x a c tm a t c hq u e r y ) ：对于给定的查询数据q ，从 d b 中找出所有与q 相同的数据： e m q ( q ) 一 d d 田1 0 一g 。 2 ) 点查询( p q ：p o i n tq u e r y ) ：给定点数据q ，从数据库中找出所有包含 点q 的数据： p q ( q ) d e d b i q n o ；口 。 3 ) 窗口查询( w q ：w i n d o wq u e r y ) ：给定一个d 维的矩形查询区闻 ，。= 【，“- 】【f ：，z 】儿，“，从数据库中找出至少包含个i 中的点 的所有数据： 5 复旦大学博士毕业论文t 高簟数据索引结梅研究 董进田 朋( j 。) 一 o n b i j 。n d - 升。 4 ) 相交查询( i q ：i n t e r s e c t i o nq u e r y ) ：给定具有一定形状的空间数据q ， 从数据库中找出至少包含q 中一点的所有数据： 垃( 窜) - o 珊j q n o _ 升。 5 ) 包含蠢询( e q ：e n c l o s u r eq u e r y ) ：给定查询数据q ，从数据库中找出 所有包含q 的数据： e q ( q ) 。 o e d b i q n o ；g 。 6 ) 被包含查询( c q ：c o n t a i n m e n tq u e r y ) ：给定查询数据q ，从数据库中 找出所有被q 包含的数据： c q ( q ) 一 d e d bj q n oi d 。 7 ) 邻接查询( a q ：a d j a c e n c yq u e r y ) ：给定查询数据q ，从数据库中找出 所有同q 邻接的数据： a q ( a ) - 口e d b i q n o _ 咖a g n o 一妒) 其中q 、0 分别表示q 和0 的内部区域。 8 ) 范围查询( 聪：r a n g eq u e r y ) ：给定查询数据q 与查询距离门限t ，从 数据库中找出所有与q 距离小于t 的数据： r q ( q ，t ) - o e d s l l l o - q l l s n 。 9 ) k - 近邻查询( k n n q ：kn e a r e s t - n e i g h b o ro u e r y ) ：给定查询数据q 及正 整数k ，从数据库中找出距离q 最近的k 个数据： k 栅q ( q ，七) 一 d o 。d 。e d b i v e e d b o o o k 。) ，l b q l l 墨l b 一鼋l l ，o f 七一l 当k = l 时，又称为最近邻查询。 在上面所述的几种查询方式中，范围查询和k 近邻查询的应用最为广泛，统 称为“相似性查询”，因此目前高维数据索引结构的研究主要集中在如何快速实 现相似性查询上面，尤其是k 近邻查询。 复且大学博士毕业论文：膏堆赫誊弓i 姑构研究董道田 2 3 向量空间与度量空间索引结构及其异同点 对于高维数据索引结构，根据构建索引结构中所采用的数据信息及相似度量 的方法不同，可分为向量空间索引结构和度量空间索引结构向量空间和度量空 间索引结构有着不同的侧重点，但也有相通之处，它们的异同简单总结如下： 1 ) 向量空间可被看作是带有坐标信息的特殊的度量空间。在一定条件下， 这两类空间是可以相互转换的：快速映射算法( f a s t m a p ) 【t 5 就是一 种将度量空间中的对象转换为具有低维坐标的向量空间中的点的算法； 而当我们在向量空间中定义好一个距离函数而只取物体之间的距离信息 时，就将向量空间转换成了度量空间。因此不难看出，在度量空间中的 索引结构比在向量空间中具有更普遍的适用范围，所用到的信息更少， 难度也会更大。 进行相似性查询时，在度量空间中算法执行的主要代价被认为是计算距 离函数的c p u 代价，因此度量空问索引结构主要考虑的减少距离函数的 计算次数；而在向量空间查询的主要代价被认为是读取磁盘的i o 代价， 向量空间中的索引结构主要考虑的是减少磁盘的i o 次数。 3 、在度量空间索引结构中，为了实现相似性查询，所唯一用到的方法就是 距离函数的三角不等式性质；而在向量空间中除了利用距离函数外，更 主要的可利用信息是数据的坐标信息。因此，在向量空间中的索引结构 上设计查询算法时，比在度量空间中具有更大的灵活性，因为它不仅可 以利用距离信息，还可以利用物体的位置( 坐标) 信息，比如普遍使用 的k - d - b - t r e e 2 1 、r t r c c 3 l 等，它们都广泛使用了数据坐标信息。 在本章的余下部分中，我们将分别对向量空间索引结构和度量空间索引结构 分别加以详细的描述。 。 2 4 向量空间高维索引结构 2 4 1 向量空间高维索引结构分类 在近几十年对向量空间高维数据索引的研究过程中，已经提出了大量的索； 结构，如图2 1 所示。根据这些索引结构的特点分类如下： 7 似蟋噬撼岛嚣姆示酶孵籁枢厘科嘲唇【n匝 复旦大学博士毕业论文t 南嘲t 据囊引蛄梅研究董道置 1 ) 根据处理数据的类型，可以分为点数据类和空间数据类。点数据类是指 那些只能处理点数据的索引结构，如k - d - t r e e 1 、t v - t r e e 9 等：空 间数据类指既能处理点数据，又可以处理线、矩形等具有一定形状的数 据的索引结构，如r - t r e e 3 、r * - t r e e 4 等。 2 ) 根据索引刨建时数据组织形式，可以分为静态结构类和动态结构类。静 态结构类是指用批处理的方式将全部数据构建成索引，不能支持动态的 插入和删除，如p a c k e dr - t r e e 1 6 ：而动态结构类指数据依次插入而 生成的索引结构，如动态r t r e e 4 、动态r * - t r e e 5 3 等。 3 ) 根据划分方法的不同，可以分为数据划分方法类、空间划分方法类以及 混合型划分方法类。数据划分方法是根据数据所在的位置进行层次划分， 如r - t r e e 4 等；空间划分方法则是将整个数据空间逐渐划分为互相邻 接的子空间，如k - d t r e e 1 等。混合型是指既根据空间进行划分又根 据数据进行划分，如h y b r i d t r e e 1 7 等。 4 ) 根据索引的组织形式，可以分为树形结构类和非树形结构类。树形结构 类指索引结构是按照树的形式组织，如k - d t r e e 1 、r - t r e e 4 等；非 树形结构类如v a f i l e e l 2 等。 5 ) 根据目录节点的形状，可以分为矩形、球形和混合形。在构造索引结构 的时候，目录节点形状的选择直接影响检索的效率，选择为矩形的有 k - d - t r e e 、r - t r e e 、r + t r e e 等；选择为球形的有s s - t r e e 6 】、t v - t r e e 9 】 等；将矩形和球形结合起来的称为混合形，如s r - t r e ：1 7 i 等。 2 4 2 几种代表性的向量空间高维数据索引结构 r - t r e e 类的索引结构类似于b - t r e e ，一般都具有层次性的数据结构，最先出 现的r - t r e e 类索引结构是在1 9 8 4 年由g u t t m a n 提出的r t r e e 4 。此后人们对它 的算法和结构进行了一些改进，不过大多都保持了与r - t r e e 相同或类似的结构 特点。 2 4 2 1 1r - t r e e r - t r e e 是一种平衡树，具有类似于b t r e e 的层次结构。在r - t r e e 中存放的 数据并不是原始数据，而是这些数据的最小外接矩形( m b r ) ，它具有以下的一 9 复且大学博士毕业论文t 膏雏散括索引螭构研究 董道嗣 些性质： 如果用m 来表示一个节点中可存放的项数目的最大值，用n l ( m m 陀) 来表示一个节点中可存放的项数目的最小值，则除了根节点外，每个节 点中必须包含m m 个项。 根节点中至少要包括两个项，除非它是个叶子节点。 节点中的每个项的结构为( r e c t ，p o i n t e r ) ，在内部节点中，r e c t 是其子节 点中所有数据的m b r ，p o i n t e r 指向该子节点：在叶子节点中，r e c t 是实 际数据的m b r ，p o i n t e r 指向实际数据存放的位置。 所有的叶子节点出现在同一层上。 图2 2 是一个简单r t r e e 的例子。它反映了r - t r e e 的结构特点。 臼一粤量 图2 2 ：r t r e e 的例子 r - t r e e 的查找算法类似于b 。t r e e 。它是从根节点出发，对内部节点，检查其 每一个项是否与要查找的区域相重叠，如果重叠的话，则查找该项所指向的子节 点，直至查找到叶子节点。由于在r - t r e e 中存放的是m b r ，这些m b r 可能相 互重叠( 如图2 中的a 和b ) ，所以无法保证查找操作只搜索一个路径即可成功， 在最坏的情况下，次查找操作可能要遍历所有的路径。 向r - t r e e 中插入一个数据，实际上是插入该数据的m b r 。和查找操作不同 的是，一次插入操作只需要遍历一个从根节点到叶子节点的路径，首先从根节点 开始，在经过的每一个内部节点中选择这样的项：它所指向的子节点为了包纳下 要插入的数据其m b r 的面积需要扩大的最小，如果出现相同的情况，则选择 m b r 最小的一个。当到达叶子节点后，如果该节点中还有剩余的空间，就将数 据插入到节点中，并按原路径返回，依次修改其祖先节点中相应项的m b r ：假 如在叶子节点中已经没有足够的空间存放下要插入的数据，则要发生分裂，生成 一个新的叶子节点，并在其父节点中插入一个指向新叶子节点的项，如果在其父 节点同样出现了溢出，也要产生分裂，如此下去直至根节点，如果根节点也发生 1 0 囝口 圆 一k 曰 | 复里大学博士毕业论文：膏维数据索引结构研究董道田 了分裂，则生成一个新的根节点，树的高度增加1 。 要在r - t r e e 中删除一个数据，首先要进行一次精确查询操作，如果找到了 该数据，则从节点将其删除，在删除之后如果节点中有足够的项( 即项数目不小 于m ) ，就依次修改其祖先节点中相应项的m b r ，删除结束；如果在删除后节点 中项的数目小于1 1 2 ，则将该节点所有的硬保存到一个临时缓冲区内，并将该节点 从树中删除，如果节点删除后影响到其父节点也出现相同的情况，则也要做相同 的操作，如此直至根节点，然后再将l f 缶时缓冲区内所有的项重新插入到树中。如 果在删除完成之后根节点只有一个子节点的话，则这个子节点就成为新的根节 点，树的高度减1 。 2 4 2 1 2 其它几种r t r e e 类索引结构 r t t r e e 【5 】：r - t r e e 对r - t r e e 的插入算法和分裂算法进行了一些改进， 主要体现在以下两点：第一，提出了强制重新插入的概念，即当一个节 点在插入过程中发生了溢出，并不急于进行分裂，而是首先看一下该层 节点在这次插入过程中有没有进行过重新插入，如果没有的话，则选择 一定比例的项从该节点中删除并重新插入到树中，而如果该层已经有节 点进行过重新插入，才对该节点进行分裂；第二，当节点进行分裂的时 候，不仅要考虑分裂后两个新节点的面积，还要考虑分裂后节点周长以 及该层节点的重叠面积等因素。 x - t r e e 8 ：x - t r e e 中引入了超节点的概念，当节点发生溢出的时候，首 先考虑对节点选择合适的分裂算法，以使节点分裂以后重叠区域小到一 定程度，假如无法避免分裂后出现较严重的区域重叠，则不分裂节点， 而是扩大节点大小以放入更多的项，形成超节点。 s s - t r e e 6 ：s s - t r e e 中采用超球代替了原来的进行数据划分的超矩形， 以更好的支持相似性查询。 s r - t r e e 【7 】：它是在分析了超矩形和超球两种不同的数据划分方法的优缺 点后，将两者结合起来，形成了s r t r e e ，从而取得更好的性能。 2 4 2 2 网格文件类 2 4 2 2 1 网格文件： 网格文件 1 8 1 是一种典型的基于哈希的存取方式，它是由包含着很多与数据 桶相联系的单元的网格目录来实现的，一般个数据桶为硬盘上一个磁盘页。每 1 1 复旦大学博士毕业论文t 毫触据素引蛄构研究董道田 个单元只对应着一个数据捅，而一个数据桶往往可以包含着几个相邻的单元。随 着数据的增多，网格目录可能会慢慢变大，所以往往将其保存在硬盘上，但为了 保证在进行精确查询的时候能仅用两次i o 操作就可找到相应的记录，一般将网 格本身保存在主存中，网格是用d ( 数据的维数) 个一维的数组来表示的，这些 数组称为刻度。当我们进行精确查询的时候，首先用这些刻度来定位包含要查找 的记录的单元，假如这个单元不在主存中，那么将进行一次i o 操作，将这个单 元从硬盘调入主存，在这个单元中包含着一个指向可能找到记录的页的指针，取 这个指针所指的页又需要一次f o 操作。而对于范围查询，需要检查所有与要查 询的区域相交的单元。图2 3 就是一个网格文件的例子。 y 刻度 习 图2 3 ：网格文件的例子 当向网格文件插入一个数据的时候，首先要进行一次精确查询以确定该数据 项应当插入的单元以及对应的数据页( 数据桶所存放的磁盘页) 。如果在这个页 中还有足够的空间的话，将数据插入即可。假如已经没有足够的空间，则要根据 与该页相联系的单元的数目来决定处理的方法，当有几个单元指向该页的b i 候， 则检查现在的刻度中是否有合适的超平面能够成功的将该页分开，如果有的话， 就产生一个新的页并根据这个超平面将数据分配在两个页中：如现存的超平面没 有合适的，或者只有一个单元指向该页时，我们将引入一个新的超平面并产生一 个新的页，然后根据这个超平面将数据分配，同时要将这个超平面插入到相应的 刻度中，而所有与此超平面相交的单元也要发生分裂。 在网格文件中删除一个数据，也要先进行一次精确查询确定该数据所在的单 元及对应的数据页，并将其删除。假如在删除之后，这个页中存储的数据低于了 一定的数目后，我们需要做相应的处理，根据当前刻度对空间的分隔情况，或者 复旦大学博士毕业论文t 鸯赡靛据童引结构研究 董道置 选择同其相邻的页合并，或者选择将刻度中的一个超平面取消。 2 4 222 其它几种网格文件类索引结构： 与网格文件类似的还有e x c e l l 、两层网格文件以及“t w i n ”网格文件等： e x c e l l 1 9 与两格文件不同之处在于其所有的网格单元是相同大小 的，因此它的每次分裂都将导致目录大小的成倍增长。 两层网格文件【2 0 1 的基本思想是再增加一个网格文件，形成两层网格来 管理目录，其中第一层被称为根目录，它是第二层目录的一个大致描述， 它具有指向第二层目录的指针，而第二层才是真正的目录，它包含有指 向数据页的指针。这种结构的好处是，当发生分裂的时候，所产生的影 响被限制在第二层目录的范围内，从而没有过多影响其它数据。 “t w i n ”网格文件【2 1 1 也是引入了另外一个网格文件，不过与两层网格文 件不同的是，这两个文件的关系是对等的，而且每个文件都覆盖了整个 空间，数据在这两个文件中的分布是动态的，当在插入过程中某个文件 的单元所指向的页出现溢出的时候，将在这两个网格文件之间重新分配 数据。 2 4 2 3k - d t r e e 类 k - d - t r e e 1 是- - 种在k 维空间中的二叉查找树，它主要存储的是点数据，在 每一个内部节点中，它用一个k - 1 维的超平面将节点所表示的k 维空间分成两个 部分，这些超平面在k 个可能的方向上交替出现，而且在每一个超平面中至少要 包括一个点数据，图2 4 就是一个k - d - t r e e 的例子。 j i g 图2 4 ：k - d t r e e 的例子 复且大学博士毕业论文：赢蟾数据索引结构研究 董道田 在k - d - t r e e 的查找和插入操作是很简单的，而删除操作则有点复杂，因为一 个点的删除可能会导致它的子树的重建。由于k d t r e e 只能处理点数据，我们对 其它具有一定形状的数据只好用它们的中心点来代替。需要指出的，当数据插入 的顺序不同的时候，k - d - t r e e 的结构也不同，而且数据会分散出现在树的任何地 方，而不是仅出现在叶子节点上。 2 _ 4 2 3 2 其它几种k d - t r e e 类索引结构： a d a p t i v ek - d - t r e e 2 2 ：它对k - d t r e e 的结构做了少许改变。在分裂 的时候选择合适的超平面使分裂后的两部分包含相同数量的数据，而且 在这些超平面上不一定非要包含数据以及它们的方向也不一定严格的在 这k 个可能的方向上交替出现。在这种结构里，内部节点表示的是分裂 的超平面，所有的数据都出现在叶子节点中，每个叶子只能包含一定量 的数据，当超过这个数量的时候要发生分裂。 k - d b t r e e1 2 ：它是将a d a p tiv ek - d t r e e 同b - t r e e 的特点结合到了 一起，首先，它采用了a d a p t i v ek - d - t r e e 树中的用超平面来划分节点 中的空同的方法，不过对于个内部节点所表示的空间，可以用多于一 个的超平面来划分，形成了几个相邻的子空间，每个子空间对应着一个 内部节点，所有的数据均存储在相应的叶子节点中。从图2 5 中可以看 出，它的结构类似于b - t r e e ，不过在k - d b - t r e e 中不能保证最小空间 利用率。 d； 。二 c 。i 。 一 f ；q ： r b ! k “ c ii 2 4 2 4q u a d t r e e 类 图2 5 ：k - d b t r e e 的例子 同k d - t r e e 类似，q u a d t r e e ( 2 4 也是用超平面的方法来划分整个空间的，不 过不同的是，q u a d t r e e 不再是二叉树，在维数为k 的空间中，每一个内部节点 具有2 。个孩子，每个孩子对应着一个子空间。例如，对于一个在二维空间的 1 4 复里大学博士毕业论文t 南赡t 器索引嫱梅研究董道田 q u a d t r e e ，每个内部节点拥有4 个孩子，每个孩子对应着一个矩形，这四个矩形 一般用n w 、n e 、s w 队及s e 来表示( n w 表示西北方向的那个矩形) 。用这种 方法将整个空间逐渐划分到每一个矩形中所包含的数据的个数低于一定的数目 为止，显然这样得到的o u a d t r c e 不能保证是平衡树，在数据比较密集的地方树 的深度将高于其它的地方，如图2 6 所示。 q u a d t r e e 的查找操作类似于普通的二叉查找树，在每一层中我们要从四个 中选择要继续查找的予树，对于点查询，只需要选择其中的一个合适的就行了， 而对于范围查询可能需要几个。按照这个方法递归执行下去直到查找到了树的叶 子节点为止， 图2 6 -q u a d t r c e 的例子 p o i n tq u a d t r e e 2 4 ，2 s 是q u a d t r e e 的一个变种，它是由点数据一个接一个 的连续插入而构造出来的，对于每一个点，我们首先进行一个点查找操作，假如 我们没有在树中发现这个点，我们就将这个点插入到刚才的查找操作终止的叶子 节点，而这个节点所表示的区域以新插入的点为中心分为2 。个子空间。如果想 从p o i n tq u a d t r e e 中删除一个点的话，则会引起相应的子树的重建，一个简单 的方法是将所有子树上的数据重新插入。图2 7 是一个p o i n tq u a d t r e e 的例