论文部分内容阅读
在图像、生物信息、医学成像、时间序列等领域需要对大数据集进行相似性查询。通过特征转换将数据对象特征映射为高维向量空间的特征向量，把相似性查询转换为向量空间的最近邻查询，即给定查询数据q及整数k，从数据库中找出距离q最近的k个数据。为了提高查询效率，研究者提出各种索引结构管理特征向量。这些索引结构在维数升高时性能会急剧下降，即“维灾”。针对高维数据索引结构的现状，我们在该领域进行了深入研究，取得了一定的成果。为了提高索引的检索效率，增强对高维的承受力，提出了多个具有良好性能的索引结构，并提供了利用这些高维索引支持图像相关反馈的方法。主要内容如下：首先，为了对聚类与查询性能之间的关系进行理论分析。提出一种新的基于聚类分解的高维度量空间B+-tree索引，它通过聚类分解对数据进行更细致的划分来减少查询的数据访问。对聚类与查询代价的关系进行了讨论，通过查询代价模型给出了最小查询代价条件下的聚类分解数目等的理论计算公式。实验显示提出的索引方法明显优于iDistance等度量空间索引，最优聚类分解数的估计接近实际最优查询时所需的聚类参数。然后，为了进一步改进高维数据库查询的效率。提出一种基于查询采样进行数据分布估计的方法，并在此基础上提出了一种支持最近邻查询的混合索引，即针对多媒体数据分布的不均匀性，有选择的使用树状索引和顺序扫描技术，建立统一的索引结构。建立混合索引的具体步骤为：首先通过聚类分解分割数据并建立树状索引；然后使用查询采样算法，对数据实际分布进行估计；最后根据数据分布的特性，把稀疏数据从树状索引中剪裁出来进行基于顺序扫描策略的索引，而分布比较密集的数据仍然保留在树状索引中。在五个真实的图像数据集上进行了充分的实验，结果显示提出的索引方法明显优于iDistance等度量空间索引，在维数达到三百多维时查询效率仍高于顺序扫描。实验结果还证明提出的查询采样算法在采样数据量仅为N1／2（N为数据量）的情况下就可以获得的满足索引需要的分布估计结果。最后，为了使得提出的索引结构能够在图像检索中应用，提出了利用高维索引支持用户相关反馈的方法。