您好、欢迎来到现金彩票网!
当前位置:彩63彩票app下载 > 高维索引 >

高维索引技术及其在医学图像数据库中的应用pdf

发布时间:2019-04-23 21:54 来源:未知 编辑:admin

  1.本站不保证该用户上传的文档完整性,不预览、不比对内容而直接下载产生的反悔问题本站不予受理。

  江苏大学 硕士学位论文 高维索引技术及其在医学图像数据库中的应用 姓名:卢佳 申请学位级别:硕士 专业:计算机应用技术 指导教师:宋余庆 20050605 江苏大学硕士学位论文 摘 要 高维索引技术是研究通过建立索引结构来提高高维数据库上检索效率的~ 门科学。黼像数撵痒作为商维数掇库的重蒙组戒鄢分,其检索离不开高维索弓i技 术的支持,近年来备受研究人员的关注。 本文辩国内辩现有关予高维索弓的技术和方法进行了综述,并飘理论、算法 和应用三方面对离维索引技术进行了研究。在分析和比较现有高维索引结构的基 璐上,摄滋了鑫蠢豹索弓髯法;势班诧为簇穑,浚计积实现了医学图像数据库检 索原型系统。本文的工作主要包括: l。觚离维数据空润焱询处毽窭发,势析了嵩维数攒及其索弓技术的特点, 探讨了高维数据登询的主瓣技术,归纳总结了高维索引的基本思想、结构以及索 弓簿法。 2.从索引思想、结构和适用性能等方面对度量空间索引方法MAM和向量 空闻索雩方法SAM中的多个典鹜索弓结构进行了分析帮阮较,辩纲总绪了二者 的区别和联系,指出了图像数据麾索引技术的研究方向。 3.鬟出了M+祷索弓方法。该方法怒戳度薰索弓l方法——M树索弓i缩构为 基础,采用基于全局的多分支插入算法建娆索引,井结台改进的Slim-down算法 辩建立的索弓结构进行优化。该方法提高了索弓辩节点剩孀率,降低了节点之闻 的霆叠率,其最大特点是邋于高维甚至超离维的数据检索。实验验证了该方法在 意维数摇稔索中的优势。 4.设计并实现了基予M+树索引的医学图像数据库检索系绕。该系统从医 学图像信息的特点氆发,采用极大熵阂值分割方法,提取区域度羹宣方萄作为医 学豳像特征,并威用M+树索引方法对直方图特征库进行了索引和组织。实验系 统特征提敬算法简荦,特征索亏i效果明显,有效蛾提高了检索的住能。 关键谰:离缀索弓,度量空闯,医学图像数攥痒,基于内容梭索 江苏大学硕士喾位论文 ABSTRACT researchersfocuson index Recently,increasing high“dimensionaltechnology, whichisascienceof theretrievaleffectivenessof improving high—dimensional databaseestablishmentofindex all of structure.As by important part high dimensional database’Sretrieval reliesonthe database,image ability suppo髓of index high—dimensionaltechnique. index are and Existinghigh。dimensionaltechniquescomparedanalyzed.By ofrelevant index systematicallyanalyzing algorithms,high-dimensionaltechniques are from and anovel investigatedtheory、algorithmimplementationaspects,and methodofindexis additional,aretrieval ofmedical presented,In prototype system databaseis and basedonthisnovelmethod.Themain image designedimplemented WO痰iSlistedhere: data dataandits l、Bystudyhigh—dimensionalspacesearching,high-dimensional index are relevant of techniqueparticularlyanalyzed。T黩easpectshi蚨一dimensional data arediscussed.Thebasicidea.structureand query algorithmsofhigh—dimensional indexare concluded。 idea、structureand are betweenmetric 2、Indexing applicabilitycompared access access and method(MAM)andspatial method(SAM).Thesimilarity to differenceofthosetwomethodsare eachmethod summarized.Appl妊ngimage database find fieldsof databaseindex retrieval,westudy image technique. of are thebasisofM-tree’S 3、AnewindexmethodM4-tree proposed,On as useofa method,called structure,this M*-tree,makesglobalmulti-wayinserting for indextreeand anamelioratedslim—down dynamicbuilding explors algorithm whichCall itsstructure.M*-treenodes ofindex algorithm optimize improvesutility of two a the between ofnodesandhas structure,decreases quantityoverlaps regions thatitcallbe to or dataretrieval prominentadvantage highhyper-dimensionat applied whichis provedbyexperiment. 4、OnthebasisofM+-treearetrieval ofmedical databaseis system image and tothecharacteristicofmedical designedimplemented.According image USe takes ofthemethodofmaximumthreshold information,氆is system entropy toextract metric asfeaturesand M4-tree segmentationregional histogram applies of methodtoindexand features featureis and organize simply database.Extracting theeffectoffeatureindexisobviousinthis that prototypesystemimproves of retrieval performanceimage effectively. Keywords:high-dimensionalindex,metric imagedatabase,CBIR space,medical Il 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定,同意学位保留并向国家 有关部门或机构送交论文的复印件和电子版,允许论文被查阅和借阅。本人授权江苏大学可 以将本学位论文的全部内容或部分内容编入有关数据库进行检索,可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 保密口,在 年解密后适用本授权书。 本学位论文属丁 不保密日。 、 学位论文作者签名:j}住 舯教师始肛弘 os年s羁6日 年 月 日 本人郑重声明:所呈交的学位论文,是本人在导师的指导下, 独立进行研究工作所取得的成果。除文中已经注明引用的内容以 外,本论文不包含任何其他个人或集体已经发表或撰写过的作品 成果。对本文的研究做出重要贡献的个人和集体,均已在文中以 明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名:专位 日期:oy年占月,日 江苏大学硕士学位论灾 第一章绪论 随着计算机和通信技术的发展,尤其是存储技术的进步和因特网的日益普 及,久稻糖有了魄戳往任俺时代帮无法}l壤豹信感蝥源。这些资源不仅畜简单静 文本数据,更包含了大量的声音、图像、视频等多媒体信息。图像作为~种内容 丰富、表蕊奁蕊静媒体,在诲多镶域都褥掰了广泛懿应潮,如数字图书键、邃理 Information 信息系统(Geographic System,GIS)、医学辅助诊断嚣。由于图像的 数蕹量丈,信惠内涵丰富,毽莼,如籍更好遣对图像数据滋{亍组织、分类箱检索, DataBase 已成为图像数据库系统(Image System,IDBS)需要解决的~个芙键问 鬈。 {。{研究背景与意义 传统的IDBS,一般通过图像的辅助关键字信息或从图像中提取的语义信息 等文本数据来实现图像懿瘫诲。崮予图像包含丈豢的滩诅翅文字躐语言耩述静信 息,所以传统的基予关键字的查询已不能适应图像检索的要求,如何充分地利用 黉像提供绘我们的信惠,实现侠遴有效静图像检索是本文研究豹淘题。驻医学图 像领域为例。仅仅根据胶片号、图像文件名、病人的基本信息进行检索和蹩询已 经不能满怒医学图像检索豹需要,医学图像数据痒系统蔑爰能使鞠结构车{:查询语 言SQL进行查询,还需要提供医学图像内容的查询。近年来,为适应图像查询 的需要发怒起来的基于图像内容的裣索(Content-basedRetrieval,CBIR), Image 可以帮助使用者对图像数据库进行有效的管理、赢询并迅速地获取所需疆的信 惑。 基于内容检索系统的基本思想是通过分析图像的视觉特征和上下文联系来 避行检索。它的实现方法怒使用萄像数据痒存储和管理圈像数据(包括原稻像和 图像特征),然后将基于内容检索技术作为数据麾的引擎嵌入图像数据库中,提 供基于内容的图像检索功能。在现有的基于内容的图像检索系统巾普遍采用最低 层次的图像信息(如图像的颜色、纹理、形状特征等,以及这些特征的缀含)来 实现图像内容检索【11l翻。它的突出特点是:(1)用于检索的是反浃图像内容并与 图像存储强一起的各种量化特征。(2)使用基于相似性度霪的近似检索。(3)大 多采用示例检索(QueryBy 键调注释方法的主观性,取而代之以图像本身的视滋信息避行索弓l,更符合图像 数据库相似性检索的要求。CBIR关键技术的研究主要包括:特缎提取、綮gi技 江苏大学硕士学位论文 术、相似性查询处理等方面。其中特征提取是CBIR技术的基础,也是很多专家 研究的热尉3】【4】【5】。 目前,关于图像索引技术的研究相对较少。图像索引方法在某种程度上决定 了图像检索系统的性能优劣。因为在应用中,图像数据库耗时较大的操作有两方 面:特征提取和相似度的计算。而特征的提取只有在图像入库时才计算,图像的 相似性度量则是每一次进行QBE查询时都需要计算的。在海量的图像数据库中 进行相似度的查询操作是一项十分艰巨的任务,描述对象的内容特征通常都是高 维的矢量,在多特征联合检索中,特征矢量甚至可能达到一百维以上。传统的图 Scan 像查询采用顺序扫描(Sequential 算其与被查询图像之间的相似性度量距离,并返回满足特定查询要求的所有图像 对象;该方法距离计算的花费很大,搜索效率较低。据统计,一个1000张床位 的综合性医院,一天的图像数据量大约为6G,一年约为2.2T,长期在线T的存储空间,对如此庞大和复杂的数据量进行顺序的查找 操作,查询的实时性和准确性都是难以得到保证的。相应的,传统的一维索引方 式已经远远无法满足要求,需要建立合适的索引方法对特征空间进行索引,使得 在检索时,不必比较数据库中的每一幅图像,而是通过索引技术进行少量的比较 计算后,快速排除明显不符合条件的图像对象,从而有效地找到所需要的查询结 果。 图像索引技术是为了提高大规模图像库中检索图像时系统的运行速度。尽管 目前大部分系统尚未采用这项技术,但它却是高性能图像检索系统必不可少的组 成部分。图像索引技术目前还很不成熟.但具有广阔的研究前景。随着CBIR技 术的研究与发展,用户可以通过互联网对感兴趣的图像进行查找、对卫星地球资 源照片的查找和分析、医学图像的存储和检索等。利用图像数据库索引技术,可 以尽可能的提高检索的速度和精度,从而更好地满足用户的实时性检索要求。尤 其是医学图像的存储和检索,能够有效地辅助医生诊断,降低误诊率;同时,对 医学图像数据库系统的功能完善和质量提高有重要的实用价值。 本文以图像数据索引技术研究为出发点,主要研究如何建立高效的索引结 构,从而提高医学图像数据库中基于内容的图像检索效率。 1.2国内外研究现状 为了能够高效的进行数据(特征)索引,实现图像、视频等多媒体信息的快 速检索,研究者们对索引技术进行了许多研究,其主要内容集中在适当的降低索 江苏大学硕士学位论文 引维数和建立良好的索引方法上。降维的基本思想是对数据对象进行维数压缩, 使得从原先高维的数据变换到相对低维的数据。常用的降维方法有K.L变换、 FFT变换以及聚类f6】【7】【8】等。但是,盲目进行维数的压缩是危险的,一方面降维 势必损失图像信息,而这些信息对于检索又是未知的,所以结果很难令人满意: 另一方面由于图像本身维数非常高,即使降维仍很难满足检索要求。因此,围绕 着如何建立良好的索引方法,研究者们做了许多的工作。 1.2.1高维索引技术 高维索引的研究始于七十年代中期,涉及计算几何、数据库管理和模式识别 等技术。早期的研究成果包括多维哈希表,网格空间等,但这些技术在高维数据 应用上的效果表现不佳。随着GIS和CAD系统对高维索引要求的不断提高,研 Access 究者们又陆续提出以R.Tree【9I为代表的各种高维空间索引(Spatial 提出的,最初是为了支持地理信息系统中范围或地点的查询,数据库中对象的相 似性度量是定义在欧式距离上。常见的SAM方法有R+树【1”,R+树‘12I,SS树㈣, sR树【141,X树【151等。 Access 高维索引的另一种方法是度量索l(MetricMethod,MAM)方法。一 般而言,MAM索引是广义的SAM索引。它不考虑查询对象在高维空间上的绝 对位置,而是以对象之间的相对距离来组织和区分搜索的空间。相对而言,度量 空间上的索引结构具有更为普遍的使用范围。常见的MAM方法有BK[16]树,VP 树【17】,MVP树【18】,M树【19】等。 这些树结构各具特色,很难评定哪一种更优。即使在某一特定方面,也没有 哪一种结构明显优于其它所有的索引结构。关于高维索引的研究还处于初步阶 段,技术还很不成熟,既没有公认的索引标准,也没有规范化的查询语言,而且 还没有建立起对各种结构的性能进行评估的有效方法。尽管如此,随着检索技术 的发展,有理由相信高维索引技术具有广阔的理论和应用前景。 1.2.2高维索引应用 进入90年代以来,基于内容图像检索技术己成为一个比较活跃的研究领域, 既有理论研究成果,也出现了很多原型和商用的图像检索系统。为了提高检索速 度,少数系统应用了高维索引技术,以下介绍几个典型的系统。 1.IBM公司的QBIC(QueryByImageContent)系统是第一个商品化的基于内 容的图像检索系统120】。QBIC系统也是第一个应用了索引技术进行查询的商用系 江苏大学硕士学位论文 统。其索引策略是先采用降低维数的方法——K—L(卡洛)变换对特征空间进行 维数压缩.然后使用R+一tree对高维特征进行索引。它主要集中非语义内容的图 像和视频检索,并采用多种图像特征来检索图像,诸如颜色直方图、纹理及目标 形状等。 2.Virage是美国加州大学圣迭戈分校设计的一个基于内容的搜索引擎[211。 针对大容量图像库需要解决的快速索引问题,Virage先后提出了SS树和 于颜色、颜色布局、纹理和结构的可视查询,但是Virage与QBIC相比,前者支 持上述4种原子查询的任何组合查询。 系统是面向多媒体制作图象素材库的,采用GSS.树作为系统的相似性查询的索 引结构。提取的图像特征包括主颜色、纹理、颜色直方图等通用特征来对图像的 内容进行描述。 上述系统初步实现了图像数据库的相似性查询,通过高维索引技术的应用在 某种程度上提高了检索的效率,但仍存在很多问题,如索引结构不理想,随着数 据维数的升高,高维索引结构的性能迅速下降;特征的提取和相似性度量缺乏具 体应用领域特点,因而建立的索引检索效果不明显等。 1.3研究内容与特色之处 高维索引技术是提高图像数据库检索效率的一个关键因素。本文通过借鉴国 内外学者己取得的研究成果和成功经验,吸收了众人先进的研究思想、技术和方 法,结合参研项目“医学图像数据库存储技术研究”(镇江市社会发展基金资助 项目sH2003014)和“高维索引与医学图像数据库”(江苏大学学生科研基金资 助项目),从理论、算法和应用三个方面对高维索引技术进行了研究。 纵观全文,本文的主要特色包括以下几个方面: 1.探讨了高维数据及其索引的特点,归纳总结了高维索引的基本结构、索 引算法、查询方式,并对两类典型的索引方法MAM和SAM从结构、算法、适 用情况和实际性能等方面做了深入的分析和比较,指出适合图像数据库检索要求 的索引结构。 2.提出了基于M+树的索引方法。该方法是在分析和研究MAM方法的典 型索引技术M树建树算法的基础上,提出了多分支插入动态建树算法与改进 Slim—down算法结合的的M+树索引方法。该方法优化了插入算法,降低了节点 4 江苏大学硕士学位论文 统a其索引策略是先采用降低维数的方法——K-L(卡洛)变换对特征空间进行 维数压缩,然后使用R+-tree对高维特征进行索引。它主要集中非语义内容的图 像和视频检索,并采用多种图像特征来检索图像,诸如颜色直方图、纹理及目标 形状等。 2.Virage是美国加州大学圣迭戈分校设计的一个基于内容的搜索引擎Ⅲl。 针对大容量图像库需要解决的快速索引问题,Virage先后提出了ss树和 于颜色、颜色布局、纹理和结构的可视查询,但是Virage与QBIC相比,前者支 持上述4种原子查询的任何组合查询。 系统是面向多媒体制作图象素材库的,采用GSS.树作为系统的相似性查询的索 引结构。提取的图像特征包括主颜色、纹理、颜色直方图等通用特征来对图像的 内容进行描述。 上述系统初步实现了图像数据库的相似性查询,通过高维索引技术的应用在 某种程度上提高了检索的效率,但仍存在很多问蹶,如索引结构不理想,随着数 据维数的升高,高维索引结构的性能迅速下降:特征的提取和相似性度量缺乏具 体应用领域特点,因而建立的索引检索效果不明显等。 1 3研究内容与特色之处 高维索引技术是提高图像数据库检索效率的一个关键因素。本文通过借鉴国 内外学者已取得的研究成果和成功经验,吸收了众人先进的研究思想、技术和方 法,结合参研项目“医学图像数据库存储技术研究”(镇江市社会发展基金资助 项目SH2003014)和“高维索引与医学图像数据库”(扛苏大学学生科研基金资 助项目),从理论、算法和应用三个方面对高维索引技术进行了研究。 纵观全文,本文的主要特色包括以下几个方面: 1.探讨了高维数据及其索引的特点,归纳总结了高维索引的基本结构、索 引算法、查询方式,并对两类典型的索引方法MA/Vl和SAM从结构、算法、适 用情况和实际性能等方面做了深入的分析和比较,指出适合图像数据库检索要求 的索引结构。 2.提出了基于M+树的索引方法。该方法是在分析和研究MAM方法的典 型索引技术M树建树算法的基础上,提出了多分支插入动态建树算法与改进 Slim—down算法结合的的M’树索引方法。该方法优化了插入算法,降低了节点 Slim—down算法结合的的M’树索引方法。该方法优化了插入算法,降低了节点 江苏大学硕士学位论文 重叠率,其最大特点是适于高维甚至超高维的空间数据检索。实验验证了该方法 在高维数据检索中的优势。 3.设计和实现了医学图像数据库基于内容图像检索系统。针对医学图像信 息的特点,设计了基于区域度量直方图特征,并采用M·树对特征进行索引的检 索方案,实现了原型系统;实验结果表明该系统在检索效果和速度方面取得了一 定成果。 1.4论文章节安排 论文的具体安排如下: 第一章“绪论”。介绍本课题的背景,研究意义和国内外相关领域的研究现 状,给出了课题的主要研究内容和章节安排。 第二章“高维数据及其索引”。从高维数据概念出发,分析了高维数据索引 的特点,基本思想以及结构;讨论了高维数据空间查询的相关问题,包括数据空 间、距离度量函数以及相似性查询方式等。最后总结归纳了高维索引的基本算法、 建树算法以及典型的查询方式。 第三章“高维索引方法研究”。对现有的多种高维索引结构进行不同的分类, 并且根据数据特征的表现形式,重点研究和分析了SAM和MAM方法中的多个 典型索引结构;最后对这两类索引从支持图像数据库检索应用方面进行了分析和 比较。 第四章“M+树索引方法”。在对传统MAM索引方法研究的基础上,对其代 表结构M树的建树算法进行了研究改进,提出了基于多分支插入和后处理的优 化算法的M+树索引结构,并且引入了衡量节点重叠率的评价标准来对MAM索 引树进行评估。 第五章“M+树索引在医学图像数据库中的应用”。在对医学图像特点的研究 基础上,根据医学图像数据库系统检索的要求,提取了基于区域的度量直方图的 医学图像特征,通过数学推导验证了度量直方图距离函数满足度量性质,从而应 用M+树索引设计和实现了医学图像数据库系统的检索。 第六章“总结与展望”。对论文内容进行了总结,根据自己研究的成果和体 会,提出了未来进一步研究的方向。 江苏大学硕士学位论文 第二章高维数据及其索引 2.1 引言 自上个世纪六十年代数据库管理系统(Database ManagementSystem, DBMS)诞生以来,实现了对文本及数字等数据的有效组织和管理,保证了数据 在数据库中的完整性,并且能够方便快速的对数据进行查找和检索等操作,数据 库索引技术也随之发展起来。索引的目的是希望无需遍历整个数据库,仅通过有 限次的比较而快速获得查询所请求的数据12”。 在早期的关系数据库管理系统中,为了提高数据检索操作的效率,主要是利 用库中存储的数据在其应用领域内的“有序性”来组织数据和建立索引。所谓“有 序性”,通常是对一维数据而言。最常用的一维数据的组织方法是B树和它的继 承者B+树。用B树对传统的数据库中存储的数据类型(数字或者短字符)进行 索引,利用的是数据的“有序性”。比如,就数值而言,9339,而对字符串而 言,“house”的字典序在“hunter”之前。这些简单的数据类型,可以在其各个 数据元素之间通过某种比较关系排成一定的顺序。B树就是利用这种“有序性”, 在查找过程中,通过比较,对不符合条件的数据元素进行剪枝(Prune)。 图2.1是B树索引的一个示例图。 臣:耋!燮童鎏鎏__塑窆塑鎏篓堕墼!燮鲎鲨_ 图2.1 B树索引示图 然而,一旦数据库中存储的数据不再是简单的文本数据,而是一些复杂的数 据对象,如图像,视频等所谓的非结构化数据,就不能够再使用传统方法来对其 进行简单的排序从而建立索引。比如,对于给定的两幅图像A和B的比较,就 不能用所谓的“AB’E或者“AB”来进行描述。 6 江苏大学硕士学镶论文 2.2高维数据及其索引技术 随着计算机成用的不断深入,计算机处理的数据不再局限于简单的文本或数 值,更逐步深入了各应用领域的复杂对象。如何在计算枧中描述帮组织这些复杂 的对象,成为数据库领域研究的蘸要问题。 2+2。{麓维数据 自然界中存在大量的复杂事物或现象,如天气状况,照白质熬因序列以及图 豫、音频筹多媒体僚怠等等。瑟麓这些大爨酌信怠,缀臻在计算枫瞧赛璧角篱擎 的文本或数值信息来表达这些复杂对象的全部信息。以图像信息为倒,其在计算 撬串豹表涿昃是一个二缭豹点薄,一个髑熬数毽表示静数字图像螽像素的灰度使 的榘合,对其表示的图像对象来说并没有明确的意义,也远远低于图像所袭示的 港义层次上麓意义。 为了实现从不同角度描述这热复杂对象,需要以各个方面的特征及特征间的 关系来共阉搐述数据怼象。对予强像数攒,可鞋筑颜色、绞瑾、形获等多方嚣对 其进行描述,这样对于每幅图像。可以由多变量组成的矢凝数据来表示。这些用 多个变量孪蠹象描述复杂瑟象魏数撵,称为搿维数撵。 高维数据具有众多的数据变鬣,它们分别反映了同一对象的各个方丽的特 援。设一个数据瓣象静n个特征德分到为而,x2~.,x。,由予它{『j采鑫同~ 个对象,所以应将它们作为整体一起考虑,为此,由它们构成一个n维特征矢量 x,X=(_,x:,...%)t,Ⅳ是原对象的一种数擘抽象,用蔟来代表原对象,也是 麓维数据鸵模式l嬲。高维数据提供了有关客观现教极其丰富、详缨的信感。. 与传统简单数据不同,高维自句数据信息具有以下一些特点: 1)窟维数据的检索一般是相似性检索,面不是传统的精确题配查询。 2)高维数据觅法进行排序。假设有离维数据的某特征的值为善,Y,z,若 考xY。,著誉代表对象馥与对象o,之闻的橱戗度要魄对象婊与对象O:之 间的相似度高。 3)裹维数攥戆属缝撰述虿戆是具有攘互联系戆多黧属性,装拉,b分刘代 表两类特征,则尝询的结祭result(a,b)≠result(a)r、result(b)。 2.2.2嵩缝数器索号技术 随着离维数据的不断增长,建维数据库的应用锝到了快速的发展,如图像数 据库,生物信息学中的DNA数据库等。与传统的数据库相比较,高维数据库对 了 江苏大学硕士学位论文 所包含对象的描述更加复杂,需要建立合适的索引技术来对其进行组织和管理。 高维数据本身的高维性和数据关系之间的复杂性决定了高维数据索引的实 现难度。对于简单数据,B树和可扩展哈希表等索引结构都有很好的性能,而且 实现起来也比较简单方便。因此,在高维数据索引的处理上,人们很自然想到把 高维向量中的数据分割使用一维索引方法来进行处理。实验表明使用这种方法的 检索效果很较差【251。另一种思路是将高维的空间数据映射到一维数据【261,使得 在高维中相近的数据,在映射后仍能保持相对应的距离关系,从而把问题转化成 一维数据的处理。但是这种映射关系很难寻找,而且即使找到了,也会损失一些 高维数据的信息量。因此,解决高维数据问题需要新建专门的索引技术来适应新 的应用。与传统数据库的一维索引结构不同,高维数据的索引结构需要满足以下 几个条件: 1)动态性。高维数据库的处理常常包括一些诸如插入和删除等操作,这就 要求存取方法在设计和维护时必须考虑动态的特点,便于在数据库的更新时,可 以动态调整索引结构。 2)协调性。虽然存储技术的发展很快,但是不可能完全在主存中进行数据 库的检索。索引文件可能会很大,因此在设计时应考虑如何合理安排主从存储之 间的任务分配来提高索引的效率。 3)高维性。复杂对象的内容描述一般都是高维的特征矢量,因此索引结构 必须要支持高维的数据。 4)简单健壮性。复杂的索引结构可能在某方面的性能会比较突出,但是也 需付出较大的代价,比如计算量大,容易出错等等。在大型的数据库系统里,我 们希望能够建立结构相对简单,健壮性较强的索引结构。 5)高效性。索引的作用在于去除一些明显不符合要求的候选对象,所以索 引的范围应尽量的小,提高存储的利用率。 6)集成性。索引结构嵌入大型数据库系统时,对整个系统的影响应该尽量 的小。 高维索引技术是为了提高大规模高维数据库检索时的系统运行速度。尽管目 前大部分高维数据库系统尚未采用这项技术,然而高维索引是未来高性能高维数 据库系统系统的重要组成部分。 2.3高维数据查询处理相关 在高维索引技术的研究中,高维数据空间,相似性度量函数、查询类型和性 江苏大学硕士学位论史 能评价标凇都是需要探讨的基本问题,这熙拟从数学的角度来对这些问题作一些 探讨。 2.3.1离维数据空间 在裔维查询处理中,被查询对象往往是通过某种特征变换的矢量数据表现的 藏维数据。当矢量数据具有固定的有限维数时,这些数摄的集合就形成了d维魄 数据空间,称为空间或向爨空间数据库。在空间数据库中,查询辩象其有囿定的 维数,并鼹可以通过每一维的数攒进行坐标定位。 若查询对象不是固定有限维的特征炙爨时,可以把查询对象糟作是嵌入于度 it_(Metric)空间的离维数据,意按用捃曩之闻的距离度爨进行焱询[271。 2.3.2相似性度缀函数 嵩维数据津孛两个辩藩翡耱议程度,主要是邋过对象翦距离来簿量。因诧, 在高维查询处理中,相似性度量鼹非常重要的一个问题。 透鬻掰冕静簇离度量黼数是Minkowsky距离; 1 d d(X,r)=tZh一只r】-(1≤A。。) (2.1) #《i (2.2) 当A—l时,式2.1为Manhattan距离,d(X,y)=∑Ix,一弘} d*l , ,王 (2。3) 当毒一2时,式2。l为Ewli&躲距襄,矗《z,y=l主‰一y,t2}2 L“ J (2.4) 显然,基于Manhattan距离的查询程几何意义上对成的是麓立方体,基予 距离,其豢询则对应了超球体。 几露意义上,该躐察对应子任意旋转的攒球,更适于摆戗性查谗。 根据艨用的不同,距离度量可以分为很多种。在此本文讨论的是通常数学意 义上的距瓷度量灏数。出予从不阉应萎l镁域弗对象实体巾提取鲍特薤暴骞壤域 性,因此,需要将相似性度量与特定领域的对象特征描述综合起来考虑,才能够 保涯相{滋瞧距离度爨鲍鸯效性。对予图像瓣藏色,纹理等霉誓援,扶入眼翦辨认爨 度来说有其特定的相似性距离度墩。需要区别对待。 9 江苏大学硕士学位论文 23.3查询方式 高维数据的查询通常是相似性查询(SimilaritySearching)。与传统数据库的 精确匹配(Exact Match)不同。传统的精确查询是找到数据库中与被查询对象精 确匹配的记录,而相似性查询是找到高维数据库中与被查询对象某些特定方面相 似的对象的集合。 相似性查询包括下列几种常见的方式: 1.点查询(PointQuery) 点查询是最简单的查询类型。对于数据库DB,查询点Q,其查询表达式为: PointQuery(DB,Q)={P∈DBP=Q} (2.5) 点查询类似与传统的精确查询;但在相似性检索里,常常只需判断查询数据 库中是否包含相似点,而不具体确定相似点的位置。 Query) 2.范围查询(Range 范围查询是为了获得与被查询对象在某一特定区域内的所有相似对象的集 合。对于查询目标Q,查询范围r,度量M,距离占和数据库DB,其范围查询 表达式为: EDB (2.6) RangeQuery(DB,Q,,,M)=(PI瓯(尸,a)≤r) 显然,点查询也可看作是范围查询在r=0和度量M为任意时的一种特例。 如果M是欧氏度量,则范围查询在数据库所有被查询点的数据空间在几何意义 对应一个超球。类似地,M取Manhattan距离,则对应了一个超立方体。 3.最近邻查询(Nearest NeighborQuery) 最近邻查询按照近邻原则进行查询,它的返回结果是数据库中离查询对象最 近的一个数据对象,但当数据库中的几个对象都与查询点距离相同时,就存在两 种不同的处理方法,一是返回所有这些查询结果,二是任选其中一个作为查询结 果。对于查询目标Q,查询范围r,度量M,距离占,其最近邻查询表示式为: NNQuery(DB,Q,肘)={P暑DB (2.7) VP’∈DB:如(P,Q)≤屯(尸。,Q)} 4.k-最近邻查询(k-NearestNeighborQuery) k.最近邻查询就是从数据库中选择离查询对象最近的k个对象。k.最近邻 查询可以说是最近邻查询的特例,它指定了返回数据集的个数。对于一个给定的 查询日标Q和一个给定的查询度量M以及距离占,其k.最近邻查询表达式为: kNNQuery(DB,Q,k,M)= ,1。、 、 7 (晶,一最一l∈DBIP∈DB、{异,.最一1),如(P,Q)≤%(P,Q),0≤ik) 10 江苏大学硕士学位论文 5.近似最近邻和近似k.最近邻查询 与该类查询中,用户也需要指定了一个查询点Q和查询结果的数目女。但与 最近邻查询不同的是,用户感兴趣的并非是离查询对象最近的对象,而是并不比 最近邻点距离远很多的那些对象集合。近似最近邻和近似_j}一最近邻查询的近似 程度可以通过计算感兴趣的集合的最近距离和最近邻距离之比来确定。 6.等级查询 等级查询中用户不指定查询结果的数目,而是把查询结果按近似的级别排 序。显然,最近似的一级,即第一级的查询结果就是最近邻查询结果,所以也可 以看作是最近邻的一种扩展。在得到第一级查询结果后,用户才可以进行可能的 第二,第三等不同级的查询。等级查询的优点在于它可以使用户在检查完前面的 结果之后,才决定是否需要进一步查询。 相似性查询的方式有很多种,大多数的查询方式的基本思想与范围查询或k 最近邻查询的思想类似,可以看成是这两种基本查询的扩展和延伸。在本文的研 究中本文采用了范围查询和k最近邻查询的方式。 2.3.4性能评价标准 影响高维索引结构性能的因素是多方面的,如何衡量高维索引的性能,至今 还没有一整套行之有效的评估方法。常见的衡量标准包括以下几个方面: 1.距离计算次数 距离计算次数(ComputationCosts,CC)是指查询时相似性距离地计算次 数。高维索引服务的对象通常都是复杂高维的大对象,相似性比较的度量函数也 相应都是复杂的函数,它执行的计算量是很巨大的,因此CPU的消耗也是相当 大的。 2.磁盘访问次数 磁盘访问次数(DiskAccessCosts,DAc)是指查询时到二级存储中读取磁 盘地次数。由于高维数据库容量十分庞大,相应的其索引结构是无法完全加载进 内存中的;因此高维数据索引是基于二级存储;然而,在磁盘上读写一个块的时 间里,计算机需要执行100万条指令忙91。因此,读写磁盘块的时间决定了查询操 作所需要的总时间。所以在进行相似性查询的处理过程中,磁盘的读写操作代价 也成为了衡量索引性能优劣的一个重要方面。 3.节点利用率(Node Utility) 节点利用率是指实际索引的对象占总的节点容纳量的比饲。高维索引方法主 要是基于从属存储器的,所以节点的利用率是其一个重要的指标;节点利用率高, 江苏大学硕士学位论文 占用存储空间少,索引结构也就相应的紧凑,从而减少磁盘访问次数,提高效率。 2.4高维索引的基本思想与结构 大多数高维索引方法是基于数据空间的层次化划分的。其基本思想是根据高 维数据集在特征空间中的分布特性,将数据切分成子数据集,并对子数据集合进 行描述。检索时通过比较各子数据集的描述,抛弃那些明显不满足条件的子数据 集,而仅对合格者进行检索和计算,从而可以大大的降低搜索时间。 根据上述思想,高维索引的结构一般由两部分组成: 1.数据集描述:用于描述本数据集的各种特性。如数据集的边界包络,包 含数据对象的个数等。 2.子集指针:指向子数据集结点的指针(即目录结点)或指向对象及其描 述的指针(即叶结点) 在形式上,常见的高维索引方法结构上类似于早期的B树。其节点分为数 据节点和目录节点,高维数据存放在数据节点,距离度量上近邻的数据尽可能存 放在同一个节点上。数据节点之间阻层次化目录结构来组织和区分数据空间。最 上层的节点称为根节点,是进行查询和更新处理的进入节点。如图2.2所示。 目 录节 点 、0●●Lr●j 、叶子节点 J 图2.2基本高维索引结构 不同的是,传统的一维索引结构数据划分是基于一种精确的无重叠的划分。 而高维索引的数据划分则是一种模糊的划分方式,数据集合之间会有重叠的部 分,从而导致检索时可能要多条路径进行查询比较。 2.5高维索引基本算法分析 高维索引有很多种方法。一般而言,各种方法都是通过采用不同的特征空间 距离定义、数据划分方法,从而得到不同类型的索引结构。通过对各种索引方法 的分析比较,发现它们的基本思想和算法却是类似的。 插入,删除,更新以及查询操作是高维索引的主要操作,也是实用的高维数 12 江苏大学硕士学校论文 据索引系统的必须礞求。一般而畜,插入、删除和更新与鼠体的索引结构是密切 稳关蕊,德是憨豹来淹逐建凑一定熬茭邋之娃。 2.5.1攒入算法 基本步骤: l。从擐节点嬲发,逐步往下态找,找到能够容纳瑟数据的时子节点,将毅 数据插入该叶子节点: 2,如果该叶予节点溢出,则依据一定的规则将该时予节点避行分裂,分裂 成两个新的叶子节点; 3。叶子节点的父节点应以搬据下层的分裂变化作檩应地修改。如鬃上层父 节点的容擞也超出了目录节点的最大容纳节点数,则目录节点亦拔一定的规则分 裂{ 4.顺着父节点一路键上,如果根节点溢出的话,则产生~个新的根节点作 为剐分裂根节点的父节点,同时,撼的高度增l。 由于插入规则是索引结构建藏的依据,因此插入是索引结构最重要的操作之 一,由于各个节点之间存在重叠秘目录区域对数攒空闻覆藏的不完整性郝使得选 择插入节点成为难点,同时分裂算法的选择与实现也是建立索引结构的重要部 分。 2.5.2删除算法 基本步骤: 1.从根节点出发,逐步往下查找,蠢询到要删除的数据所在的叶子节点; 2.溯除该数糖; 3.若删除该数据元豢后,叶予节点包含数据的数目小于限定值的话,则将 魏节点孛瀚所有数据移密,瓣j除此节点,然后把移窭静数据再插入翳其它时子节 点; 4,著造成攒入的咔予节煮溢出,翔分裂该节点:算法与上述箍入算法类议。 对于大多数的索引结构,删除操作是一件很豳难的任务,因为它常常带来大 筑模的索弓{结构羹组。潮豫会带_聚的合并和平衡闯题,一般的索弓结构的解决方 法鼹么是对其进行重新插入,要么根本就不提供删除的算法。 更新舞法在其体豹瘟孀中,可瑷看作麓一系捌豹删除阻及插入操作豹综合过 獠,在此不再赘述。 江苏大学硕士学位论文 2.5.3查询算法 以范围查找为例,算法步骤如下: 1.从根节点出发,查找与其距离最近的目录节点; 2.从目录节点往下逐步查找,直到查询到离被查询对象最近的叶子节点; 3.若被查询对象处于相邻目录节点的重叠区域,分别查找重叠的支路,直 到最后的叶子节点: 4.计算被查询对象与追踪的叶子节点中的数据元素的距离度量,找出距离 小于某特定值那些对象集合。 如果索引文件大到无法一次调入内存,那么查询过程先把根结点调入内存, 然后从找个根节点开始查询。由于大多数高维索引结构允许节点间的重叠,所以 可能在几个不同的分支都需进行搜索才能完成查询操作。 2.6本章小结 本章从索引的基本思想入手,分析了传统索引方法和高维索引方法的区别, 总结了高维索引方法的特点;并对高维索引的相关问题进行了探讨,包括高维数 据空间、相似性度量函数以及相似性查询方式等;最后总结分析了高维索引的基 本结构以及索引的插入、删除和查询等基本算法。 14 江苏大学硕士学位论文 第三章高维索引技术 离维数据索弓l技术是计算极技术懿缝成部分,经过遮卡多年豹发震,取零了 许多成果。其应月j已经从最初的地理信息系统和机械CAD,扩展到机器人技术、 环境鼓学、萋像检索羁医疗图像等诲多鬏域。虽然基藏鸯镊多这方嚣懿磷究,也 摅出了很多种索引方法,与其先前方法相比,每种方法都有其较好的一面,但是 还没考一摹孛具有胡显爨势瓣索号l方法,驮露艰测了毫维索弓l熬安际应鼹。 3.1 高维索引方法分类 根据离维数攒索引结构的各种特点,可以有不同的分类,以下列举几种常见 筋分类方式。 1.根据索引创建时数据的组织形式,可以分为静态结构类和动态结构类。 静态结搀类是指建楗霹数据库全秘或大部分数攥郏已翘,毅梵采怒孰处理豹方式 将金部数据构建索引,不能支持或者不能有效地支持动态的插入和删除,如GHt30 楗,VP楗}171等;褥动态续梅类是攘垮数撵菝次援入瑟生成豹索霉l结构,翔R耱 191及其变种R+树112l等等。 2。嘏据索gl豹缝缓形式,霹l冀分必楗形结梭类窝{≥瓣形缝秘类。樾形绩穆 类是指索gf结构按树的形式组织数据,如x树【”1;非树形结构魁指索引结构不 是按照爨豹形式缌织豹,蠡瑟FQAt3¨、AESA瑟。1等。 3.根据目录结构的形状,也就是所谓的边界包络形状,可以分为矩形、球 形秘漫台麓。在捻造索弓绥构薅,强录缝点形状黪选择煮簇影璃稔索嚣效率。矩 形包络对区域或包含的关系描述简单便撬,而球形包络的距离概念比较强,如通 鬻靛R嚣、弘D糖馨21等等,它稍箨采霉戆形佟为覆盖速城麴描述。SStl3漉剩是 采用球形靓络:耐将矩形和球形结合起来的称为混合型,如SRll41树就是混合型 豹。 Access 4.根据对象特征的表示形式,可以分为向擞空间索引结构(Spatial 间将高维数据对象映射成离维空间中的点,两对象之间的麓异以备维的坐标值和 距离来囊爨,这逡楚商缨数据瘴孛矮豢弱豹稳嵇髂模鍪;疫量空漓粼不考虑有关 计算距离的知识和对象特,镬表示的知识,只根据数据对象的距离殿量来划分数据 空溷,霞鬻瞧称爨离空阉。SAM秘MAM静龚璧代表分溺是R褥翻蠢M掰狰l。 江苏大学硕士学位论文 以上几种分类方式,前三种是根据索引结构本身的结构特点来划分,第四种 则是从数据对象的特点来划分的。从图像数据库系统应用的角度出发,本文采用 第四种分类方式,对~些有代表性的索引结构进行介绍和比较分析。 3.2向量空间索引方法 SAM空间数据索引结构,也称向量空间(Vector Space)索引,是在空间数据 库系统的研究中提出的,最初是为了支持地理信息系统中范围或地点的查询,数 据库中对象的相似性度量是定义在欧式距离上,也是高维数据常见的索引方法。 当对象提取的特征值具有固定的有限n维时,可以将数据对象看成映射到n 维空间中的点数据,用空间数据库的索引方法对其进行索引。SAM方法利用高 维矢量的坐标值对空间进行划分,或者说是将高维数据映射到向量空间上的点数 据结构。假设将矢量的每一维数据看作一个坐标轴,以坐标的数值即某个特征值 来定位数据,从而建立基于维度坐标划分的索引结构来管理空间数据结构。 典型的向量空间索引结构包括K-D树,四叉树,R树,X树,SS树等。 3.2,1 K—D树类 K.D树【32】是-7中k维空间中的二叉查找树,主要存储的是点数据。在每一 个内部节点,用一个k.1维的超平面将节点所表示的k维空间分成两个部分。这 些超平面在k个可能方向上交替出现,而且在每一个超平面中至少要包含一个数 据。如图3.1所示。 A /\。 E/B 图3.1 K_D树索引结构示图 在K—D树的查找和插入操作很简单,而删除操作则比较复杂。某一个点的 删除可能会导致其子树的重建,由于K-D树只能处理点数据。对具有一定形状 的数据对象只好用其中心点来代替。数据插入顺序的不同,也会导致K.D树的 结构的不同;同时数据会分散出现在树的任何地方,而不是仅出现在叶子节点上。 16 江苏大学硕士学位论文 对K—D树索引方法进行结构上改进的有以下两种索引: AdaptiveK-D褥印j:它对K-D耱豹结橡钕了少谗致凌,在分裂懿对穰选舞 台适的超平面使分裂后的两个部分包含相同数量的数据。而且在这些超平面上不 一定≤}要酝含数爨,阂对它懿豹方淘氇不一定严硌麴在这k令可缝静方羯上交替 出现。在遂种结构星,内部节点袭示的是分裂的越平面,所有的数据都出现在叶 子节矗孛,每个时予哭能镪含一定爨瓣数攥,当超逡这个数垂懿嚣亨媛要发黧分裂。 k-D树同B树的特点结合到了一超,首先,它采 K.D.B树[34】:将Adaptive 鼹了Adaptivek.d瓣孛震怒平嚣采燃分苇患孛熬窆瓣懿方浚,不遐怼予一令肉部 节点所表豕的空间,可以用多于一个的超平面来划分,形成几个相邻的予空间, 每个子空澜对应一巾内部帮患,艨有熬数据均存髓在稳旋褥辞子苓点孛。 K.D树类结构类似于B树,当树的目录节点发生分裂时,分裂不仅会向上 蒺,还会怒下层予麓京传攘,最终会雩;莛时节熹蠡擘分裂;这傻褥索等}结梭不能缳 i正最小空间利用率,从而造成了存储空间上的浪赞。 3.2.2瑙叉树类 的,不过不同的是,四叉树不再怒二叉树。在维数为k的窑问中,每一个目录节 点具有2‘个子节点。每个子节点对应羞一令子空阅。例如,对予一个农二维空 间的四叉树,每个目录节点拥有4个子节点。每个子节点对应着一个矩形。这四 个矩形一般用NW,NE,SW以及SE来袭示(NW表示鼷j也方向的那个矩形)。 用这种方法将整个空间逐渐划分到一个斑形中所包含的数据的个数低于一定的 数嚣兔止,显然这样褥到的四叉樾不§§保{芷是乎德挝。农数据魄较密集的地方, 树的深度将高于其它的地方,如图3.2所示。 强3+2疆翼瓣索;l肇辆示霉 江苏大学硕士学位论文 四叉树的查找操作类似于普通的二叉查找树。在每一层要从四个子节点中选 择要继续查找的予树。对于点查询,只需要选择其中的一个合适的就行了,而对 于范围查询可能需要几个。按照这个方法递归执行下去直到查找到了树的叶子节 点为止。 点四又树(Point Quadtree)是四叉树的一个变种,它是由点数据一个接一个 地连续插入而构造出来的。对于每一个点,首先进行一个点查找操作。假如没有 在树中发现该点,就将该点插入到刚才的查找操作终止的叶子节点,而这个节点 所表示的区域以新插入的点为中心分为2‘个子空间。如果想从点四叉树中删除 一个点的话,则会引起相应的子树的重建,需要将所有子树上的数据重新插入, 删除的代价相当大。 3.2.3R树类 树是空间数据索引结构SAM中最典型的一类层次性数据结构,在后来成为许多 后续SAM索引方法的基础。 R树的结构类似于B树,采用平衡树的概念,即从根节点到每个叶子的路径 长度都是相等的。不同的是,它引入了最小包围矩形(Minimum Bounding 目标数据集合的最小矩形。如图3.3所示,以二维情况为例,图中的各个大小的 矩形就是MBR,整个数据空间就是通过这些MBR一层一层组织起来的。更高 维时,MBR就自然成为最小包围超矩形。 每一个R树的节点都对应了一个磁盘页面的大小,从而保证了对于一个节 点的访问都在一个磁盘页面上,避免了频繁的读写磁盘。在R树中,每一个目 录节点存放了指向其子节点的地址,及其子节点中的所有对象的最小边界矩形 MBR。叶子节点形式类似,不过节点存放的是一个真正的数据库实体以及该数 据库对象的最小边界矩形。 图3.3R树索引结构示图 江苏大学硕士学位论文 R树舆有以下几个性质: · 翔果瘸M来表示~令节淼审霹存敬匏顼数磊夔鼓丈蓬,m是一个节点可 存放的最小项数目(2≤m《lM,2I),则除根节点外,所商节点存放的项 数蠢m,必须满慧掰12蔓掰≤M。 ● 根节点至少包含两个项,除非它怒个叶子节点。 ·R耱是一个平衡耱,每一个时予带点蜀嘏蒂点承凝离穗等。 R树的查找算法类似予B树,从根节点出发,沿树的分支进行比较,逐步逼 逡强标对象;餐蹙与B树不弱静建,R树查找豹籍经并不是难~静;戳为在R 树中,为了保证树的平衡,各个节点包含的矩形区域可以相互重擞。从而提高了 节赢利矮率:经簸努一方甏来说,没有疆鞠熬允谗瀵叠将会严重影响查谪靛效率。 当搜索点猩几个MBR的熬叠区域时,则这几个MBR节点的下层路径都要被搜 索翔。警缭数增蓠辩,节赢阊嚣羹叠必然增夫,套诲豹复杂度氇鞠应的增大;在 最坏的情况下,一次查询操作可能蔡遍历所有的路径。 R橱绦久粕撼穗了一种全新豹解决嵩维索雩游蘧秘方法,一缝研究者对它的 结构和算法进行了研究和改正,以期望得到更好的性能,走要有以下几种: R『卜橱㈥:为了解决R褥熬过瘫重叠闷题,TimosSellis等撬掇了R+褥索亏 结构,采用新的分裂方式使节点之间不再存在重懿。具体的做法怒对重叠区域进 芎亍分裂,两个节煮矩形之阙的重叠被重赣潮分为一个薪静麓煮,数据翔暴处于分 裂区域内,则分酉己到原节点与新节点之中;由于节点之间无重叠,查询的效率也 就褶应撬黼了,毽在一定耩度上会造成存储空闻酌浪费帮树商庋的增加。 Insert” R+树【12I:对R树的插入算法和分裂算法进行了改进,提出了“Force (疆嗣重撩静穰念,帮鲡荣一个节点溢国,就删除一定褥分篦的远离中心透域 的数据对象,再按插入规则重新插入这些对象,从而提高了存储利用率和索引的 毪能。有数据表稿,R+褥豹性能甏眈R树提高了10%~75%。 3。2.4X撼 当节点之间的重叠率太大时,高维索引的效率可能还不如顺序查询方法 出了X.tree索引方法【15】。X树结合了层次的R树索引和线性的顺序索引的优点, 弓}入了“SuperNode”(越苓焘)熬壤念。索孳缓褥如下鹜3.4爨添。 当节点发生溢出的时候,首先考虑对节点选择合适的分裂算法,以使节点分 裂滋螽重畿区域尽霹戆懿,j、至l一是程度;镁如无法避受分裂嚣出联豹严耋蕊域重 叠,则不分裂节点,而是扩大节点太小以放入更多的项,形成超节点;当赢询到 19 江苏大学硕士学姣论文 达越节点时。对超节点内的对象采用线性的顺序查询方法。随着维数的增加,由 予程离维辩辩超节杰韵线後访润要优予对薅度重叠的謦遥节点静瑶次纯谤闷,祷 结构需要动态的改变超节意的数量和大小以提高索引效率。 圈3.4X树蒙§l结梅拳强 在实际性能比较中,虽然x树为减少麓叠引入了线性结构,傻是在复杂度 帮夺闯土静汗销都缀大;随着维数豹增大,超节熹太小不戳定,援索速度魄将近 似于顺序搜索。 32.5 SS树类 SS据【13】是采蠲最枣边棼零形(Minimum BoundingSphere,MBS)取代原来 进行数据划分的MBR,以更好的支持相似憔查询。Ss树的数据划分是这样确定 匏:绘定数攥集合,找裂冀中心点(各令缎上数攒浆平均馕),半经取是戳孛心 为球心,将集合中所有数据都包含在内的最小距离。SS树索Sl结构如图3.5所示。 在援入惑Ss辫对予撼躲选择怒鞋霸予秘节点戆中心懿距褒送泛鸯栋壤瓣, 选择距离最近的节点进行插入,而不考虑产生的重爱或增大的面积。数据插入后 对予薅豹中心焘帮半径邦娶终秘应熬援整。鑫手球形龟络懿复杂瞧,当一个节点 分裂为两个节点时,很难找到一种无重叠的分裂方忒。 圈3.58S树索引缩梅承围 江苏失学硕士学位论文 sR树【14】是一种在目泶节点中将矩形犟Ⅱ球形结合在一起的索引结构。可以看 成是建·秘与Ss瓣豹混合形式。在嚣录节悫孛,它将MBR帮MBS豹籀交区域 作为节点区域,结合了二者的优点,达到更好的空间划分。但是由于MBR和 MBS酶结合,SR耱其鸯掰骞索弓l结椽中袋复杂豹节点形羧,苇点占矮空淹大, 利用率不商。 鞋上会缨7冗秘典鳌豹SAM索雩{靛终稳,京翻霹嵩维空滴索弓l都鸯一定豹 特点,彼此之间有拱同之处,同时每一种都有比前一种索引有某方颇的优越之处: 鸯整索零终较已经瘦矮予滠型系统或蠢躅系统,发挥了一定懿终矮。 3.3度鬃空间索引方法 g方法。农过去戆臻究串,久粕对予SAM戆索霉结构骰7大量躬工作,穗琵较 而盲,人们对MAM的索引结构的重视程度要小很多。实际上,SAM索引方法 哥戮看{睾怒带骞黧标僖惑瓣MAM度量空阗;稳凌之下发麓空阉上豹MAM索弓 结构具有更为普遍的使用范围。 定义3一{度麓空阗f19]M=(p,蠢),蕤中转蔻空海孛对象静集合,表示赘形 式是一系列的高缎矢量(在本文的应用中,可以看成是豳像数攒库中的所有图 镣);d是发萤空瓣中距离涵数,窀吴有骧下圈个蕊本瞧袋: Vpj,I-y,l,:∈D ● 露(叱,V,)=0 (国反往) ● d(叱,k)≥0 (非负性) ●d(v,,Vy)=d(vy,叱) (对称性) ●d(v:,b)≤#(‰,y:)÷蠢(矿:,y,) (三是誉等鳇) 与SAM不同,MAM索引不考虑查询物体在高维空间上的绝对位置,而仅 叛物锌之澜豹鞠瓣距离泉组织黎嚣分装索空阉鹣,这样翡空闯瞧称疫爨空闻 (Metric space)。需要指出的是,在度量空间中,各种高维索引结构的查询难要利 弱豹是三麓不等黢(TriangleInequality),辇盂藏多援索范蚕,提褰焱询效率;关予 利用三角不等性进行搜索算法将在下一章详细研究。 MAM戆薹零愚怒是懿惹一个或者死拿静参考辩蒙f蠛称支熹;Pivot),数蠢 集中的其他对象根据与参考点的躐离关系建立索引结构。在查询时,将待查询的 誉豫与参考踅缳滋行相议瞧度量豹磁较,瓣距离藕麓三角不等毪辩数据集避褥所 谓的“剪拨”,即排除明显不符合条件的对象,减少计算爨,以提黼检索的性能。 江苏大学硕士学位论丈 在多年的研究中,人们提出了多种适用在度量空间中的索引结构。 3.3.1BK树类 间树状索引结构,其构造方法是从数据集中任意选取元素P作为索引树的根节 点;对于任意的离散距离i0,将P周围的数据空间以半径r的倍数划分空间; 对每一个与P的距离在r,2r,3r,..,”r的数据对象划分为一个个数据子集;设定阈 值f,当数据集中剩余的数据对象少于t时,停止划分。如此再对数据子集进行 递归的划分下去,最终形成树状的索引结构。图3.6是一棵简单的BK树。它反 应了BK树的特点。 囡 囤圆回回 图3.6简单的队树结构 在进行相似性查找时,BK树的查询算法从根节点出发,找出所有满足不等 点和叶子节点的每一个元素都要与口进行比较,记录下所有满足d(q∥)≤,的数 据对象作为结果返回。在查询中,所有三角不等性保证了所有满足查询条件的点 均被检索到。 在BK树提出之后,人们在该树的基础上又进行了各种改进,但是结构上保 持了相似的特点,以期得到更好的性能,下面列出主要的几种: FQ树(Fixed.Queries 点:第一,数据库中的所有数据都是存放在叶子节点上,在非叶予节点中存放的 可能是数据库中的数据,也可能是其它的关键字:第二,位于同一高度上的所有 中间节点存放的都是同一个关键字,这是FQ-tree最新颖的地方。由于同一层的 中间节点所对应的是同一个关键字,因此在检索时可以减少距离比较的次数,但 是同时也会增加遍历的节点数,树的高度相应的增加。 31】。FHQ—tree在FQ-tree的基础上又做出了改进, FHQ树(Fixed.HeightFQT)I 即强行规定所有的叶子节点都必须在同一高度上。因此在进行查询时,对于同一 层的节点可以统一考虑,而不必再分为叶子节点和中间节点两种情况考虑。其代 江苏大学硕士学位论文 价为某些叶子节点不得不增加高度以满足这一条件。 3.3.2BS樽类 查找树。箕构造方法为:从根节点出发,为每一个节点选择两个中心数据点C。和 岛。依照距离中心点C;鄹龟谁更避鲍骧粼,依次搀剩余元素分别放入节点的友 右予树中;为每一个中心点记录下它的覆菔半

  ·靶向白血病干细胞的抗CD3IL3及其二硫键稳定构型的融合蛋白的构建、表达及活性研究.pdf

  ·新型HDAC抑制剂——苯达莫司汀化合物Nl-101的抗白血病作用及机制研究.pdf

  ·中国人群乳腺癌ER、PR、HER2的表达及临床病理特征分析;三阴性乳腺癌BRCA1基因甲基化与临床病理特征及预后的相关性研究.pdf

  ·新型HSP90抑制剂抗胃癌作用及机制研究高通量筛选eIF4E抑制剂及其抗肿瘤作用研究.pdf

  ·异基因骨髓间充质干细胞移植治疗难治型原发性胆汁性肝硬化的研究.pdf

http://bed-plans.net/gaoweisuoyin/15.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有