（计算机软件与理论专业论文）基于边界区域分离的高维点数据索引研究.pdf

山大学硕十论文矩于边界区域分离的高维点数据索9j 研究 摘要 在基于内容的多媒体信息检索中，人们利用特征提取算法从多媒体对象中提 取出特征矢量，然后利用特征矢量之间的距离衡量多媒体对象之间的相似度。相 似性检索的实现就是通过计算查询矢量与数据库中矢量之问距离以找出满足条 件的对象。当数据库中对象很多时，简单的顺序扫描将导致极大查询代价，无法 满足用户需求。为了有效实现快速相似查询，就必须借助于多维数据索引结构。 为了有效索引多维数据，人们进行了大量研究，提出了众多的索引结构，例 如r - t r e e ，r 一t r e e ，x - t r e e ，s r t r e e ，s s t r e e 等，这些索引结构在低维 空间中性能很好，但是，在高维空间中，性能急剧下降，甚至不如顺序查询，这 种现象被称为“维数危机”。 为了解决“维数危机”，本文提出了种基于边界区域分离韵高维索弓l 结构， 实践证明，该索引结构在高维空间中有着良好的性能。 关键字：基于内容索引结构高维相似查询维数危机 山大学硕+ 论文 堪丁边界区域分离的高维点数撕索引研究 a b s t r a c t i nt h ep r o c e s so fc o n t e n tb a s e dm u l t i m e d i ai n f o r m a t i o nq u e r y , w ea b s t r a c t f e a t u r ev e c t o r sf i o mm u l t i m e d i ao b j e c t s t h ef e a t u r ev e c t o r sa r eu s e dt or e p r e s e n tt h e s i m i l a r i t yb e t w e e nm u l t i m e d i ao b j e c t s w ea c h i e v es i m i l a r i t yq u e r yb yc o m p u t i n gt h e d i s t a n c eb e t w e e nq u e r yv e c t o ra n dv e c t o r si nd a t a b a s e w r h e nd a t a b a s ec o n t a i n sa l a r g en u m b e ro ff e a t u r ev e c t o r s ，s i m p l es 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 yh i g h q u e r yc o s ta n dc a n n o ts a t i s f yu s c r s ，s ow cm u s tm a k eu s eo fm u l t i d i m e n s i o ni n d e x s t r u c t u r et oa c h i e v ef a s tq u e r y p e o p l eh a v ed o n ea l o to f r e s e a r c ht oi n d e xm u l t i - d i m e n s i o nd a t ae f f e c t i v e l ya n d h a v ep r o p o s e dm a n yi n d e xs t r u c t u r e ss u c ha sr - t r e e ，r + 一t r e e ，x - t r e e ，s r - t r e ea n d s s - t r e e t h e s ei n d e xs t r u c t u r e s p e r f o r m a n c ed e c r e a s es h a r p l yw i t ht h ed i m e n s i o n i n c r e a s e ，a l t h o u g ht h e yw o r k w e l li nl o wd i m e n s i o ns p a c e t h i sp h e n o m e n ai sc a l l e d l ec u r s eo f d i m e n s i o n a l i t y t os o l v et h i sp r o b l e m , w eb r i n gf o r w a r dai n d e xs t r u c t u r eb a s e do nb o u n d a r y s e p a r a t e p r a c t i c es h o wt h a tt h i si n d e x s t r u c t u r ew o r k sw e l li nh i g hd i m e n s i o ns p a c e k e y w o r d s ：c o n t e n tb a s e d ，i n d e xs t r u c t u r e , h i g hd i m e n s i o n , s i m i l a r i t yq u e r y , t h e c n r s eo f d i m e n s i o n a l i t y 3 l ，山大学硕十论文基于边界区域分离的高维点数据索引研究 第1 章前言 多媒体信息检索的传统方法是基于文本的。使用关键字注释是最常用的方 法，使用这种方法，对多媒体信息的检索转变为对关键字的查询。这种方法可以 利用传统的d b m s 实现，简单易行，而且能够从用户角度表达对多媒体内容的 理解。但对于目前容量以g b 或t b 来计算的多媒体信息来说，要求对每条记 录进行注释是不可行的，同时，多媒体内容对于注释者的依赖性也局限了这种方 法的正确性。除了关键字，多媒体文件的文件类型、大小、日期等附加信息也可 以作为检索的辅助手段，但它们都不能反映多媒体的内容。 为了克服以上方法的局限性，9 0 年代初出现了基于内容的信息检索系统 ( c b i r c o n t e n t - b a s e di n f o r m a t i o nr e t r i e v a l ) 。c b i r 系统除了利用以上方法之 外，主要是从多媒体中抽取出特征向量，然后，利用特征向量来进行匹配、查找。 利用已有的算法，特征抽取可以由机器自动完成，这就克服了手工注释的低效和 二义性。 从多媒体中抽取出特征向量后，多媒体之间的相似性就转变为特征向量之 间的相似性，多媒体信息查询就转变为特征向量的查询，然而，高维向量占用的 磁盘空问很大，如果进行顺序扫描的话，将要花费大量的时间来进行磁盘i o ， 而且，计算向量之问的距离也需要花费大量的c p u 时间，因此，当维数很高，数 据库很大的时候，用顺序扫描的方法来进行相似性查询必将导致系统的反应速度 变得很慢，在现实系统中是不可取的，所以需要建立附加的索引结构加速查询的 执行。 为了有效索引多维数据，人们进行了大量研究，提出了众多的多维数据索引 结构，例如r - t r e e 1 ，r 一t r e e 2 ，x - t r e e 3 ，s r t r e e 4 ，s s t r e e 5 等，这些索引结构在低维空间中性能很好，但是，在高维空间中，性能急剧下降， 甚至不如顺序查询，这种现象被称为“维数危机”，为了解决“维数危机”，我们 在本文中进行了相关研究。 论文贡献和内容 本文提出了一种基于边界区域分离的高维索引结构c l u s t e r + 树，该索引结 构在数据集为“簇集”数据时，有着良好的性能，一定程度上克服了维数危机。 r h ih 大学硕十论文基于边界区域分离的高维点数据索引研究 本文按以下方式组织： 第一章介绍了论文的背景和主要内容；第二章详细介绍了多维空间的相关概 念；第三章介绍了多维索引方面的相关研究；第四章提出了基于边界分离的高维 索引结构c l u s t e r + 树；第五章介绍了多媒体数据库管理系统e b a s e ，并对c l u s t e r + 树的性能进行了测试；第六章对本文进行了总结。 巾山大学硕十论文 基丁边界区域分离的高维点数据索弓l 研究 第2 章高维向量空间综述 在相似性检索领域，需要在对象集中查找与某个给定对象相似的对象，这种 查找过程称为“相似性查询”，通常，对象之间的相似程度不是由对象本身直接 定义，而是首先从对象中提取出描述对象的某种特征，该特征一般用高维空间中 的特征向量来描述然后，通过计算特征向量之间的距离来反映对象本身的相似 程度，因此，相似查询问题就转化为高维空间中的相似向量查询问题。 2 1 向量空间相关概念 2 1 1 向量空间 自然界中存在大量复杂的事物或现象，为了从不同角度描述这些复杂对象， 需要用各个方面的特征及特征问的关系来共同描述。这些用多个变量抽象描述复 杂对象的数据，称为多维向量。 实数域上的一个n 维向量就是实数域中n 个数组成的有序数组 ( a 。a ! ，如) 。其中a 。称为该n 维向量的分量。两个n 维向量相等当且仅当这 两个n 维向量的所有分量都相等。以实数域中的数作为分量的n 维向量的全体， 称为实数域上的n 维向量空间，记为瞅。 2 1 2 内积 在n 维向量空间v 上定义一个二元实函数，称为内积，记作( c t ，b ) 。它具有 以下性质： 1 ) ( ，b ) = ( b ，o ) ； 2 ) ( ko ，b ) = k ( a ，b ) ： 3 ) ( q + b ，v ) = ( o ，y ) + ( b ，y ) ： 4 ) ( q ，) = o ，当且仅当o = ( 0 ，0 ，0 ) 时，( ，a ) = o ： 其中a ，1 3 ，y 是v 中任意向量，k 是任意实数。定义了内积的n 维向量空 间又称为一个n 维欧几里德向量空间 在r n 中，对于向量= ( a ，如，a 。) ，b = ( b 。，b ：，b 。) ，( ， b ) ：a ，b + a ：b 。+ + 咖。是一种常见的内积定义，该内积又称为“点积”，通常，点 积可以简写为ab 。 2 1 3 向量长度 - | j 山大学硕士论文 基于边界区域分离的高维点数捌索引研究 非负实数厕称为向量。的长度，记为。长度为l 的向量称为单位向 量。如果n o ，用向量e l 的长度去除向量a ，得到一个与。同向的单位向量， 通常称为向量e l 的单位化。 两向量之间的距离 对两向量a 与b ，长度k i 称为向量n 与向量1 3 之问的距离，记为d ( n ， b ) 。向量之间的距离有以下三条基本性质： 1 ) d ( e l ，b ) = d ( b ，a ) ： 2 ) d ( e l ，” 1 0 ，并且当且仅当n = b 时，等号成立： 3 ) d ( ，b ) d ( a ，y ) + d ( y ，b ) ( 三角不等式) ； 两向量之间的夹角 对于非零向量n 与b ，它们之间的夹角 为： 防a r c c o s 黼，o 衩。如。( 2 - 1 ) 如果两向量1 3 和0 的夹角为零，则e l 和b 称为正交或互相垂直，记为q 上 b 。 2 2 常用的向量之间距离函数。 在抽取出对象的特征之后，很直观的方法是直接使用特征向量之间的距离 来衡量两对象之间的相似性。然而，不同的距离度量方法对不同的特征抽取模型 具有不同的性能。在中，w y m a 和b s m a n j u n a t h 的实验显示欧几里德距离和 加权欧几里德距离对不同的特征集具有较大的性能差异。下面介绍一些较为常用 的距离公式。 1 ) m i n k o w s k y 距离 d ( x ，y ) ( 2 2 ) 这是若干种距离公式的通式表示，以下的m a n h a t t a n 距离和欧几里德距离 都是它的特例。 2 ) m a n h a t t a n 距离 人，咒 一 鼍 。h ，l 山大学硕十论文 萆丁边界区域分离的高维点数据索引研究 d ( x ，y ) 2 z t x , 一m i ( 2 3 ) i = l 这是m i n k o w s k y 距离当r = l 时的特例 3 ) 欧几罩德距离 m 川= 辱焉 ( 2 4 ) 欧几里德距离是应用较广的距离公式。然而欧几里德距离公式和前面几种距 离公式一样，完全不考虑向量各维之问的关系，因此各维必须是同等重要的，这 就大大影晌了它的使用范围和有效性。 4 ) 加权欧几里德距离 吣川= 厣 ( 2 5 ) 其中w i 是各维相应的权值。加权欧几里德距离考虑了不同维之间的不同重 要性。由于通常抽取得到的特征向量各维之问的重要性是不同的，因此，加权欧 几里德距离应用也很广。 5 ) 加权欧几里德距离的推广 。_ _ _ _ _ _ _ _ - _ 。- 。_ _ _ _ _ _ _ _ _ _ _ - 。一 d ( x ，y ) = 4 ( x 一 1b(xy)(2-6) 其中b 是一个正定对称矩阵。在实际应用中，b 通常是根据向量子空间内向 量的分布计算得到的协方差矩阵。 2 3 向量空间的查询方式 多维向量的查询通常是相似性查询，与传统数据库的精确匹配不同。传统的 精确查询是找到数据库中与被查询对象精确匹配的记录，而相似性查询是找到数 据库中与被查询对象某些方面相似的对象的集合。 相似性查询包括下列几种常见的方式： 1 点查询( p o i n to u e r y ) 点查询是最简单的查询类型。对于数据库d b ，查询点q ，其查询表达式为： p o i n t q u e r y ( d b ，q ) = p d b p = q )( 2 - 7 ) 点查询类似传统的精确查询。 9 山大学硕十沦文 批丁边界区域分离的高维点数据素引研究 2 范围查询( r a n g eq u e r y ) 范围查询的目的是为了获得与被查询对象的距离在某一阀值内的所有对象 的集合。对于查询目标q ，阀值r ，数据库d b ，范围查询的表达式为： r a n g e q u e r y ( d b ，q ，r ) = p e d b | d ( p ，q ) r ( 2 - 8 ) 显然，点查询可以看作是范围查询在r = o 时的一种特例。如果距离度量为欧 几里德距离，则范围查询的几何意义为以查询点为球心的一个超球。如果距离度 量为m a n h a t t a n 距离，则对应一个超立方体。 3 最近邻查询( n e a r e s tn e i g h b o rq u e r y ) 最近邻查询返回数据库中与查询对象最近的一个对象，但是当数据库中有 几个对象与查询点距离相等时，存在两种不同的处理办法，一种是返回所有的查 询结果，一种是任选其中一个对象作为查询结果。对于查询目标q ，数据库d b ， 最近邻查询表达式为； n n q u e r y ( d b ，q ) = p e d b ivx d b ：d ( p ，q ) d ( x ，q ) ) 4 k 一最近邻查询( k n e a r e s tn e ig h b o rq u e r y ) k 一最近邻查询是最近邻查询的一种推广，它返回数据库中距查询对象最近的 k 个对象。显然最近邻查询是k 一最近邻查询在k = l 时的特例。对于一个给定的查 询目标q ，数据库d b ，k 一最近邻查询表达式为： k n n q u e r y ( d b ，q ，k ) = p 6 d b lvx d b ，x 仨k n n q u e r y ( d b ，q ，k ) ，d ( p ，q ) d ( x ，q ) 且 k n n q u e r y ( i ) b ，q ，k ) l = k ( 2 9 ) 5 似最近邻查询和近似k 一最近邻查询 在该类查询中，对于一个指定的查询点q 和查询结果的数目k ，返回的并非 一定是离查询对象最近的那些对象，而是允许有一定的误差。 6 等级查询 等级查询中用户不指定查询结果的数目，而是把查询结果按近似的级别排 序。显然，最近似的一级，即第一级的查询结果就是最近邻查询结果，所以也可 以看作是最近邻查询的一种扩展。在得到第一级查询结果后，用户可以进行可能 的第二，第三等不同等级的查询。等级查询的优点在于它可以使用户在检查完前 面的结果后，才决定是否需要进行进一步查询。 o 小山大学硕+ 论文 麟丁边界区域分离的高维点数据索引研究 相似性查询的方式有很多种，其中范围查询与k 最近邻查询是最常见也是 最重要的两种，其实，大多数的查询方式可以看成是这两种基本查询方式的扩展 和延伸。在本文的研究中主要针对的是这两种查询方式。 2 4 本章小节 在本章中，对多维数据空间的相关概念进行了详细介绍，并具体介绍了多维 空间中查询的几种方式，其中范围查询与k - 最近邻查询是最常见也是最重要的 两种查询方式，为了加快查询的执行，需要建立相关的索引机构，下一章将对这 方面的相关研究进行介绍。 p 山大学硕+ 论文 拈丁边界区域分离的高维点数据索引研究 第3 章多维索引相关研究 在数据库中，常需要建立索引结构来加速查询的执行，传统的数据库索引技 术是基于关键字字段的算术运算：大小比较和包含关系运算。这类关系都是拟序 的，且具有自反性、非对称性和传递性。索引的构造主要是利用传递性将记录排 序，然后划分为不同的区间，区问再划分为子区间，层层下去构造一颗索引树。 然而，多维向量之间是一种相似关系，这种关系运算只具有自反性、对称性、却 没有传递性。因此，传统的构造索引的方法对于多维数据不再适用。 3 1 多维索引的目标 多维索引需要实现以下两个主要目标： 1 索引的正确性 索引的算法必须保证查询得到的结果是有效的和有用的。 2 索引的时间有效性 索引的最终目的是加快查询的速度，因此利用索引查询的速度应大大少于 利用顺序扫描进行查询的速度。 另外，一个好的索引结构还应具有以下一些特征 6 ： 1 动态构造：由于数据可以在数据库中以任意顺序插入或删除，因此其索引 结构也应该与之保持一致，即索引结构也必须支持动态的插入和删除。 2 多级存储管理：虽然主存日益增大，仍然不能将一个完整的大型数据库保 存在主存中，因此索引结构要充分考虑二级以及三级的存储管理。 3 支持尽量多的操作：不能以牺牲其它操作的代价而支持某一种特定的操 作。 4 独立于输入数据及插入顺序：支持各种多维数据和任意的输入顺序。 5 可增长性：索引结构要能适应数据库大小的增长。 6 空间有效性：一个索引结构相对于其原始数据应是比较小的，要保证一定 的空间利用率。 7 并行性和可恢复性。 巾山大学碗十论文牡丁边界区域分离的高维点数据索引研究 3 2 多维索引的分类 根据高维数据索引结构的各种特点，可以有不同的分类方式，以下列举几种常 见的分类方式。 1 根据索引创建时数据的组织形式，可以分为静态结构类和动态结构类。静 态结构类是指建树时数据库全部或大部分数据都己知，因此采用批处理的方式将 全部数据构建索引，不能支持或者不能有效地支持动态的插入和删除，如g h 树 7 ，v p 树 8 等：而动态结构类是指将数据依次插入而生成的索引结构，如r 树 1 及其变种r 树 2 等等。 2 根据索引的组织形式，可以分为树形结构类和非树形结构类。树形结构类 是指索引结构按树的形式组织数据，如x 树 3 ；非树形结构是指索引结构不是 按照树形结构组织的，如v a 文件 9 等。 3 根据索引的创建方式索引结构可分为基于数据集划分的索引结构、基于 空间划分的索引结构、基于降维的索引结构、基于量化的索引结构。 4 根据对象特征的表示形式，可以分为向量空间索引结构( ( s p a t i a la c c e s s m e t h o d ，s a m ) 和度量空问索引结构( m e t r i ca c c e s sm e t h o d ，m a m ) 。向量空间将 多维数据对象映射成多维空间中的点，两对象之间的差异以各维的坐标值和距离 来衡量，这也是多维数据库中最常用的相似性模型：度量空间则只考虑数据之问 的距离信息，而不考虑坐标值等其它相关信息。创建索引时度量空间索引结构只 根据数据对象的距离度量来划分数据空间。s a m 和m a m 的典型代表分别是r 树 1 和m 树 1 0 。 。 本文采用第3 种方式，对常见的多维索引结构进行介绍。 3 3基于数据集划分的索引结构 基于数据集划分的索引结构把数据集划分为几个子集，对每个子集的特征进 行描述，然后把各个子集进步划分为更小的子集，这样一直划分下去，直到数 据集中的数据足够少。 根据数据集之间的包含关系建立了一个树形结构，在该结构中，每个中间节 点代表一个数据集，其中保存有该数据集的特征描述，而它的各子节点迸一步对 山大学硕+ 沦文 幕，边界区域分离的高维点数据索引研究 它的各子集进行描述。树的根节点代表数据库中的全部数据，作为查询时的入口。 查询时，从根节点往下，对每个子集，根据保存在树节点中的特征描述判断 是否可能包含查询结果，如果可能有，则进一步对与浚子集对应的子树进行查询， 否则，该子集不需要进一步进行查询，可以被“剪枝”，从而避免了不必要的数 据读取和距离计算，加快了查询速度。 在基于数据集划分的索引结构中，对数据集特征的描述很关键。特征描述得 越详细，筛选能力越强，但同时占用得空间越多，树节点的扇出度越小，树的高 度越大。在索引结构中，通常使用以下特征描述：代表点、最小边界矩形、最小 边界超球。 r 一树 1 及以其为基础的各种树形结构是最常用的基于数据集划分的索引结 构，也是对多维数据索引的较早尝试1 9 8 4 年g u t t m a n 首次提出r 一树 1 的概 念它是b + 树在多维空间上的扩展，在r 一树 1 中，使用最小边界矩形来描述数 据集的特征。 r 一树 1 是一平衡树，它具有以下特点： l i 如果用m 来表示一个节点中可以存放的项数目的最大值，用m 来表示一个节 点中可以存放的项数目的最小值，则除了根节点外，每个节点中必须包含 m m 个项。 2 根节点中至少要包含两个项，除非它是一个叶子节点。 3 结点中的每个项的结构为( 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 指向实际数据存放 的位置。 4 所有叶子节点在同一层。 向r 一树 1 中插入数据时，首先从根节点开始，在经过的每一个内部节点中 选择这样的项：它所指向的子节点为了包纳下要插入的数据其m b r 的面积需要扩 大最小，如果出现相同的情况，则选择m b r 最大的一个。当到达叶子节点后，如 果该节点中还有剩余空间，就将数据插入到该节点中，并按原路径返回，依次修 改其祖先节点中相应项的m b r ：假如在叶子节点中已经没有足够的空间存放下要 插入的数据，则要进行分裂，生成一个新的叶子节点，并在其父节点中插入个 山大学硕十论文冰于边界区域分离的高维点数据索引研究 指向新叶子节点的项，如果其父节点同样出现了溢出，也要产生分裂，如此下去， 直到根节点，如果根节点也发生分裂，则生成一个新的根节点，树的高度增加l 。 要在r 一树 1 中删除一个数据，首先要进行一次精确查询操作，如果找到了 该数据，则从节点将其删除，在删除之后如果节点中有足够的项( 即项数目不小 于m ) ，就依次修改其祖先节点中相应项的m b r ，删除结束：如果删除后节点中项的 数目小于i i 2 ，则将该节点所有的项保存到一个临时缓冲区内，并将该节点从树中 删除，如果节点删除后影响到其父节点也出现相同的情况，则也要做相同的操作， 如此直至根节点，然后再将临时缓冲区内所有的项重新插入到树中。如果在删除 完成之后根节点只有一个子节点的话，则这个子节点就成为新的根节点，树的高 度减l 。 图3 一l 是r 一树的一个简单例子，它反映了r 一树的结构和特点。 图3 一l ：r 树索引结构示意图 r 树给人们提出了一种全新的解决多维索引问题的方法，一些研究者对它的 结构和算法进行了研究和改正，以期望得到更好的性能，主要有以下几种： r + 树 1 1 ：为了解决r 树的过度重叠问题，t i m o ss e l l i s 等提出t r + 树索引结 构，采用新的分裂方式使节点之间不再存在重叠。具体的做法是对重叠区域进行 分裂，两个节点矩形之间的重叠被重新划分为一个新的节点，数据如果处于分裂 区域内，则分配到原节点与新节点之中：由于节点之间无重叠，查询的效率也就 相应提高了，但在一定程度上会造成存储空问的浪费和树高度的增加。 s s 一树：s s 树 5 是采用最小边界超球( m b s ) 取代原来进行数据划分的m b r ，以 更好的支持相似性查询。s s 树的数据划分是这样确定的：给定数据集合，找到其 中心点( 各个维上数据的平均值) ，半径取为以中心为球心，将集合中所有数据都 t i 山大学硕士论文基于边界区域分离的高维点数据索引研究 包含在内的最小距离。s s 树索引结构如图3 2 所示。 在插入时s s 树对子树的选择是以和子树节点的中心的距离远近为标准的，选 择距离最近的节点进行插入，而不考虑产生的重叠或增大的面积。数据插入后对 子树的中心点和半径都要作相应的调整。由于球形包络的复杂性，当一个节点分 裂为两个节点时，很难找到一种无重叠的分裂方式。 图3 - 2 ：s s 树索引结构示意图 旷树 2 ：r + 树对r 一树的插入和分裂算法进行了一些改进，主要体现在以下两 点：第一，提出了强制重插概念，当一个节点在插入过程中发生了溢出，并不急 于进行分裂，而是首先看一下该层节点在这次插入过程中有没有进行过重新插 入，如果没有的话，则选择一定比例的项从该节点中删除并重新插入到树中，如 果该层已经有节点进行过重新插入，才对该节点进行分裂；第二，当节点进行分 裂的时候，不仅要考虑分裂后的两个新节点的面积，还有考虑分裂后节点周长以 及该层节点的重叠面积等因素。有数据表明，f 树的性能要比r 树提高了l o 至l j 7 5 。 s r - 树：s r 一树 4 是对s s 一树的扩展，并结合y s s 一树和r + 树 2 的概念。s r 树是一种在目录节点中将矩形和球形结合在一起的索引结构。可以看成是r 树与 s s 树的混合形式。在目录节点中，它将m b r 和m b s 的相交区域作为节点区域，结合 了二者的优点，达到更好的空间划分。但是由于m b r 和m b s 的结合，s r 树具有所有 索引结构中最复杂的节点形状，节点占用空间大，利用率不高。 x 一树e 3 ：当节点之间的重叠率太大时，高维索引的效率可能还不如顺序查 询方法。为此，针对高维索引结构在高维数据空间的高度重叠性，b e r c h t o l d 等 人提出了x 一树索引方法 3 。x y 结合了层次的r 树索引和线性的顺序索引的优 点，引入了“s u p e rn o d e ”( 超节点) 的概念。索引结构如图3 - 3 所示。 6 山大学硕十沦文幕丁边界区域分离的高维点数据索引研究 图3 3 ：x 树索引结构示图 当节点发生溢出时，首先考虑对节点选择合适的分裂算法，以使节点分裂后 重叠区域尽可能的小到一定程度：假如无法避免分裂后出现的严重区域重叠，则 不分裂节点，而是扩大节点大小以放入更多的项，形成超节点：当查询到达超节 点时，对超节点内的对象采用线性的顺序查询方法。随着维数的增加，由于在高 维时对超节点的线性访问要优于对高度重叠的普通节点的层次化访问，树结构需 要动态改变超节点的数量和大小以提高索引效率。 在实际性能比较中，虽然x 树为减少重叠引入了线性结构，但是在复杂度和 空间上的开销都很大：随着维数的增大，超节点大小不固定，搜索速度也将近似 于顺序搜索。 最近，s a k u r a i 提出了a - 树索引结构，并引入了相关近似的概念。a 一树的 基本思想是使用虚拟边界矩形来近似表达最小边界矩形或最小边界对象。这洋。 在树的一个节点上，会包含m b r 区域的位置的精确信息以及其孩子的相关位置 的近似信息其性能超过了v a f i l e 和s r 村。 基于聚类的索引结构采用各种聚类算法对数据集进行划分，形成一棵聚类 树，从本质上讲，基于聚类的索引结构仍然是一种基于数据集划分的索引结构， 其特殊性在于其划分数据集时采用的方法。 m 一树 1 0 系列索引树是另一类型的基于数据集划分的索引结构，同时它是一 种度量空问的索引结构。m 一树的结构特点非常类似r 一树，具体体现在： 1 它是平衡树，它所有的指向实际数据的指针都存放在叶子节点上。 2 每个节点所存放的项的数目最大不得超过n 。 3 在动态插入一个数据项时，选择最“相近”的分支往下插入，当引起节 1 7 r | i 山大学硕十论文基于边界区域分离的高维点数据袈引研究 点溢出时，要对节点进行分裂。 与r 树不同的是：m 树的节点不仅存放了参考对象的特征矢量，还存放了度量 距离信息；而且中问节点和叶子节点的结构是不同的。 叶节点格式：e n t r y ( 0 ) = o ，o l d ( 0 ) ，d ( 0 ，p ( 0 ) ) 目录节点格式：e n t r y ( 0 ) = 0 ，p t r ( t ( o ) ) ，r ( 0 ) ，d ( 0 ，p ( 0 ) ) m n 的目录节点和叶子节点都存放了其度量区域的参考节点对象o ，以及0 与 其父参考节点的距离d ( o ，p ( 0 ) ) ，存放这些距离可以在查询时根据三角不等式减 少距离计算。m 一树的索引结构如图3 4 所示。 图3 4 ：m 树索引结构示意图 s l i m 一树 1 2 ：s 1 i m 一树是在m 一树的基础上对它进行了优化，具体体现在： 1 提出了一种基于m s t ( m i n i m a ls p a n n i n gt r e e ) 的新的节点分裂算法。如图 3 5 ，首先为待分裂节点中的所有元素构造一最小生成树( 边的权值以距离表示) ， 选择权值最大的边( a b ) 进行切分；将剩余的两个连通图中的元素分别作为两个新 节点中的元素；最后为每个新节点选取有代表性的元素和最小覆盖半径。 2 提出了一种衡量度量空间中空间重叠程度的办法，并且利用这种衡量标准 给出了一种在节点之间移动数据项的算法，以期降低节点相互重叠程度。 b 持删除的边 c 图3 5 ：基于m s t 的分裂方法示意图 山大学硕十论文 基于边界区域分离的高维点数据索引研究 v p 一树 8 ：v p 一树同样是一种基于度量空间的索引结构，它是一棵二叉平衡 树，它的思想在于如何将二分查找用于只有距离信息的多维度量空间中。v p 一树 的每个节点都相当于对空间的个划分，具体的构造方法为：选取一个元素p 为 根节点，将剩余的所有元素根据到p 的距离的远近分别均匀地放n p 的左右子树 中，离p 较近的一半元素放入p 的左子树中，离p 较远的一半元素放入p 的右子树中； 设m 为左右子树的临界值，将它作为节点的附加信息保存；分别对左右子树重复 以上过程，直到节点中的元素数目小于阀值k 在v p 一树上的查询同样是利用三角不等式减少查询分支。如果d ( q ，p ) 一r m ， 则进入p 的左子树；如果d ( q ，p ) + r m ，则进入p 的右子树。 构造v p 一树的空间复杂度为0 ( 1 0 9 n ) ，时间复杂度为0 ( n l o gn ) ，在查询半径 很小的条件下查询问复杂度为0 ( o g n ) 。图2 1 6 就是一个v p - 树的例子。 l 7 弋- 32 2 9 “少。 4 s67 图3 6 ： 选择元素1 为根节点的v p 一树 m v p 一树 1 3 ：m v p 一树对v p 一树的结构做做了少许改变。它将中间节点所包含 元素( v a n t a g ep o i n t ) 的数目由v p 一树的一个增加到两个，其中每个元素的划分份 数为m ，这样提高了每个节点的输出能力，降低了树的高度，从而减少了距离函 数的计算次数。构造一棵m v p 一树所需要的距离函数的计算次数为0 ( n l o g 。n ) ，比 v p t r e e 少 l o g 。n ，并且查询性能上也有了很大的提高。 基于数据集划分的索引结构在维数较低的时候性能很好，但是，当维数较高 的时候，索引性能急剧下降，当维数超过3 0 维时，利用索引结构进行查询时的效 率几乎和顺序查询的效率差不多，甚至不如顺序查询，这种现象被称为“维数危 机”。造成这种现象的主要原因是：对数据集特征的描述是对数据集的一种抽象， 1 9 f 山大学硕+ 沦文 基于边界区域分离的高维点数据索引研究 即该数据集中的所有元素均满足该特征描述，但同时，满足该特征描述的数据不 一定在该数据集中，记数据集为d s ，描述为u ，在数据空间中满足描述d 的数据的集 合为d ( u ) ，基于数据集划分的算法把数据集d s 划分为互不相交的子数据集 d sb 一，d s 。各子数据集对应的特征描述分别为u ，u 。，满足这些描述的数据 的集合分别为d ( u 。) ，d ( u ：) ，d ( u 。) 。显然有d s 。c d ( u ，) 。我们希望d s i 与d ( u ) 足 够接近，同时d ( u ) ，d ( u ：) ，d ( u 。) 互不相交，这样索引结构的过滤能力强，在 低维空间中这可以做到，但是在高维空间中，d ( u ，) ，d ( u 。) ，d ( u 。) 之间不可避 免地有大量的重叠区域，同时有 d ( u ) l l 魍i 。这样查询时索引结构的过滤能 力变得很弱，甚至不得不遍历所有路径，导致查询性能急剧下降，甚至低于顺序 查询。 3 4 基于空间划分的索引结构 基于空间划分的索引结构不考虑数据的空间分布，它把空间划分为互不相交 的子空间，各子空间进一步划分为更小的子空间，按这种方法产生一棵层次树。 k d 树是最常见的基于空间划分的索引结构。k d 树 1 4 是一种k 维空间中的 二叉查找树，主要存储的是点数据。在每一个内部节点，用一个k l 维的超平面 将节点所表示的k 维空间划分成两个部分。这些超平面在k 个可能方向上交替出 现，而且在每一个超平面中至少要包含一个数据。如图3 1 所示。 入。 八 图3 - 7 ：k - o 树索引结构示意图 在k d 树中的查找和插入操作很简单，而删除操作则比较复杂。某一个点的 删除可能会导致其子树的重建。数据插入顺序的不同，也会导致k d 树的结构的 be 山大学硕十论文摹丁边界区域分离的高维点数据索引研究 不同：同时数据会分散出现在树的任何地方，而不是仅出现在叶子节点上。 对k - d 树进行结构上改进的有以下两种方法： a d a p t i v ek - d 树 1 5 ：它对k d 树的结构做了少许改变，在分裂的时候选择合 适的超平面使分裂后的两个部分包含相同数量的数据，而且在这些超平面上不一 定非要包含数据，同时它们的方向也不一定严格的在这k 个可能的方向上交替出 现。在这种结构里，内部节点表示的是分裂的超平面，所有的数据都出现在叶子 节点中，每个叶子只能包含一定量的数据，当超过这个数量的时候要发生分裂。 k d b 一树 1 6 ：它是将a d a p t i v ek - d 树同b 一树的特点结合到了一起。首先， 它采用了a d a p t i v ek - d 树中的用超平面来划分节点中的空问的方法，不过对于一 个内部节点所表示的空间，可以用多于一个的超平面来划分，形成了几个相邻的 予空问，每个子空间对应着一个内部节点，所有的数据均存储在相应的叶子节点 中。从图3 8 中可以看出，它的结构类似于b t r e e ，不过在k d - b - 树中不能保证 最小空问利用率。 d g 。l二 t 。：， 一 l：h b i 7 肌r c ii 图3 8 ：k d - b 一树示意图 四叉树 1 7 ：同k d 树类似，四叉树也是用超平面的方法来划分整个空间的， 不过不同的是，四叉树不再是二叉树。在维数为k 的空间中，每一个目录节点具 有2 个子节点。每个子节点对应着一个子空问。例如，对于一个在二维空间盼四 叉树，每个目录节点拥有4 个子节点。每个子节点对应着一个矩形。这四个矩形 一般用n w ，n e ， s w 以及s e 来表示( n w 表示西北方向的那个矩形) 。用这种方法将 整个空间逐渐划分直到一个矩形中所包含的数据的个数低于一定的数目为止，显 然这样得到的四叉树不能保证是平衡树。在数据比较密集的地方，树的深度将高 于其它的地方，如图3 9 所示。 山大学硕士论文 摹丁边界区域分离的高维点数据索引研究 + 图3 9 ：四叉树索引结构示意图 四叉树的查找操作类似于普通的二叉查找树。在每一层要从四个子节点中选 择要继续查找的子树。对于点查询，只需要选择其中的一个合适的就行了，而对 于范围查询可能需要几个。按照这个方法递归执行下去直到查找到了树的叶子节 点为止。 点四叉树：点四叉树( p o i n tq u a d t r e e ) 是四叉树的一个变种，它是由点数据 一个接一个地连续插入而构造出来的。对于每一个点，首先进行一个点查找操作。 假如没有在树中发现该点，就将该点插入到刚才的查找操作终止的叶子节点，而 这个节点所表示的区域以新插入的点为中心分为2 “个子空间。如果想从点四叉树 中删除一个点的话，则会引起相应的子树的重建，需要将所有子树上的数据重新 插入，删除的代价相当大。图3 1 0 是点四叉树的一个例子 i 1 8 lfa 1 o 6 | 尊 图3 - 1 0 ：点四叉树示意图 基于空间划分的索引结构由于完全不考虑数据的分布情况，因此，节点的利 用率很低，树的高度较高，当维树较高时，同样存在索引性能急剧下降的“维数 危机”。 山大学硕士论文基丁边界区域分离的高维点数据索引研究 3 5 基于降维的索引结构 基于数据集划分的索引结构和基于空自j 划分的索引结构在高维空问部面i i j “维数危机”，基于降维的索引结构试图通过把高维空问的数据转变为低维空间 的数据，然后在低维空间建立索引来解决“维数危机”。在这类索引结构中，比 较特殊的是把高维空间的数据转变为一维空问的数据。 空间填充曲线索引方法：这一类索引结构的特点就是希望找到某种方法对高 维空间中的数据进行近似的排序，使得原来在空间中较为接近的数据能在排序后 以比较高的概率靠在一起，那么就可以用维数据对它们进行索引。用这种方法 在点查询操作中能够取得良好的效果，但进行范围查询时就会比较麻烦了。 根据这种思路，人们就提出了几种将高维空间中的点数据映射到一维空问并 进行排序的方法，图3 - 1 l 列出了四种。 ：o u - - xi 厂 ： o】 1 r 、| 口0 黼熊 h l i b t n 图3 1 1 ：四种空间填充曲线 所有的空间填充曲线都有一个重要的优点，就是对任何维数的数据都可以处 理，前提是映射到的一维空问的键值可以任意大。但这种方法也有一个明显的缺 点，当将两个不同区域的索引组合到一起的时候，至少要对其中的一个进行重新 编码。 门 t i i 山大学硕士论文 萆r 边界区域分离的高维点数据索引研究 n b 一树：n b 树直接使用向量长度作为高维到一维的映射函数，如图3 一1 2 。在 把多维数据映射到一维空间后，使用b + 树对一维数据进行索引。由于在高维空问 相邻的向量其长度必然相近，因此查询时可以先计算出查询向量的长度，然后以 该长度在b + 树中做相应的查询。 图3 - 1 2 ：n b 树的高维到一维映射 d i s t a n c e ：在j d i s t a n c e 索引结构中，高维空间中的向量按如下方法映射到 一维空间：把高维空间划分为几个子空问，然后为每个子空间选择一个参考点。 假设我们有m 个子空间p 0 ，p i ，”，p | 。，它们相应的参考点分别为0 0 ，0 l ”，吨+ 对于 高维空间中的任意一个点p ：( x 。，x ”，x d 一。) ，0 x j 1 ，o d ，设它距离参考点o 。 最近，n p 被映射到一维空间的点y ，其中y = i c + d ( p ，0 。) 。 其中c 是一个常量，这样子空间p i 中的所有点被映射到 i c ，i xc + c 。显然， c 必须足够大以使各分区不会重叠。图3 1 3 是2 维空间中映射的一个例子。 经过映射后得到的数据在b 十树上进行组织。考虑一( q ，r ) 的范围查询，假设 点p 在该范围内，由三角不等式有： d ( o i ，q ) 一r d ( o i ，p ) d ( 0 i ，q ) + r ( 3 ，1 ) 因此，可以把查询转化为在b + 树上的一系列范围查询。在得到一系列候选点 后，再测试是否在( q r ) 内，最后得到查询结果集。 最近邻查询可以通过范围查询完成，作者给出了通过范围查询完成近邻查询 的算法。 山大学硕士论文批丁边界区域分离的高维点数据索引研究 o o ( 0 图3 - 1 3 ：i d i s t a n c e 树的高维到一维映射 3 6 基于过滤的索引结构 基于过滤的索引结构通过过滤掉一些向量以使得在检索中只需要访问较少 部分的其余向量它可以通过多种途径实现 v 卜f i l e 9 及在其基础上发展起来的一系列变体都属于这类方法，