（应用数学专业论文）海量数据的高维索引结构研究.pdf

河南大学硕士研究生学位论文第1 页 摘要 图像作为一种内容丰富、表现直观的媒体，在许多领域都得到了广泛应用， 如数字图书馆、地理信息系统、生物信息学的d n a 数据库和医学辅助诊断等。如 何在大型图像数据库中快速处理基于内容的相似性检索变得越来越重要，高维索 引技术是基于内容的相似性检索领域研究的一个基本问题，也是一个热点问题， 因此研究海量数据的高维索引结构具有重要的理论和实际意义。然而，由于受到 “维度灾难”的影响，随着数据维数的增长，传统的索引结构性能急剧下降。 针对上述问题，本文以大规模图像库的海量高维数据为背景，围绕图像特征 的高维特性，通过实验研究分析了图像高维特征数据的距离分布特点，在此基础 上，研究并设计了新的高维数据索引结构k v p t r e e 。论文的主要工作如下： 第一，本文通过实验首先提取分类图像库和混合图像库的不同类型不同维数 的特征向量并对其进行归一化，然后计算图像库中任意两幅图像之间的距离，最 后分析得出高维数据的距离分布特点：高维空间中的距离分布具有较大的均值和 较小的方差，其距离分布是“集中的”。进而分析得出如下结论：高维空间的索引 结构采用“平衡树”不一定是最好选择。 第二，本文结合k m e a n s 聚类算法和m t r e e 的结点结构对v p t r e e 进行改进， 给出了一种新的高维索引结构k v p t r e e ，介绍了其设计思想、结点结构、建树过 程和查询方法，最后利用测试数据，对v p t r e e 和k v p t r e e 的性能进行深入的实 验分析。通过实验对k v p t r e e 和v p t r e e 的查询性能进行了详细比较，k v p - t r e e 增加了结点的输出能力，减少了距离计算次数，提高了查询效率。 关键词：高维索引结构；特征提取；k - m e a n s 聚类；v p t r e e ；m t r e e 第l i 页河南大学硕士研究生学位论文 a b s t r a c t i m a g ea sar i c h ，i n t u i t i v ep e r f o r m a n c eo ft h em e d i a ，i nm a n ya r e a sh a s b e e nw i d e l y a p p l i e d ，s u c ha sd i g i t a ll i b r a r i e s ，g e o g r a p h i ci n f o r m a t i o ns y s t e m s ，t h ed n ad a t a b a s eo f b i o i n f o r m a t i c s ，m e d i c a ld i a g n o s i s ，e t c h o wt od e a lw i t h q u i c k l y c o n t e n t - b a s e d s i m i l a r i t y s e a r c hi s b e c o m i n gi n c r e a s i n g l yi m p o r t a n t i na l a r g ei m a g ed a t a b a s e h i g h - d i m e n s i o n a li n d e x i n gt e c h n o l o g yi sn o to n l yaf u n d a m e n t a li s s u eo ft h ef i e l do f t h ec o n t e n t - b a s e ds i m i l a r r e t r i e v a l ，b u t a l s oah o ti s s u e s o s t u d y i n g o n h i g h d i m e n s i o n a li n d e xs t r u c t u r e so fl a r g ed a t ah a si m p o r t a n tt h e o r e t i c a la n dp r a c t i c a l s i g n i f i c a n c e h o w e v e r ，d u et ot h ei m p a c to f c u r s eo fd i m e n s i o n a l i t y ”，w i t ht h eg r o w t h o ft h ed a t ad i m e n s i o n ，t h ep e r f o r m a n c eo ft h et r a d i t i o n a li n d e xs t r u c t u r eh a sd r o p p e d d r a s t i c a l l y i nr e s p o n s et ot h e s ep r o b l e m sa b o v e ，t oh i g h d i m e n s i o n a ld a t ao fm a s s i v ei m a g e s d a t a b a s ea st h eb a c k g r o u n d ，a r o u n dt h eh i g h - d i m e n s i o n a lc h a r a c t e r i s t i c so ft h ei m a g e c h a r a c t e r i s t i c s ，t h i sp a p e rs t u d i e da n da n a l y z e dt h ed i s t a n c ed i s t r i b u t i o nc h a r a c t e r i s t i co f h i g h d i m e n s i o n a li m a g ed a t ab ye x p e r i m e n t a l o nt h i sb a s i s ，t h er e s e a r c ha n dd e s i g na n e ws t r u c t u r eo fh i g h - d i m e n s i o n a ld a t ai n d e x i n g ，t h a ti sk v p t r e e t h em a i nc o n t e n t si s a sf o l l o w s ： f i r s t l y ，b ye x p e r i m e n t st h ed i f f e r e n tt y p ea n dt h ed i f f e r e n td i m e n s i o nf e a t u r ev e c t o r o fc l a s s i f i c a t i o ni m a g e sa n dm i x e di m a g el i b r a r yd a t a b a s ea r ee x t r a c t e da n du n i f o r m e d t h e nt h ed i s t a n c eb e t w e e na r b i t r a r yt w oi m a g e so fi m a g ed a t a b a s ea r ec a l c u l a t e d 。a t l a s tt h ed i s t a n c ed i s t r i b u t i o nc h a r a c t e r i s t i co fh i g hd i m e n s i o n a l i t yd a t ai s g i v e n ：t h e d i s t a n c ed i s t r i b u t i o no fh i g hd i m e n s i o n a l i t ys p a c eh a st h ef e a t u r eo fl a r g e rm e a n sa n d s m a l l e rv a r i a n c e t h a ti st h ed i s t a n c ed i s t r i b u t i o ni sc e n t r a l s oi ti sg i v e nt h a tt h eh i g h d i m e n s i o n a l i t yi n d e xs t r u c t u r eu s i n ga “b a l a n c e dt r e e ”i sn o tn e c e s s a r i l yt h eb e s to p t i o n s e c o n d l y ，an o v e lh i g hd i m e n s i o n a l i t yi n d e xs t r u c t u r ei sp r o p o s e db yi m p r o v e d v p t r e e ，t h a ti sk v p t r e e ，w h i c hc o m b i n e st h ec l u s t e ra l g o r i t h mo f k m e a n sa n dn o d e s t r u c t u r eo fm t r e e t h ed e s i g nt h i n k i n g ，n o d es t r u c t u r e ，t h ep r o c e s s i o no fb u i l d i n gt r e e a n dt h eq u e r ym e t h o do fk v p t r e ea r ei n t r o d u c e d t h e nb ye x p e r i m e n tt h ep e r f o r m a n c e 河南大学硕士研究生学位论文第1 ii 页 o fk v p t r e ei sd e e p l ya n a l y z e d t h ee x p e r i m e n t ss h o wt h a tk v p - t r e ei m p r o v e st h e o u t p u tc a p a c i t yo fn o d e ，d e c r e a s e st h en u m b e ro fd i s t a n c ec a l c u l a t i o n ，a n di m p r o v e st h e e f f i c i e n c yo fq u e r yb yc o m p a r i n gt h eq u e r yp e r f o r m a n c eo fk v p - - t r e ea n dv p - t r e ei n d e t a i l k e yw o r d s ：h i g h - d i m e n s i o n a li n d e xs t r u c t u r e s ；f e a t u r ee x t r a c t i o n ；k m e a n s ； v p - t r e e ；m - t r e e 关于学位论文独立完成和内容创新的声明 本人向河南大学提出硕士学位申请。本人郑重声明：所呈交的学住论文是 本人在导师的指导下独立完成的，对所研究的课题有新的见解。据我所知，除 文中特别加以说明、标注和致谢的地方外，论文中不包括其他人已经发表或撰 写过的研究成果，也不包括其他人为获得任何教育、科研机构妁学位或证书而 使用过的材料。与我一同工作的同事对本研究所做旮勺任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位申请人( 学位论文作者) 签名： i 叠军 2 0年月 日 关于学位论文著作权使用授权书 本人经河南大学审核批准授予硕士学位。作为学位论文的作者，本人完全 了解并同意河南大学有关保留、使用学住论文的要求，即河南大学有权向国家 图书馆、科研信息机构、数据收集机构和本校图书馆等提供学位论文( 纸质文 本和电子文本) 以供公众检索、查阅。本人授权河南大学出于宣扬、展览学校 学术发展和进行学术交流等目的，可以采取影印、缩印、扫描和拷贝等复制手 段保存、汇编学位论文( 甄质文本和电子文本) 。 ( 涉及保密内容的学位论文在解密后适用本授权书) 一士幺、y 学位获得者( 学位论文作者) 签名： 璺! 翌圣 2 d年月 目 学位论文指导教师签名： 一 河南大学硕士研究生学位论文第1 页 第一章绪论 在现代生活中，图像在人们的生活中起着非常重要的作用，并被广泛应用在 医学、教育及娱乐等领域。但是直到上世纪7 0 年代，随着计算机信息技术的发展， 以图像检索为代表的真正的多媒体信息检索技术才产生并日益发展起来。近几十 年来，由于计算机信息技术在各个领域的广泛普及，尤其是近年来互联网上图像 信息的急剧膨胀，对图像的检索需求越来越迫切，传统的数据库管理技术已经不 能满足应用的需要。由于多媒体数据有着与传统的数值、文本等结构化数据信息 截然不同的特性，而对象关系数据库虽然能够很好地定义自己的数据类型和操作， 但是不能解决索引机制问题，这给传统的检索理论带来了极大的挑战。 1 1 研究背景及意义 随着计算机和通信技术的发展，尤其是存储技术的进步和因特网的日益普及， 人们拥有了比以往任何时代都无法比拟的信息资源。这些资源不仅有简单的文本 数据，更包含了大量的声音、图像、视频等多媒体信息。图像作为一种内容丰富、 表现直观的媒体，在许多领域都得到了广泛的应用，如数字图书馆、地理信息系 统、生物信息学的d n a 数据库、医学辅助诊断等。如何在大型高维数据库中快速 处理基于内容的相似性查找变得越来越重要。高维索引技术是基于内容的相似性 检索领域研究的一个基本问题，多年来一直受到研究者的极大关注。 基于内容的相似性检索可视为在高维特征空间中寻找与指定点距离最近的一 组点的问题。在传统计算机科学中，这个问题对应于k 近邻搜索问题或相似索引 问题。当数据库中对象数量较小时，采用顺序搜索就可以获得满意的检索效率。 对于大规模或超大规模数据库来说，顺序搜索算法的c p u 和i 0 复杂度通常都很 大，为了降低查询开销，加速高维空问中的相似性查找，常用的方法是设计一个 高维索引来支持这种类型的查询。多年来，人们陆续提出多种支持相似查询的索 引结构，各种新技术、新方法不断提出，理论研究成果和实验系统相继出现，已 经取得了可喜的进展。然而，许多高维索引技术在实际应用中，其查询效率还不 够理想，未能达到预期的设计目标。其主要原因是高维索引技术并不像传统数据 库中关键字索引技术那样成熟，该领域仍有诸多“瓶颈”问题需要研究解决，对 其中一些基本问题的研究与认识还需进一步深化，许多面向实际应用目标的理论 方法还有待探索和创新。 第2 页河南大学硕士研究生学位论文 本文以图像库中高维特征数据的距离分布规律和特点为研究的出发点，主要研 究如何建立高效的索引结构，从而提高大规模图像数据库中基于内容的图像检索 效率。 1 2 国内外研究现状 为了能够高效的进行数据( 特征) 索引，实现图像、视频等多媒体信息的快速检 索，研究者们对索引技术进行了许多研究，其主要内容集中在适当的降低索引维 数和建立良好的索引方法上。降维的基本思想是对数据对象进行维数压缩，使得 从原先高维的数据变换到相对低维的数据。常用的降维方法有k l 变换、f f t 变 换以及聚类【1 】等。但是，盲目进行维数的压缩是危险的，一方面降维势必损失图像 信息，而这些信息对于检索又是未知的，所以结果很难令人满意；另一方面由于 图像本身维数非常高，即使降维仍很难满足检索要求。因此，围绕着如何建立良 好的索引方法，研究者们做了许多的工作。 1 2 1 高维索引技术 高维索引的研究始于七十年代中期，涉及计算几何、数据库管理和模式识别 等技术。目前的高维索引方法可以分为两大类，一类是向量空间索引结构s a m ( s p a t i a la c c e s sm e t h o d ) ，另一类是度量空间索引结构m a m ( m e t r i ca c c e s s m e t h o d ) 。 向量空间索引结构s a m 中具有代表性的有r t r e e 2 1 、r 木t r e e 3 1 、x t r e e 4 1 、 s s t r e e t 5 1 、s r 。t r e e 6 1 ，网格文件【7 1 、t v - t r e e 引、两层网格文件【9 l 、“t w i n ”网格文件 1 0 】， k d t r e e 1 1 1 、a d a p t i v ek d t r e e 1 孙、k dbt r e e t l 3 l ，四叉树( q u a d t r e e ) 1 4 】、e x c e l l 1 5 】， 空间填充曲线【1 6 l ，v a f i l e 17 1 ，金字塔技术【1 8 】，h y b r i d t r e e 19 1 ，a t r e e l 2 0 1 ， d i s t a n c e 【2 1 1 等。近年来国内在该领域也有了一些进展，例如董道国提出的v a t r i e 【2 2 1 ， v a r t r e e t 2 3 】；梁俊杰提出的b c d i s t a n c e 2 4 l ，c s a t r e e ”1 ，l b d t 2 6 1 等。其中k - d t r e e 是最早被提出的多维索引结构，但因为它是在每个坐标轴上作切割，因此它的执 行时间会随着数据维数的增加而呈指数增长。a d a p t i v ek d t r e e 、k d - b t r e e 是 k - d t r e e 的变形结构。因为它们都是直接在数据空间中作分割，因此较适用于数据 的维数较小且数据在空间中的分布比较均匀的情况。g u t m a n 首先提出了r t r e e 索 引结构，在此基础上，研究者们又提出了多种r t r e e 变种，其中包括r 木t r e e 、x t r e e 、 s s t r e e 、s r t r e e 等。这些索引结构都是根据数据的分布来分隔空间，其中r t r e e 、 河南大学硕士研究生学位论文第3 页 r 半t r e e 是以多维长方体在空间中分割；s s t r e e 使用多维球体来分割空间：而s r - t r e e 则同时使用长方体和球体以期获得更好的检索效果。 向量空间索引方法对于维数较低的查询非常有效，但是随着维数的增加，索 引的性能迅速降低。针对r t r e e 及其变种的实验已经发现，当特征向量的维数小 于2 0 时，它们都可以获得很好的相似检索效率；然而，对于更高维数的特征向量 ( 例如维数大于2 0 ) ，这些索引结构的检索效率就会显著地下降，这就是所谓的“维 数灾难”问题( c u r s eo f d i m e n s i o n a l i t y ) ，前述的各种s a m 索引结构几乎都存在这 一问题。为了解决这一问题，常会采用降维方法，也就是先降低数据的维数，然 后使用现有的s a m 方法来索引低维的数据空间。然而，在基于内容的相似检索应 用中，大量对象信息属于度量空间而非向量空间。因此这些s a m 结构就无能为力 了。为了满足度量空间中快速检索的需要，人们提出了基于距离的索引技术，即 度量空间索引技术。 一般而言，m a m 索引是广义的s a m 索引。它不考虑查询对象在高维空间上 的绝对位置，而是以对象之间的相对距离来组织和区分搜索的空间。相对而言， 度量空间上的索引结构具有更为普遍的使用范围。对于度量空间上的相似检索问 题，距离计算一般被认为是费用高的。因此，建立索引结构的目的就是尽可能减 少每个查询所需的距离计算次数，从而减少相似检索的费用，提高检索效率。 u h l m a n n 于1 9 9 1 年首先提出了m e t r i c t r e e ”1 ，它支持度量空间上的相似检索，它 仅利用对象间的相对距离来划分和组织查询空间，关心的问题是如何利用“三角 不等式 来减少相似检索中的距离计算次数。在度量空间索引结构m a m 中典型 的方法有m t r e e t 2 8 1 ，v p t r e e ”1 ，m v p t r e e 3 们，b k t r e e 3 1 1 ， f q t r e e 3 2 1 ，b s t r e e 3 3 1 ， m 2 - t r e e 3 4 1 s l i m t r e e 35 1 ，g n a t r e e 【3 6 1 ，s a t r e e t 3 7 1 等。国内近年来在m a m 上的研究成 果相对s a m 较少，例如曹奎等人提出的o p t t r e e 及其改进r t r e e 索引结构 3 8 1 ，周 项敏提出的m + t r e e 【3 9 1 等。上述绝大多数m a m 方法以及已提出的其它算法，本 质上都是静态的，并且都是采用自项向下的递归处理方法。唯一例外的是m t r e e ， 它是一种动态平衡的外查找索引结构，它将m e t r i c t r e e 与数据库存取方法的优点 结合在一起，追求的设计目标是动态数据库存取。与其它动态平衡树一样，它采 用自底向上的生长策略。与s a m 方法类似，基于度量空间的索引方法在数据维数 不是太高的情况下效率非常高，但是随着数据维数的增加，大多数现有索引方法 的查询性能会下降。 以上索引结构各具特色，很难评定哪一种更优。即使在某一特定方面，也没 第4 页河南大学硕士研究生学位论文 有哪一种结构明显优于其它所有的索引结构。关于高维索引的研究还处于初步阶 段，技术还很不成熟，既没有公认的索引标准，也没有规范化的查询语言，而且 还没有建立起对各种结构的性能进行评估的有效方法。尽管如此，随着检索技术 的发展，有理由相信高维索引技术具有广阔的理论和应用前景。 1 2 2 高维索引应用 进入9 0 年代以来，基于内容的图像检索技术己成为一个比较活跃的研究领 域，既有理论研究成果，也出现了很多商用的图像检索系统。为了提高检索效率， 少数系统应用了高维索引技术，以下介绍几个典型的系统。 1 i b m 公司的q b i c ( q u e r yb yi m a g ec o m e n t ) 系统是第一个商品化的基于内容 的图像检索系统，q b i c 系统也是第一个应用了索引技术进行查询的商用系统。其 索引策略是先采用降低维数的方法即k l ( 卡洛) 变换对特征空间进行维数降低，然 后使用r 半t r e e 索引结构对高维特征进行索引。它主要集中在非语义内容的图像和 视频检索，并采用多种图像特征( 如颜色直方图、纹理及目标形状等) 来检索图 像。 2 v i r a g e 是美国d h , 7 , i ，f 大学圣迭戈分校设计的一个基于内容的检索系统。针对大 型图像库需要解决的快速索引问题，v i r a g e 先后提出了s s t r e e 和v a m s p l i t t r e e 等索引结构实现对高维特征的索引。与q b i c 类似，v i r a g e 支持基于颜色、颜色布 局、纹理和结构的可视查询。不仅如此，v i r a g e 还支持上述4 种特征查询的任何组 合查询。 3 i m g r e t r 是由清华大学设计的基于内容的w w w 图像搜索引擎。i m g r e t r 系统是面向多媒体制作图像素材库的，采用g s s t r e e 作为系统相似性查询的索引 结构。提取的图像特征包括主颜色、纹理、颜色直方图等通用特征。 上述系统初步实现了图像数据库的相似性查询，通过高维索引技术的应用在 某种程度上提高了检索的效率，但仍存在很多问题，例如索引结构不理想，随着 数据维数的升高，高维索引结构的性能急剧下降；特征的提取和相似性度量缺乏 具体应用领域特点，因而建立的索引结构检索效果不明显等。 1 3 论文结构 本文主要内容是对海量数据高维索引结构的相关研究，将按照以下结构组织 和论述： 河南大学硕士研究生学位论文第5 页 第一章绪论：主要介绍高维数据索引结构的研究背景和意义，国内外的研究现状， 并给出论文结构。 第二章高维数据索引技术的预备知识：系统论述高维索引领域研究的基拙知识、 基本概念和定义。首先介绍了高维数据的相似性查询方法；然后详细介绍 了向量空间和度量空间的高维索引结构；其次讨论了高维索引面临的问 题；最后给出了高维索引技术的评价准则。 第三章海量数据的距离分布研究：详细介绍了提取图像的颜色、纹理和形状三种 不同特征的比较经典的方法，对特征向量归一化的方法，特征向量之间的 距离计算方法，最后通过实验分析了分类图像库和混合图像库中高维特征 向量距离分布的特点和规律。 第四章k v p - t r e e ：主要介绍了结合k - m e a n s 聚类方法刚和m t r e e 的结点结构对索 引结构v p t r e e 的改进所形成的新的索引结构k v p t r e e ，包括k v p t r e e 的设计思想、结点结构、建树过程、查询以及对其的性能分析。 第五章总结和展望：这部分对本文的内容进行了总结，介绍了本文的主要工作以 及下一步工作的研究思路。 第6 页河南大学硕士研究生学位论文 第二章预备知识 本章系统的介绍了高维索引领域研究的基拙知识、基本概念和定义。首先介 绍了高维数据的相似度量方法；然后详细介绍了向量空间中具有代表性的高维索 引结构r - t r e e 、r * - t r e e 、矛d k - d b - t r e e ，度量空间中具有代表性的高维索引结构 m t r e e s n m + 一t r e e ；其次讨论了高维索引面临的问题；最后给出了高维索引技术的 评价准则。 2 1 高维数据的相似性查询 在高维索引结构中，高维数据的相似性查询是最基本也是最重要的操作。与 传统关系数据库基于关键字的查询相比，高维索引结构要求支持多种不同类型的 相似查询，如最近邻查询、区间查询、近似查淘等。这些查询通常要求在数据库 的所有数据对象中查找与给定查询对象相似的数据对象。接下来，将简要介绍高 维索引结构中相似性查询的基本概念和主要思想。 要进行相似性查询必须首先定义相似性度量，任何相似性度量都是以两个对 象为输入变量来确定一个非负的实数值，代表两个对象之间的相似程度。在定义 相似性查询之前给出相似性度量的定义。 一近似查询和最近邻( n e a r e s tn e i g h b o r ，n n ) 近似查询是两个主要的查询形 式。与这两种查询相对应，即有两种不同的相似性定义。 定义2 1 相似 对象p 和q 被称作e - 相似，当且仅当它们之间的距离小于，即6 ( p ，c o e ( 当= 0 时，称两个对象相同) 。 定义2 。2n n 相似 设p ，q o ，p 和q 被称作n n 一相似，当且仅当vo o ，o q ：6 ( p ，q ) 6 ( p ，o ) ，即o 中任何其它对象与p 之间的距离都大于q 与p 之间的距离。 在定义2 1 和定义2 2 的基础上，即产生了e 相似查询和n n 相似查询的定义。 定义2 3 相似查询 所谓e 相似查询，即：给定一个查询对象q u e r y ，在o 中寻找与该对象e 相 似的所有其它对象，这些结果对象构成的集合可表示为 r e s u l t o6 ( q u e r y ，r e s u l t ) e 相似查询意味着用户感兴趣的是那些与目标对象之间的相似度大于( 即它 河南大学硕士研究生学位论文第7 页 们之问的距离小于) 某个给定阈值的对象。 定义2 4n n 相似查询 所谓n n 相似查询，即：给定一个查询对象q u e r y ，在o 中寻找与该对象n n 相似的对象，这些结果对象构成的集合可表示为 r e s u l t 0 v o o ，o r e s u l t ：6 ( q u e r y ，r e s u l t ) 6 ( q u e r y ，o ) 【4 1 】 在基于内容的图像检索c b i r ( c o n t e n t b a s e di m a g er e t r i e v a l ) 的应用中，解决 相似查询通常是基于图像的特征进行的。c b i r 通常先提取图像的特征( 如图像 的颜色、形状、纹理等特征) ，并将它们表示为高维的特征向量，即高维特征空 间中的一个点，从而把图像的基于内容相似搜索转化为对高维特征空间中数据点 的相似查询。 在没有索引结构支持的情况下，从图像库中查找与给定的查询对象相似的图 像，需要将查询对象的特征与图像库中所有图像的特征一一进行比较，从而找到 满足条件的结果。当图像库的规模较小时，这种顺序扫描的方式是可取的。但是 随着图像库的规模越来越大，传统的顺序扫描方式显然无法满足用户的需求，这 就必然要求有一个合理的索引机制来辅助大规模图像库的基于内容相似搜索。 由于图像的特征数据通常是数十维甚至上百维的高维数据，而传统的用于低 维数据的索引机制几乎都不能直接用于高维空间。这就迫切地要求建立有效的高 维索引机制，以提高大规模图像库基于内容相似搜索的性能。这也正是本文所要 研究的重要问题。 2 2 向量空间和度量空间的高维索引结构 目前的高维索引方法可以分为两大类，一类是向量空间索引结构s a m ( s p a t i a l a c c e s sm e t h o d ) ，另一类是度量空间索引结构m a m ( m e t r i ca c c e s sm e t h o d ) 。下 面首先介绍向量空间和度量空间中索引结构的异同，然后介绍向量空间和度量空 间中几种比较常见的索引结构。 2 2 1 向量空间和度量空间中索引结构的异同 对于高维数据索引结构，根据构建索引结构中采用的数据信息及相似度量的 方法的不同，可分为向量空间索引结构和度量空问索引结构。向量空间和度量空 | 、日j 索引结构有着不同的侧重点，但也有相通之处，它们之间主要的异同点如下【4 2 】： 1 ) 向量空间可以看作是带有坐标信息的特殊的度量空间。在一定条件下，这 第8 页河南大学硕士研究生学位论文 两种空间是可以相互转换的：快速映射算法就是一种将度量空间中对象转换为具 有低维坐标的向量空问中的点的算法；而当在向量空间中定义好一个距离函数且 只耿物体之间的距离信息时，就将向量空间转换成了度量空间。不难看出，度量 空间中的索引结构比向量空间中的索引结构具有更普遍的适用范围，其用到的信 息更少，而其难度也更大。 2 ) 进行相似性查询时，度量空间中算法执行的主要代价被认为是计算距离函 数的占用c p u 的代价，因此度量空间索引结构主要考虑的是如何减少距离函数的 计算次数；而向量空间查询的主要代价则是磁盘读取时的i o 代价，因此向量空间 中的索引结构主要考虑的是如何降低读取磁盘的i o 次数。 3 ) 在度量空间索引结构中，为实现相似性查询，用到的唯一方法就是距离函 数的三角不等式性质；而在向量空间中除了利用距离函数外，更主要的是利用数 据的坐标信息。因此，向量空间的索引结构上的查询算法设计比度量空间的索引 结构上的查询算法具有更大的灵活性，因为它不仅可以利用距离信息，还可以利 用物体的位置信息，例如k dbt r e e 、r t r e e 等，这些算法都广泛使用了数据坐标 信息。 2 2 。2 向量空间常见高维索引结构 下面重点介绍度量空间中常见的高维索引结构r - t r e e 、胁一t r e e 及其 k d b - t r e e 。 1 r t r e e r - t r e e 是用于高维数据空间中的比较成功的索引结构，它是一种平衡树结构， 具有类似于b t r e e 的层次结构。在r t r e e 中存放的数据并非原始数据，而是这些数 据的最小外接矩形( m b r ) 。一个r t r e e 索引对应一组分层嵌套的多维超矩形。它是 一种动态索引结构，插入和删除操作可以和查询操作交替进行而不需要周期性地 重新组织索引结构。 r t r e e 由叶子节点和非叶子节点构成，其中非叶子节点的结构为： n ：( c 1 ，c 2 ，c n ) ( m n n m n ) c i = ( r ，c h il d p o i n t e r ) ( i = l ，2 ，n ) ， 其中c h i l d p o i n t e r 是指向子树的指针，r 是包含子树中所有矩形的最小边界 矩形m b r ( m i n i m u mb o u n d i n gr e c t a n g l e ) ； 叶子节点的结构为： 河南大学硕士研究生学位论文第9 页 l ：( e 1 ，e 2 ，e n ) ( m l n m l ) e i = ( r ，o i d ) ( i = 1 ，2 ，n ) ， 其中，r 是索引对象的最小边界矩形m b r ，o i d 是对象的标识，指向数据库中的 对象。如图2 1 是一个简单的r t r e e ，它反映了r t r e e 的结构特点。 旨嗝 墨一 图2 1r - t r e e 的例子 2 r 木一t r e e r 水t r e e 是r - t r e e 的一种最成功的变种，r * - t r e e 同r - t r e e 的主要区别就在于它 改进- r - t r e e 的插入算法。r * - t r e e 采用了强制的重新插入策略。当节点中的记录 数上溢时，并不是简单的分裂该节点，而是将距离中心最远的一部分记录删除并 重新插入到树中。但如果索引树的某一层次己经进行过强制重插时，则按照j 下常 的分裂算法进行分裂。 r * - t r e e l f , 其它r 树及其变种具有很大的优势：在对每个查询文件和数据文件， 胁一t r e e l l 其它r 树及其变种需要更少的磁盘访问量；由于r 木一t r e e 保存了次序( 彼 此靠近的矩形更有可能存在同一个页面上) ，因此对小的查询矩形，胁一t r e e 能获 得比大的查询矩形更好的性能，因为对大的查询矩形，存储利用率更加重要，r 木有 最好的存储利用率；使用强制重新插入的概念，降低了平均插入的花费。 3 k d b t r e e k - d - b - t r e e 是最早支持高维数据索引的一种动态索引结构，它综合了b 树磁盘 驻留的特性并i k - d - t r e e 支持高维数据索引的特性。k d b t r e e 是一种严格的平衡 树，它的节点分为叶子节点和非叶子节点。每个节点代表一个多维超矩形，根节 点代表的超矩形包含所有的数据，同一层次的节点所代表的数据区域没有重叠， 非叶子节点所代表的数据区域包含子节点所代表的数据区域之和，叶子节点覆盖 其中的所有的数据点。 第10 页河南大学硕士研究生学位论文 其中非叶子节点的结构为： n ：( c l ，c 2 ，c n ) ( n a n n m n ) c i = ( r ，c h i l d p o i n t e r ) ( i = l ，2 ，n ) ， 其中c h i l d p o i n t e r 是指向子树的指针，k d b 是包含子树中所有矩形的最小边 界矩形m b r ( m i n i m u mb o u n dr e c t a n g l e ) ： 叶子节点的结构为： l ：( e 1 ，e 2 ，e n ) ( m l n m l ) e i = ( r ，o i d ) ( i = l ，2 ，n ) ， 其中，r 是索引对象的最小边界矩形m b r ，o l d 是对象的标识，指向数据库中的 对象。如图2 2 是它的一个例子，从中可看出，它的结构类似于b t r e e 。 图2 - 2k d b t r e e 的例子 2 2 3 度量空间常见高维索引结构 下面重点介绍度量空间中常见的高维索引结构m - t r e e 及其变种m + - t r e e 。 1 m t r e e 从性能方面来考虑，位置空l 、日j 访问系列方法适用于同访问辅存页面的时间相 比，计算两个特征向量或者数据对象的包络之间距离的时间可以忽略不计的情况， 但是对于多媒体应用而言，这个假设往往是不成立的，数据对象的相似性距离的 计算往往很复杂，时间不能简单的忽略。m t r e e 这种索引结构不仅考虑到辅存页 面的访问时间而且还考虑到距离计算的复杂度。它的基本思想是利用度量空间中 数据对象之间的距离所满足的三角不等式和节点中预先保存的距离来减少距离计 算次数并减少搜索量。如图2 - 3 所示是一个m - t r e e 的例子。 m t r e e 是一个动态分页平衡树，可以处理动态数据文件，不需要周期的重组。 河南大学硕士研究生学位论文第11 页 m - t r e e 的节点分为叶子节点和非叶子节点。实验表明，m - t r e e 的性能优于r 木一t r e e ， 而且维数越高，m - t r e e 性能的优越性越明显。 m - t r e e 的非叶子节点是由四元组组成： i = ( o r ，p t r ( t ( o r ) ) ，r ( o r ) ，d ( o np ( o r ) ) ) 图2 - 3 一个m t r e e 的示例 其中o r 是路径对象的特征值，p t r ( t ( o r ) ) 是指向子树根节点的指针，r ( 0 r ) 是 0 r 的覆盖半径，d ( o np ( o r ) ) 是o r n 父节点的距离。 m - t r e e 的叶子节点由三元组组成： l = ( o j ，o l d ( o j ) ，d ( o j ，p ( o j ) ) ) 。 其中0 r 是路径对象的特征值，o i d ( o j ) 是对象的标识，是指向实际的数据库 对象的指针。d ( o j ，p ( o j ) ) 是o j n 父节点的距离 2 m + 一t r e e m + - t r e e 是一种新型的高维索引结构，充分利用了m - t r e e 数据分片方法和 m v p t r e e 数据分片方法的优点，是一种新的高维数据空间划分策略，即在基于距 离划分的基础上，进行基于关键维的二次划分，从而将一个子空间进一步分割成 一对孪生子空间，并且利用孪生兄弟节点间的数据重分配保证数据空间的利用率。 用这种索引结构进行相似性查询，既有通过超球体包络的过滤，又有通过关键维 进行的二次过滤。在通过关键维分割的两个子空间之间进行查询过滤时不需要额 外的距离计算。这样一来该索引结构在不增力h c p u 代价的同时，大大地提高了它的 过滤性能，相似性查询的性能也就随之改善。 2 3 高维索引面临的问题 第12 页河南大学硕士研究生学位论文 对外部存储设备中的数据建立索引结构可以在查询时迅速定位所需数据，提 高查询效率。研究者提出了许多有效的针对多维数据索引结构。其中树型索引结 构是最常用也是最普遍的索引方法。下面首先介绍高维树型结构的构建方法，然 后以树型结构为例介绍维数灾难现象的产生。 2 3 1 高维索引的结构 通常以数据空间中的塔式聚类思想来构造树型索引结构。在树型索引结构中， 数据点被存储在树的叶子结点上，每一个数据点存储在一个叶子结点上，不同的 叶子结点中没有相同的数据。数据结点被组织成一个塔式结构的目录，一个目录 结点指向一棵子树的集合。一般来说，叶子结点的信息存储结构域目录结点的方 式完全不同。目录结点的存储结构一般包含( 关键字、指针) 对。不同的索引结 构其关键字信息也不相同，b 树中关键字信息是一维数据的范围，而r 树系列中则 是m b r 信息，s s 树中是超球信息。一个单独的目录结点作为根结点，它用来作为查 询和更新工作的入口结点。索引结构是高度平衡的，也就是说，从根结点到各层 数据项的距离是相同的，此距离也被称为树的“高度”。叶子结点中能够包含的 数据点数目称为数据结点的扇出度( f a n - o u t ) 。大部分索引结构采用了将根目录 或整个目录结点放在内存中而将下层目录和数据结点放在磁盘上的组织形式，性 能上以降低磁盘的i o 代价为目的。在高维索引结构中，结点的有效利用率不能达 至i j l 0 0 ，一般要求结点的最小有效利用率要大于4 0 。如图2 4 是一个简单的树型索 引结构示意图。 ) d i r e c t o r y p a g e s ) d a t a 姆s 图2 4 树型索引结构示意图 2 3 。2 高维索引的管理 为有效的读取外存中的数据，一般选择合适的参数使叶子结点中的数据恰好 充满个二次存储设备的页。在目前的操作系统中，磁盘的数据页面大小对于程 河南大学硕士研究生学位论文第13 页 序员来说是隐藏的，但是，对磁盘上顺序存储的数据进行连续读取，在性能上还 是由于离散读取数据的方式。在树型索引结构中，由用户定义数据页面大小，页 面大小一般从几k - n 几百k 字节。 为了更有效的查询数据，位于同一页面中的数据一般是很好的聚类在一起的， 也就是说，距离相近的数据对象一般被存储在同一页面中。每个页面也可由页面 区域( p a g er e g i o n ) 来表示，它是数据空间的一个子集。页面区域可以是一个超 立方形状的或超球体形状的实心凸起区域。采用塔式结构组织的页面区域一定要 完全包含在它的父区域内，相类似，所有的存储在子树上的数据对象也都包含在 其根节点的页面区域内。页面区域是其包含的数据对象的一个近似表示，页面区 域的表示是经过优化的。如果页面区域的表示过大，那么索引本身也会变大，而 且会导致查询性能下降。 按照结点的建立方式不同，树型多维索引结构可以进一步分为数据点划分和 空间划分两大类。基于数据点划分的