基于边界区域分离的高维点数据索引研究

《基于边界区域分离的高维点数据索引研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、中山大学硕士学位论文基于边界区域分离的高维点数据索引研究姓名：唐斌申请学位级别：硕士专业：计算机软件与理论指导教师：李磊20060528山大学硕十论文矩于边界区域分离的高维点数据索9J研究摘要在基于内容的多媒体信息检索中，人们利用特征提取算法从多媒体对象中提取出特征矢量，然后利用特征矢量之间的距离衡量多媒体对象之间的相似度。相似性检索的实现就是通过计算查询矢量与数据库中矢量之问距离以找出满足条件的对象。当数据库中对象很多时，简单的顺序扫描将导致极大查询代价，无法满足用户需求。为了有效实现快速相似查询，就必须借助于多维数据索引

2、结构。为了有效索引多维数据，人们进行了大量研究，提出了众多的索引结构，例如R-Tree，R}一Tree，X-Tree，SR—Tree，SS—Tree等，这些索引结构在低维空间中性能很好，但是，在高维空间中，性能急剧下降，甚至不如顺序查询，这种现象被称为“维数危机”。为了解决“维数危机”，本文提出了～种基于边界区域分离韵高维索弓l结构，实践证明，该索引结构在高维空间中有着良好的性能。关键字：基于内容索引结构高维相似查询维数危机山大学硕+论文堪丁边界区域分离的高维点数撕索引研究AbstractIntheprocessofcont

3、entbasedmultimediainformationquery,weabstractfeaturevectorsfi'ommultimediaobjects．Thefeaturevectorsareusedtorepresentthesimilaritybetweenmultimediaobjects．Weachievesimilarityquerybycomputingthedistancebetweenqueryvectorandvectorsindatabase．W～rhendatabasecontainsala

4、rgenumberoffeaturevectors，simplesequentialscanwillincurextremelyhighquerycostandcannotsatisfyuscrs，sowcmustmakeuseofmulti—dimensionindexstructuretoachievefastquery．Peoplehavedonealotofresearchtoindexmulti-dimensiondataeffectivelyandhaveproposedmanyindexstructuressu

5、chaSR-Tree，R+一Tree，X-Tree，SR-TreeandSS-Tree．Theseindexstructures’performancedecreasesharplywiththedimensionincrease，althoughtheyworkwellinlowdimensionspace．Thisphenomenaiscalled‘Ⅵlecurseofdimensionality'’．Tosolvethisproblem,webringforwardaindexstructurebasedonbound

6、aryseparate．Practiceshowthatthisindexstructureworkswellinhighdimensionspace．Keywords：contentbased，indexstructure,highdimension,similarityquery,thecnrseofdimensionality3·l，山大学硕十论文基于边界区域分离的高维点数据索引研究第1章前言多媒体信息检索的传统方法是基于文本的。使用关键字注释是最常用的方法，使用这种方法，对多媒体信息的检索转变为对关键字的查询。这种方

7、法可以利用传统的DBMS实现，简单易行，而且能够从用户角度表达对多媒体内容的理解。但对于目前容量以GB或TB来计算的多媒体信息来说，要求对每～条记录进行注释是不可行的，同时，多媒体内容对于注释者的依赖性也局限了这种方法的正确性。除了关键字，多媒体文件的文件类型、大小、日期等附加信息也可以作为检索的辅助手段，但它们都不能反映多媒体的内容。为了克服以上方法的局限性，90年代初出现了基于内容的信息检索系统(CBIR—Content-basedInformationRetrieval)。CBIR系统除了利用以上方法之外，主要是从多媒

8、体中抽取出特征向量，然后，利用特征向量来进行匹配、查找。利用已有的算法，特征抽取可以由机器自动完成，这就克服了手工注释的低效和二义性。从多媒体中抽取出特征向量后，多媒体之间的相似性就转变为特征向量之间的相似性，多媒体信息查询就转变为特征向量的查询，然而，高维向量占用的磁盘空问很大，如果进行