（计算机软件与理论专业论文）支持最近邻查找的高维空间索引.pdf

论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果。论文中除 了特别加以标注和致谢的地方外，不包含其他人或其它机构已经发表或撰写过的 研究成果。其他同志对本研究的启发和所做的贡献均已在论文中作了明确的声明 并表示了谢意。 作者签名： 麦量军蕴 论文使用授权声明 日期：塑! ! z ：墨：， 本人完全了解复旦大学有关保留、使用学位论文的规定，即：学校有权保留 送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内 容，可以采用影印、缩印或其它复制手段保存论文。保密的论文在解密后遵守此 规定。 作者签名：墨红圣丝导师签名：幺巡日期：竺! z ：量z 复且大学博十毕业论文：支持最近邻查找的高维空间索引 张军旗 摘要 在图像、生物信息、医学成像、时间序列等领域需要对大数据集进行相似性 查询。通过特征转换将数据对象特征映射为高维向量空间的特征向量，把相似性 查询转换为向量空间的最近邻查询，即给定查询数据q 及整数k ，从数据库中找 出距离q 最近的k 个数据。为了提高查询效率，研究者提出各种索引结构管理 特征向量。这些索引结构在维数升高时性能会急剧下降，即“维灾”。针对高维 数据索引结构的现状，我们在该领域进行了深入研究，取得了一定的成果。 为了提高索引的检索效率，增强对高维的承受力，提出了多个具有良好性能 的索引结构，并提供了利用这些高维索引支持图像相关反馈的方法。 主要内容如下： 首先，为了对聚类与查询性能之间的关系进行理论分析。提出一种新的基于 聚类分解的高维度量空间b + 一t r e e 索引，它通过聚类分解对数据进行更细致的 划分来减少查询的数据访问。对聚类与查询代价的关系进行了讨论，通过查询代 价模型给出了最小查询代价条件下的聚类分解数目等的理论计算公式。实验显示 提出的索引方法明显优于i d i s t a n c e 等度量空间索引，最优聚类分解数的估计 接近实际最优查询时所需的聚类参数。 然后，为了进一步改进高维数据库查询的效率。提出一种基于查询采样进行 数据分布估计的方法，并在此基础上提出了一种支持最近邻查询的混合索引，即 针对多媒体数据分布的不均匀性，有选择的使用树状索引和顺序扫描技术，建立 统一的索引结构。建立混合索引的具体步骤为：首先通过聚类分解分割数据并建 立树状索引；然后使用查询采样算法，对数据实际分布进行估计；最后根据数据 分布的特性，把稀疏数据从树状索引中剪裁出来进行基于顺序扫描策略的索引， 而分布比较密集的数据仍然保留在树状索引中。在五个真实的图像数据集上进行 了充分的实验，结果显示提出的索引方法明显优于i d i s t a n c e 等度量空间索 引，在维数达到三百多维时查询效率仍高于顺序扫描。实验结果还证明提出的查 询采样算法在采样数据量仅为( n 为数据量) 的情况下就可以获得的满足索 引需要的分布估计结果。 最后，为了使得提出的索引结构能够在图像检索中应用，提出了利用高维索 引支持用户相关反馈的方法。 关键词：最近邻查询，采样，高维索引结构，边缘数据，聚类分解 复且大学博七毕业论文：支持最近邻查找的高维审问索引张军旗 a b s t r a c t m a n ye m e r g i n gd a t a b a s ea p p l i c a t i o n ss u c ha si m a g e ，t i m es e r i e sa n ds c i e n t i f i c d a t a b a s e s ，m a n i p u l a t eh i g hd i m e n s i o n a ld a t a i nt h e s ea p p l i c a t i o n s ，o r l eo ft h em o s t f r e q u e n t l y u s e da n d y e te x p e n s i v eo p e r a t i o n s i st of i n d o b j e c t s i nt h e h i g h - d i m e n s i o n a ld a t a b a s et h a ta r es i m i l a rt oag i v e nq u e r yo b j e c t n e a r e s tn e i g h b o r s e a r c hi sac e n t r a lr e q u i r e m e n ti ns u c hc a s e s t h e r ei sal o n gs t r & d mo fr e s e a r c ho n s o l v i n gt h en e a r e s tn e i g h b o rs e a r c hp r o b l e m , a n dal a r g en u m b e ro fm u l t i d i m e n s i o n a l i n d e x e sh a v eb e e nd e v e l o p e df o rt h i sp u r p o s e h o w e v e rt h e s ei n d e x e st u r nw o r s ew i t i l t h ed i m e n s i o ng r o w t h , w h i c hi sc a l l e dd i m e n s i o n a l i t yc u r s e i no r d e rt oi m p r o v et h eq u e r ye f f i c i e n c y , k - m e a n sc l u s t e ra p p r o a c hi so f t e nu s e d t oe s t i m a t et h ed a t ad i s t r i b u t i o ni nt h ec o n t e x to f h i g hd i m e n s i o n a lm e t r i cs p a c ei n d e x b u ti np r e v i o u sw o r k , t h ep a r a m e t e r so fc l u s t e r i n ga r eu s u a l l ys e l e c t e da c c o r d i n gt o s o m eh e u r i s t i cm a n n e r i nt h i sp a p e r , w ep r e s e n tan e wh i g hd i m e n s i o n a li n d e x a p p r o a c h c l u s t e rs p l i t t i n gb a s e dh i g hd i m e n s i o n a lb + - t r e e t h r o u g hc l u s t e rs p l i t t i n g , t h ed a t as p a c ei sp a r t i t i o n e dm o r ef i n e l yt or e d u c et h ec o s to fd a t aa c c e s s t h e r e l a t i o n s h i pb e t w e e nc l u s t e ra n dt h eq u e r yc o s ti sd i s c u s s e d ，a n db a s e do nt h eq u e r y c o s tm o d e l ，w ep r e s e n tf o r m u l a st oc o m p u t et h e “o p t i m a l p a r a m e t e r so ft h ec l u s t e r w h i c hc a l lm i n i m i z et h eq u e r yc o s ti nt h e o r y o u re x p e r i m e n tr e s u l t ss h o wt h a tt h e e f f i c i e n c yo f o u rm e t h o d si sb e t t e rt h a ni d i s t a n c e ，m - t r e ea n ds e q u e n c es c a n , a n dt h e p a r a m e t e r sc o m p u t e db y0 1 1 1 f o r m u l a sa r ev e r yc l o s e dt ot h er e a lo p t i m a lo n e i no r d e rt oi m p r o v et h eq u e r ya n s w e r i n go fh i g h - d i m e n s i o n a ld a t a b a s e ，d a t a d i s t r i b u t i o ni sn e c e s s a r yf o rs e c l e 埘i n ga p p r o p r i a t ei n d e x i n gs t r a t e g y h o w e v e r , t h e t r a d i t i o n a ld a t ad i s t r i b u t i o nm o d e lc a nn o te s t i m a t et h ea c c u r a t ed a t ad i s t r i b u t i o ni n t h ec o m p l e xr e a lm u l t i m e d i ad a t ao f i m a g ea n dv i d e o t h i sp a p e rp r e s e n t sam e t h o dt o e s t i m a t et h ea c c u r a t ed a t ad i s t r i b u t i o nb a s e do nq u e r ys a m p l i n ga n dp r o p o s e san o v e l h y b r i di n d e xt os p e e du pp r o c e s s i n go fh i g h - d i m e n s i o n a lk - n e a r e s tn e i g h b o r ( k n n ) q u e r i e s t h ep r o p o s e dh y b r i di n d e xi m p r o v e st h eq u e r ye f f i c i e n c yb ya d a p t i v e l y s e l e c t i o nd i f f e r e n ti n d e xs t r a t e g i e sf o rt h ed a t aw i t hd i f f e r e n td i s t r i b u t i o n i nt h ef i r s t s t e pt h ec l u s t e ra n a l y s i sa n dc l u s t e rs p l i t t i n gm e t h o d sa r ea p p l i e dt oc o n s t r u c ta t r e e - b a s e di n d e x ，t h e nt h e r e l a t i o n s h i p b e t w e e nd a t ad i s t r i b u t i o na n di n d e x p e r f o r m a n c ei sd e r i v e db ys a m p l i n g a tl a s ts o m et r e eb r a n c h e sw i t l ls p a r s ed a t aa r e e x t r a c t e df o rl i n e a rs c a n , w h i l et h ea g g r e g a t ed a t ar e m a i n si nt h et r e e e x t e n s i v e e x p e r i m e n t so nf i v e r e a li m a g ed a t as e t ss h o wt h a tt h ep r o p o s e dh y b r i di n d e x 2 复旦大学博+ 毕业论文：支持最近邻盒找的高维空间索引张军旗 s t r u c t u r ep e f f o n 删sb e n e rt l l 柚i d i s t a n c e m - t r e ea n dl i n e a rs c a n , a n ds c a l e sb e t t e r w i t hd i m e n s i o n s n 地i n d e xi ss t i l lf a s t e rt h a nl i n e a rs c a nw h e nt h ed i m e n s i o n r e a c h e s 3 3 6 t h ee x p e r i m e n t sa l s os h o wt h a tt h ep r o p o s e dq u e r ys a m p l i n ga l g o r i t h mc a l l o b t a i nt h ea c c u r a t ed a t ad i s t r i b u t i o nw h e nt h em o u n t o f s a m p l i n gi sb e l o w4 nm i s t h es i z eo f d a t as e t ) i ng e n e r a l ，i n d e xc a l ln o ts u p p o r tt h er e l e v a n c ef e e d b a c ki nt h ei m a g er e t r i e v a l p r o c e s s i nt h i sd i s s e r t a t i o n , an o v e la l g o r i t h ms u p p o r t i n gr e l e v a n c ef e e d b a c ku s i n gt h e p r o p o s e dh i g h - d i m e n s i o n a li n d e x k e yw o r d s ：n e a r e s tn e i g h b o rq u e r y , h i g hd i m e n s i o n a li n d e x ，s a m p l i n g ，c l u s t e r s p l i t t i n g 3 复日大学博十毕业论文：支持最近邻查找的高维窄问索引张军旌 1 研究背景及意义 第一章引言 随着高速传输和高效存储技术的发展，大量信息以计算机可读的形式存在， 其中不仅包含文字和声音，更主要的是图形、图像和视频等多媒体视觉信息。面 对日益增多的可访问到的多媒体信息，为了不迷失在其中，人们往往会提出快速 查询的需求，称为相似性检索，即从数据库中查找出与给定的查询对象最为相似 的一些或一个对象。但数据库的数据量很大时，如何实现快速查询成为多媒体信 息检索等应用领域的关键问题。自2 0 世纪7 0 年代起，随着c a d 、g i s 、生物信 息及医药影像等应用的出现，逐渐提出对高维数据相似查询的需求，对于高维数 据，由于其自身的无序性、复杂性等特点，使得b + 树等传统关系型数据库中的 索引结构无法使用，为此，人们开始了高维索引结构的研究，在过去的几十年中， 大量的高维索引结构被相继提出，其中大都为树型索引结构，如k d 树、k d b 树、r 树、r 树、s s 树、s r 树、x 树、t v 树、i q 树、a 树等。但当维数较高 时，都面l 晦维灾问题。除了树型结构外，v a f i l e 、l p c f i l e 等采用了量化压 缩的方法来减少查询过程中的磁盘访问代价，但其查询性能加速限制在很小的范 围内，仍难以满足实际应用的需要。 多媒体信息的海量以及人们对多媒体信息检索需求的急剧增大，使得快速的 相似性检索显得日益重要，而已有的高维数据索引结构仍难以满足实际应用的需 要，为此，深入的进行高维索引结构及相关的相似性查询算法的研究具有重要的 研究意义与实用价值。 2 研究目标及主要贡献 通过以下几个研究思路以期望提出更为有效的高维数据索引结构及相应的 查询算法： 1 ) 近年来，通过把高维数据对象映射到一维距离空间，采用8 + - t r e e 进行索 引得到了较深入的研究。为了获得数据分布信息，i d i s t a n c e 采用k - m e a n s 聚类 方法对数据分布进行分析，并在此基础上进行b + - t r e e 索引。由于高维空间中普 遍存在聚类相互重叠，聚类内部数据分布比较稀疏等现象，传统查询算法一凡是 与查询覆盖区域相交的据数据区域( 如聚类) 都进行数据搜索，会引起对大量聚 类子类的搜索，查询效率不高。i d d i s t a n c e 通过选择合适的初始查询半径，并进 行逐步扩展来克服上述问题，但是其查询半径的扩展需要根据经验( 或反复试验) 来确定，缺乏理论与系统化的方法。已知工作虽然对如何选取最优参考点进行了 4 复日大学博+ 毕业论文：支持最近邻查找的高维空间索引张军旗 大量的研究，但是，聚类与查询效率的关系等问题并未得到充分的讨论。例如在 索引参考点确定后，选取不同的子聚类数目将如何影响查询效率? 另一方面，鉴 于高维数据集上进行k - m e n s 聚类时，子类越多( k 越大) ，聚类的计算代价越 高昂，如何在k 值一定的情形下，最小化查询代价也是采用聚类分析的高维度 量空间索引所必须解决的问题。 2 ) 对于常见的介于几十到几百维的多媒体数据，如何选择索引策略是个难 题，需要考虑数据集的数据分布与索引策略之间的关系。树型索引能有效过滤密 集数据，而顺序扫描策略对检索稀疏数据更加有效。对于大量中等规模维数的多 媒体数据，使用树型索引时，稀疏数据不可避免地加入到密集数据的聚类中，使 得聚类平均半径过大，索引过滤能力减弱，随之而来的是数据过滤能力的下降， 直至低于顺序扫描的效率；使用顺序扫描策略时，由于数据维数并没有到达足够 高，数据的分布仍不均匀，理论上，此时彻底抛弃树型索引也是不合适的。因此 对于大量中等规模维数的多媒体数据，使用单一索引策略存储所有数据因无法区 分数据，局限了树型过滤技术与顺序扫描方法各自优势的发挥，降低了索引对数 据维数变化的承受力。 3 ) 在传统数据库中，查询通过数据属性精确匹配查找，但在现代数据库中， 如多媒体数据库中，数据的属性特征从数据复杂的信息中提取出来，这些特征定 义在向量空间或度量空间。在多媒体数据库中，对象间的相似性查找是基本的需 求，如查找与查询图像最相似的图像，也称“最近邻查找”，对象问的相似性只 能通过距离函数进行比较，而对象的数据意义和真实意义问存在语义鸿沟，用户 提交查询时，很多时候并不能很精确的表达先要查询的对象，所以需要利用用户 相关反馈判断返回结果中哪些相似( 或不相似) ，进一步修改查询要求，提高查 询效果。但是一般的索引结构无法支持相关反馈。 在上面这些研究思路的指导下，提出了数种高效的、新的高维索引结构，并 将其中的一些结构应用于实际系统之中。主要贡献有： 1 ) 针对上述问题，提出了一种新的高维度量空间b + - t r e e 索引：( 1 ) 为了克 服聚类数据稀疏、相互重叠等问题，提出了聚类分解的概念，即按聚类中心把聚 类超球分解为不同半径的空腔超球体( 也称为聚类环) ，对这些空腔超球体分别 进行索引有利于提高数据过滤效率。( 2 ) 对聚类进行分解其实是根据数据分布对 数据进行更细致的划分，显然，过度地划分数据并不能带来更高的查询效率。为 了考察聚类、聚类分解与查询代价的关系，给出采用聚类分解的高维度量空间 b + - t r e e 索引的查询代价模型，即通过对数据点间距离的概率分布的估计，求得 k n n 查询代价的数学期望，并进一步推导出使得查询代价最小化的聚类分解数 的计算公式。( 3 ) 并且对查询代价最小条件下的数据聚类数且进行了讨论。 复且大学博士毕业论文：支持晟近邻查找的高维卒问索引张军旗 2 ) 提出一种新的支持中等维数多媒体数据查询的混合索引方法，能够自适 应地对实际分布不同的数据采用树型过滤技术或顺序扫描方法。树型索引与顺序 扫描的结合是一种平滑的过渡，随着维数的增高，树型索引的成分逐渐减小并过 渡到顺序扫描。由于实际数据的分布非常难于把握，我们提出一种构造性的方法， 采用先根据数据实际分布建树型索引，再根据数据分布对索引性能的影响自适应 地对树的分支裁剪。为了得到数据的真实分布，首先对数据进行聚类分析，再使 用聚类分解方法对各聚类内部数据按分布情况进一步划分。数据划分后，我们提 出复杂度仅为的查询采样算法，以聚类环为单位，得到数据被访问的平均概 率，据此分析数据实际分布对不同索引效率的贡献，并从树形索引中剪裁稀疏数 据直接存储到顺序文件中用于顺序扫描。实验显示提出的混合索引方法明显优于 i d i s t a a c e 等度量空间索引，在维数达到三百多维时查询效率仍高于顺序扫描。 3 ) 继承了h a f n e r 使索引距离成为查询距离下界的方法和q i c - m t r e e 的三个 距离函数框架，在b + 树上实现了基于聚类的支持用户相关反馈的索引结构，使 用区域估计加快查询速度，利用过滤参照点作为比较距离函数，在索引中存储数 据集与第二个参照点的距离，在查询中利用三角不等式进行过滤，不需要在线计 算。 3 论文结果及主要内容 主要介绍本人在高维数据索引结构领域的研究成果及应用，将按照以下结构 组织和论述： 第一章简介：主要阐述高维数据索引结构的研究背景及意义，以及的主 要研究目标和贡献，并给出文章的结构； 第二章高维索引结构综述：系统论述了目前高维数据索引结构研究的现 状，包括高维数据的特点、高维索引结构的特点、高维数据的相 似性查询、矢量空间索引结构和度量空间索引结构，从该章的叙 述中可对高维索引结构的研究有各清晰的了解； 第三章图像检索：介绍了高维索引在图像检索领域应用时，需要了解的 背景知识。 第四章相关反馈：介绍了图像的相关反馈，提出一种支持用户相关反馈 查询的索引结构，并通过概率估计方法使聚类紧缩，以损失一定 的数据精度来大大提高查询速度，使图像检索能在通用数据库中 速度和查询效果两方面得到较大改善。 第五章基于聚类分解的高维度量空间索引b + t r e e ：提出一种新的基于 聚类分解的高维度量空间b + - t r e e 索引，通过聚类分解对数据进行 6 复旦大学博十毕业论文：支持最近邻查找的高维卒间索引张军旗 第六章 第七章 更细致的划分来减少查询的数据访问。对聚类与查询代价的关系 进行了讨论，通过查询代价模型给出了最小查询代价条件下的聚 类分解数目等的理论计算方法。 提出一种基于查询采样进行数据分布估计的方法，并在此基础提 出了一种支持最近邻查询的混合索引，即针对多媒体数据分布的 不均匀性，有选择的使用树状索引和顺序扫描技术，建立统一的 索引结构。为了实现混合索引，采用构造性方法：首先通过聚类 分解分割数据并建立树状索引：然后使用查询采样算法，对数据 实际分布进行估计；最后根据数据分布的特性，把稀疏数据从树 状索引中剪裁出来进行基于顺序扫描策略的索引，而分布比较密 集的数据仍然保留在树状索引中。 小结与今后工作：总结全文，并介绍目前关注的新问题。 7 复日大学博十毕业论文：支持最近邻查找的高维审问索引 张军旗 第二章高维索引综述 近年来，高维数据库的应用得到快速的发展，如海量的多媒体数据库、生物 信息学中庞大的d n a 数据库、图像数据库、科学数据库等，这些信息一般使用 特征抽取等方法映射为高维数据，然后通过计算这些高维数据之间距离实现相似 性查询。例如，对于图像数据，往往采用颜色直方图来表征一副图像，当需要从 数据集查找到与给定图像相似的图像时，通过计算颜色直方图之间的距离实现查 询。在这种背景之下，高维数据索引结构和适用于高维索引结构的相似查询算法 得到了人们的极大重视，而在己提出的众多高维索引结构中，有的特定工作在向 量空间中，而有的是针对度量空问而设计。本章将对高维索引结构研究的现状进 行较为详细的介绍，包括：高维数据及高维索引结构的特点、高维数据库的查询 方式、向量空间与度量空间中高维索引结构的异同及他们中有代表性的索引结构 简介、以及相似性查询算法等。 1 高维数据及索引结构的特点 所谓高维数据，是指高维空间中的数据，例如二维空间中的点、线段、矩形， 三位空间的球、立方体以及高维空间中的点数据等。一般来说，高维数据有以下 一些特点【1 】： 1 ) 复杂的结构：对于高维数据，它有可能是一个高维空间的点数据，也有 可能是复杂的多边形或多面体，一般不像传统的关系型数据库一样用固 定大小的条目来保存。 2 ) 动态特性：在插入和删除的过程中，还往往伴随着对数据本身的修改。 3 ) 数据的海量：高维数据库往往是比较大的，例如，一般的地图大概需要 几千兆的存储空间。 4 ) 多样化的操作：对高维数据库而言，没有标准操作，往往要根据实际应 用的需要确定。 5 ) 时间代价大：尽管对高维数据库的操作所花费的时间各不相同，但一般 远高于传统的关系型数据库的操作。 6 ) 不能排序：无法对空间数据进行线性排序以使得那些在高维空间中相邻 的数据仍然能够相邻。 正是由于高维数据具有以上这些特点，所以要求索引结构也相应具有以下一 些特征n 】： 1 ) 构造：由于数据可以在数据库以任意顺序插入或删除，其索引也应该与 复日大学博十毕业论文：支持最近邻查找的高维空问索引 张军旗 之保持一致，即索引结构也必须支持动态的插入和删除。 2 ) 二级三级存储管理：尽管主存容量日益增大，仍不能将一个完整的数据 库保存在主存中，因此索引结构要考虑到二级以及三级的存储管理。 3 ) 支持尽量多的操作：不能以牺牲其他的操作而支持某一种特定的操作。 4 ) 独立于输入数据及插入顺序：支持各种高维数据以及任意的插入顺序。 5 ) 可增长性：索引结构要能够适应数据库大小的增长。 6 ) 时间的有效性：查找速度必须是快速的。 7 ) 空间的有效性：一个索引结构相对于其原数据应是比较小的，要保证一 定的空间利用率。 8 ) 并行性及可恢复性。 2 高维数据查询方式 根据应用领域的不同，高维数据库的查询方式也各不相同。对于给定的数据 库d b ，常用的查询方式有f 1 】： 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 b l 0 = g ) 2 )点查询( p q ：p o i n tq u e r y ) ：给定点数据q ，从数据库中找出所 有包含点q 的数据： p q ( q ) = d d b q n 0 = g ) 3 )窗口查询( w q ：w i n d o wo u e r y ) ：给定一个d 维的矩形查询区间 1 8 ，从数据库中找出至少保混一个i 中的点的所有数据： w q ( q ) = d d b l l 4n o g ) 4 )相交查询( i q ：i n t e r s e c t i o nq u e r y ) ：给定具有一定形状的空 间数据a ，从数据库中找出至少包含q 中一点的所有数据： i q ( q ) = d e d b l g n 0 妒 5 )包含查询( e q ：e n c l o s u r eq u e r y ) ：给定查询数据q ，从数据库 中找出所有包含q 的数据： e m ( q ) = d e d b i g n 0 = 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 d b iq n o = d ) 7 )邻接查询( a q ：a ja c e n c yq u e r y ) ：给定查询数据q ，从数据库 中找出所有同q 邻接的数据： 9 复旦大学博士毕业论文：支持最近邻查找的高维审问索引张军旗 a q ( g ) = d d b i g n d g - r 、o = 其中q ，、o ，分别表示q 和0 的内部区域。 8 )范围查询( r q ：r a n g eq u e r y ) ：给定查询数据q 和查询距离门 限t ，从数据库中找出所有与q 距离小于t 的数据： r q ( g ，d = d d b | | p q 8 r 9 )k 一近邻查询( k n n q ：kn e a r e s t n e i g h b o rq u e r y ) ：给定查询 数据q 及整数k ，从数据库中找出距离q 最近的k 个数据： 阳v n ( q ，七) = 0 0 。q _ l d b i v e d b 0 0 o t - 1 ) ，u o , 一q l l i l e - g | l d 茎f 蔓k 一1 ) 当k = l 时，又称为最近邻查询。 在上面所述的几种查询方式中，范围查询和k 近邻查询的应用范围最为广泛，统 称为“相似性查询”，因此目前高维数据索引结构的研究主要集中在如何快速实 现相似性查询方面，尤其是k 近邻查询。 3 向量空间与度量空间索引结构及其异同点 对于高维数据索引结构，根据构建索引结构中所采用的数据信息及相似度量 的方法不同，可分为向量空间索引结构和度量空问索引结构。向量空间和度量空 间索引结构有着不同的侧重点，但也有相通之处，它们的异同简单总结如下： 1 )向量空间可被看作是带有坐标信息的特殊的度量空间。在一定条 件下，这两类空间是可以相互转换的：快速映射算法( f a s t m a p ) 【2 1 就是一种将度量空间中的对象转换为具有低维坐标的向量空 间中的点的算法；而当我们在向量空间中定义好一个距离函数而 只取物体之间的距离信息时，就将向量空间转换成了度量空间。 因此不难看出，在度量空间中的索引比在向量空间中具有更普遍 的适用范围，所用到的信息更少，难度也会更大。 2 )进行相似性查询时，在度量空间中算法执行的主要代价被认为是 计算距离函数的c p u 代价，因此度量空间索引结构主要考虑的是 减少距离函数的计算次数；而在向量空间查询的主要代价被认为 是读取磁盘的i o 代价，向量空间中的索引结构主要考虑的是减 少磁盘的i o 次数。 3 )在度量空问索引结构中，为了实现相似性查询，所唯一用到的方 法就是距离函数的三角不等式性质；而在向量空间中除了利用距 离函数外，更主要的可利用信息是数据坐标信息。因此，在向量 空间中的索引结构上设计查询算法时，比在度量空间中具有更大 1 0 复旦大学博十毕业论文：支持最近邻盘找的高绺空间索引张军旗 的灵活性，因为它不仅可以利用距离信息，还可以利用物体的位 置( 坐标) 信息，比如普遍使用的k d b 树3 1 ，r 树等，它们 都广泛使用了数据坐标信息。 4 向量空间高维索引结构 4 1 向量空间高维索引结构分类 在近几十年对向量空间高维数据索引的研究过程中，已经提出了大量的索引 结构。根据这些索引结构的特点分类如下： 1 )根据处理数据的类型，可以分为点数据类和空间数据类。点数据类 是指那些只能处理点数据的索引结构，如k d 树 5 1 、t v 树【6 1 等； 空间数据类指既能处理点数据，又可以处理线、矩形等具有一定形 状的数据的索引结构，如r 树，r + 树等。 2 ) 根据索引创建时数据组织形式，可以分为静态结构类和动态结构类。 静态结构类是指用批处理的方式将全部数据构建成索引，不能支持 动态的插入和删除，如p a c k e d r 树【8 1 ；而动态结构类指数据依次 插入而生成的索引结构，如动态r 树、动态r 树等。 3 )根据划分方法的不同，可以分为数据划分方法类、空间划分方法类 以及混合型划分方法类。数据划分方法是根据数据所在的位置进行 层次划分，如r 树等；空间划分方法则是将整个数据空间逐渐划 分为互相邻接的子空间，如k d 树【5 等。混合型是指既根据空间进 行划分又根据数据进行划分，如h y b r i d 树f 1 0 1 等。 4 )根据索引的组织形式，可以分为树型结构类和非树型结构类。树型 结构类指索引结构是按照树的形式组织，如k d 树5 1 、r 树等； 非树型结构类如v a f i l e 【1 1 等。 5 )根据目录节点的形状，可以分为矩形、球形和混合型。在构造索引 结构的时候，目录节点形状的选择直接影响检索的效率，选择为矩 形的有k d 树、r 树、r + 树等；选择为球形的有s s 树1 2 】、t v 树6 】 等；将矩形和球形结合起来使用的成为混合型，如s r 树【1 3 1 等。 4 2 几种代表性的向量空间高维数据索引结构 4 2 1r 树类 r 树类的索引结构类似于b 树，一般都具有层次性的数据结构，最先出现的 r 树索引结构是在1 9 8 4 年由g u t t m a n 提出的r 树【7 】。此后人们对它的算法和 结构进行了一些改进，不过大多都保持了与r 树相同或类似的结构特点。 4 2 1 1r 树 复日大学博+ 毕业论文：支持最近邻查找的高维空间索引张军旗 r 树是一种平衡树，具有类似于b 树的层次结构。在r 树中存放的数据并不 是原始数据，而是这些数据的最小外接矩形( m b r ) ，它具有以下的一些性质： 1 )如果用m 来表示一个节点中可存放的项数目的最大值，用m ( 研m 2 ) 来表示一个节点中可存放的项数目的最小值，则除了 根节点外，每个节点中必须包含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 ) 所有叶子节点出现在统一层上。 图2 1r 树结构示意图 r 树的查找算法类似于b 树，它是从根节点出发，对内部节点，检查其每一 个项是否与要查找的区域相重叠，如果重叠的话，则查找该项所指向的子节点， 直至查找到叶子节点。由于在r 树中存放的是m b r ，这些m b r 可能相互重叠( 如 图2 1 中的a 和b ) ，所以无法保证查找操作只搜索一个路径即可成功，在最坏 的情况下，一个查找操作可能要遍历所有的路径。 向r 树中插入一个数据，实际上是插入该数据的m b r 。和查找操作不同的 是，一次插入操作只需要遍历一个从根节点到叶子节点的路径，首先从根节点开 始，在经过的每一个内部节点中选择这样的项：它所指向的子节点为了包纳下要 插入的数据其m b r 的面积需要扩大的最小，如果出现相同的情况，则选择m b r 最小的一个。当到达叶子节点候，如果该节点中还有剩余的空间，就将数据插入 到节点中，并按原路径返回，一次修改其祖先节点中相应项的m b r ；假如在叶子 节点中已经没有足够的空间存放下要插入的数据，则要发生分裂，生成一个新的 叶子节点，并在其父节点中插入一个指向新叶子节点的项，如果在其父节点同样 出现了溢出，也要产生分裂，如此下去直至根节点，如果根节点也发生了分裂， 囝日 圆r 曰一 复且大学博十毕业论文：支持晟近邻查找的高维空间索引张军旗 则生成一个新的根节点，树的高度增加1 。 要在r 树中删除一个数据，首先要进行一次精确查询操作，如果找到了该数 据，则从节点将其删除，在删除之后如果节点中有足够的项( 即项数目不小于m ) ， 就依次修改其祖先节点中相应项的m b r ，删除结束；如果在删除后节点中项的数 目小于m ，则将该节点所有的项保存到一个临时缓冲区内，并将该节点从树中删 除，如果节点删除后影响到其父节点也出项相同的情况，则也要做相同的操作， 如此直至根节点，然后再将临时缓冲区内所有的项重新插入到树中。如果再删除 完成之后根节点只有一个子节点的话，则这个子节点就成为新的根节点，树的高 度减1 。 4 2 1 2 其他几种r 树类索引结构： 1 )r 树 9 】：r t 树对r 的插入算法和分裂算法进行了一些改进，主要体现在 以下两点：第一，提出了强制重新插入的概念，即当一个节点在插入的过 程中发生了溢出，并不急于进行分裂，而是首先看一下该层节点在这次插 入过程中有没有进行过重新插入，如果没有的话，则选择一定比例的项从 该节点中删除并重新插入到树中，而如果该层已经有节点进行过重新插 入，才对该节点进行分裂；第二，当节点进行分裂的时候，不仅要考虑分 裂后两个新节点的面积，还要考虑分裂后节点周长以及该层节点的重叠面 积等因素。 2 ) x 树 1 4 】：x 树引入了超节点的概念，当节点发身溢出的时候，首先考虑 对节点选择合适的分裂算法，以使节点分裂以后重叠区域小到一定程度， 假如无法避免分裂后出现较严重的区域重叠，则不分裂节点，而是扩大节 点大小以放入更多的项，形成超节点。 3 )s s 树【1 2 1 ：s s 树中采用超球代替了原来的进行数据划分的超矩形，以更 好地支持相似性查询。 4 ) s r 树【1 3 1 ；它是在分析了超矩形和超球两种不同的数据划分方法的优缺点 后，将两者结合起来，形成了s r 树，从而取得更好的性能。 4 2 2 网格文件类 4 2 2 1 网格文件： 网格文件【1 剐是一种典型的基于哈希的存取方式，它是由包含着很多与数据 桶相联系的单元的网格目录来实现的，一般一个数据桶为硬盘上一个磁盘页。每 一个单元只对应着一个数据桶，而一个数据桶往往可以包含着几个相邻的单元。 随着数据的增多，网格目录可能会慢慢变大，所以往往将其保存在硬盘上，但为 了保证在精确查询的时候能仅用两次i o 操作就可找到相应的记录，一般将网 格本身保存在主存中，网格是用d ( 数据的维数) 个一维的数组来表示的，这些 复旦大学博士毕业论文：支持晟近邻查找的高维空问索引张军旗 数组成为刻度。但我们进行精确查询的时候，首先用这些刻度来定位包含要查找 的记录的党员，假如这个单元不在内存中，那么将进行一次i o 操作，将这个 单元从硬盘调入主存，在这个单元中包含着一个指向可能找到记录的页的指针， 取这个指针所指的页又需要一次i o 操作。而对于范围查询，需要检查所有与 要查询的区域相交的单元。 当向网格文件插入一个数据的时候，首先要进行一次精确查询以确定该数据 项应当插入的单元以及对应的数据页( 数据桶所存放的磁盘页) 。如果在这个页 中还有足够的空间的话，将数据插入即可。假如已经没有足够的空问，则要根据 与该页相联系的单元的数目来决定处理的方法，当有几个单元指向该页的时候， 则检查现在的刻度中是否有合适的超平面能够成功的将该页分开，如果有的话， 就产生一个新的页并根据这个超平面将数据分配在两个页中；如现存的超平面没 有合适的，或者只有一个单元指向该页时，将引入一个新的超平面并产生一个新 的页，然后根据这个超平面将数据分配，同时要将这个超平面插入到相应的刻度 中，而所有与此超平面相交的单元也要发生分裂。 在网格文件中删除一个数据，也要先进行一次精确查询确定该数据所在的单 元及对应的数据页，并将其删除。假如在删除之后，这个页中存储的数据低于一 定的数目后，需要做相应的处理，根据当前刻度对空间的分割情况，或者选择同 其相邻的页合并，或者选择将刻度中的一个超平面取消。 4 2 2 2 其它几种网格文件类索引结构： 与网格文件类似的还有e x e l l 、两层网格文件以及“t w i n ”网格文件等： 1 )e x c e l l “1 与网格文件不同之处在于其所有的网格单元是相同大小的， 因此它的每次分裂都将导致目录大小的成倍增长。 2 )两层网格文件u 7 1 的基本思想是再增加一个网格文件，形成两层网格来管 理目录，其中第一层被成为根目录，它是第二层目录的一个大致描述，它 具有指向第二层目录的指针，而第二层才是真正的目录，它包含有指向数 据页的指针。这种结构的好处是，当发生分裂的时候，所产生的影响被被 限制在第二层目录的范围内，从而没有过多影响其他数据。 3 )u t w i n ”网格文件u 8 1 也是引入了另外一个网格文件，不过与两层网格文 件不同的是，这两个文件的关系是对等的，而且每个文件都覆盖了整个空 间，数据在这两个文件中的分布是动态的，当在插入过程中某个文件的单 元所指向的页出现溢出的时候，将在这两个网格文件之间重新分配数据。 4 2 3k d 树类 4 2 3 1k d 树 k d 树是一种在k 维空间中的二叉查找树，它主要存储的是点数据，在每一 1 4 复日大学博士毕业论文：支持最近邻查找的高维审问索引张军旗 个内部节点中，它用一个k 一1 维的超平面将节点所表示的k 维空间分成两个部 分，这些超平面在k 个可能的方向上交替出现，而且在每一个超平面中至少包括 一个点数据，下图2 2 为一个k d 树例子： | | g 图2 2k d 树结构示意图 在k d 树的查找和插入操作是很简单的，而删除操作则有点复杂，因为一个 点的删除可能会导致它的子树的重建。由于k d 树只能处理点数据，我们对其他 具有一定形状的数据只好用它们的中心点来代替。需要指出的是，当数据插入的 顺序不同的时候，k d 树的结构也不同，而且数据会分散出现在树的