海量数据的高维索引结构研究

《海量数据的高维索引结构研究》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、河南大学硕士学位论文海量数据的高维索引结构研究姓名：于静洋申请学位级别：硕士专业：应用数学指导教师：曹奎20090501河南大学硕士研究生学位论文第1页摘要图像作为一种内容丰富、表现直观的媒体，在许多领域都得到了广泛应用，如数字图书馆、地理信息系统、生物信息学的DNA数据库和医学辅助诊断等。如何在大型图像数据库中快速处理基于内容的相似性检索变得越来越重要，高维索引技术是基于内容的相似性检索领域研究的一个基本问题，也是一个热点问题，因此研究海量数据的高维索引结构具有重要的理论和实际意义。然而，由于受到“维度灾难”的

2、影响，随着数据维数的增长，传统的索引结构性能急剧下降。针对上述问题，本文以大规模图像库的海量高维数据为背景，围绕图像特征的高维特性，通过实验研究分析了图像高维特征数据的距离分布特点，在此基础上，研究并设计了新的高维数据索引结构KVP．tree。论文的主要工作如下：第一，本文通过实验首先提取分类图像库和混合图像库的不同类型不同维数的特征向量并对其进行归一化，然后计算图像库中任意两幅图像之间的距离，最后分析得出高维数据的距离分布特点：高维空间中的距离分布具有较大的均值和较小的方差，其距离分布是“集中的”。进而分析得出

3、如下结论：高维空间的索引结构采用“平衡树”不一定是最好选择。第二，本文结合K．means聚类算法和M．tree的结点结构对VP．tree进行改进，给出了一种新的高维索引结构KVP．tree，介绍了其设计思想、结点结构、建树过程和查询方法，最后利用测试数据，对VP．tree和KVP—tree的性能进行深入的实验分析。通过实验对KVP．tree和VP．tree的查询性能进行了详细比较，KVP-tree增加了结点的输出能力，减少了距离计算次数，提高了查询效率。关键词：高维索引结构；特征提取；K-means聚类；VP—t

4、ree；M—tree第lI页河南大学硕士研究生学位论文AbstractImageasarich，intuitiveperformanceofthemedia，inmanyareashasbeenwidelyapplied，suchasdigitallibraries，geographicinformationsystems，theDNAdatabaseofbioinformatics，medicaldiagnosis，etc．Howtodealwithquicklycontent-basedsimilaritys

5、earchisbecomingincreasinglyimportantinalargeimagedatabase．High-dimensionalindexingtechnologyisnotonlyafundamentalissueofthefieldofthecontent-basedsimilarretrieval，butalsoahotissue．Sostudyingonhigh—dimensionalindexstructuresoflargedatahasimportanttheoreticalan

6、dpracticalsignificance．However，duetotheimpactof‘‘curseofdimensionality”，withthegrowthofthedatadimension，theperformanceofthetraditionalindexstructurehasdroppeddrastically．Inresponsetotheseproblemsabove，tohigh—dimensionaldataofmassiveimagesdatabaseasthebackgrou

7、nd，aroundthehigh-dimensionalcharacteristicsoftheimagecharacteristics，thispaperstudiedandanalyzedthedistancedistributioncharacteristicofhigh—dimensionalimagedatabyexperimental．Onthisbasis，theresearchanddesignanewstructureofhigh-dimensionaldataindexing，thatisKV

8、P—tree．Themaincontentsisasfollows：Firstly，byexperimentsthedifferenttypeandthedifferentdimensionfeaturevectorofclassificationimagesandmixedimagelibrarydatabaseareextractedanduniformed．Then