支持最近邻查找的高维空间索引

《支持最近邻查找的高维空间索引》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、复旦大学博士学位论文支持最近邻查找的高维空间索引姓名：张军旗申请学位级别：博士专业：计算机软件与理论指导教师：施伯乐20070410论文独创性声明本论文是我个人在导师指导下进行的研究工作及取得的研究成果。论文中除了特别加以标注和致谢的地方外，不包含其他人或其它机构已经发表或撰写过的研究成果。其他同志对本研究的启发和所做的贡献均已在论文中作了明确的声明并表示了谢意。作者签名：．麦量军蕴论文使用授权声明日期：塑!!Z：墨：，／本人完全了解复旦大学有关保留、使用学位论文的规定，即：学校有权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内容，可以采用影印、缩印

2、或其它复制手段保存论文。保密的论文在解密后遵守此规定。作者签名：墨红圣丝导师签名：幺巡日期：竺!z：量z』复且大学博十毕业论文：支持最近邻查找的高维空间索引张军旗摘要在图像、生物信息、医学成像、时间序列等领域需要对大数据集进行相似性查询。通过特征转换将数据对象特征映射为高维向量空间的特征向量，把相似性查询转换为向量空间的最近邻查询，即给定查询数据q及整数k，从数据库中找出距离q最近的k个数据。为了提高查询效率，研究者提出各种索引结构管理特征向量。这些索引结构在维数升高时性能会急剧下降，即“维灾”。针对高维数据索引结构的现状，我们在该领域进行了深入研究，取得了一定的成果。为了提高

3、索引的检索效率，增强对高维的承受力，提出了多个具有良好性能的索引结构，并提供了利用这些高维索引支持图像相关反馈的方法。主要内容如下：首先，为了对聚类与查询性能之间的关系进行理论分析。提出一种新的基于聚类分解的高维度量空间B+一tree索引，它通过聚类分解对数据进行更细致的划分来减少查询的数据访问。对聚类与查询代价的关系进行了讨论，通过查询代价模型给出了最小查询代价条件下的聚类分解数目等的理论计算公式。实验显示提出的索引方法明显优于iDistance等度量空间索引，最优聚类分解数的估计接近实际最优查询时所需的聚类参数。然后，为了进一步改进高维数据库查询的效率。提出一种基于查询采样

4、进行数据分布估计的方法，并在此基础上提出了一种支持最近邻查询的混合索引，即针对多媒体数据分布的不均匀性，有选择的使用树状索引和顺序扫描技术，建立统一的索引结构。建立混合索引的具体步骤为：首先通过聚类分解分割数据并建立树状索引；然后使用查询采样算法，对数据实际分布进行估计；最后根据数据分布的特性，把稀疏数据从树状索引中剪裁出来进行基于顺序扫描策略的索引，而分布比较密集的数据仍然保留在树状索引中。在五个真实的图像数据集上进行了充分的实验，结果显示提出的索引方法明显优于iDistance等度量空间索引，在维数达到三百多维时查询效率仍高于顺序扫描。实验结果还证明提出的查询采样算法在采样

5、数据量仅为√Ⅳ(N为数据量)的情况下就可以获得的满足索引需要的分布估计结果。最后，为了使得提出的索引结构能够在图像检索中应用，提出了利用高维索引支持用户相关反馈的方法。关键词：最近邻查询，采样，高维索引结构，边缘数据，聚类分解复且大学博七毕业论文：支持最近邻查找的高维审问索引张军旗AbstractManyemergingdatabaseapplicationssuchasimage，timeseriesandscientificdatabases，manipulatehighdimensionaldata．Intheseapplications，Orleofthemostfre

6、quentlyusedandyetexpensiveoperationsistofindobjectsinthehigh-dimensionaldatabasethataresimilartoagivenqueryobject．Nearestneighborsearchisacentralrequirementinsuchcases．Thereisalongstr&dmofresearchonsolvingthenearestneighborsearchproblem,andalargenumberofmultidimensionalindexeshavebeendevelop

7、edforthispurpose．HowevertheseindexesturnworsewitIlthedimensiongrowth,whichiscalleddimensionalitycurse．Inordertoimprovethequeryefficiency,K-meansclusterapproachisoftenusedtoestimatethedatadistributioninthecontextofhighdimensionalmetricspaceindex．But