基于单维映射的高维索引结构研究及其应用

摘要

多媒体内容检测是多媒体数据库中的一项重要应用。内容检测时提取的特征向量往往具有高维特性，传统的多维索引结构在高维空间中会面临着“维数灾难”问题。本文针对高维空间中的查询效率问题，提出了一种新的基于单维映射的高维索引方法，能够加速多媒体数据的相似性检测。
　　 本文首先分析了高维索引技术的发展历程和各类索引结构的特点。面向向量空间中的k 近邻搜索，提出了一种新的结合主分量和距离过滤的单维映射方法-pcDistance。首先将高维数据点集进行聚类划分，对每个聚类进行主分量分析，将数据点与聚类中心的距离映射为一维数据，并采用B+-Tree 索引这些一维数据。在k 近邻搜索中，根据查询向量与主分量坐标轴的空间关系对数据点进行过滤，并且采用部分失真搜索算法加速搜索过程。实验结果表明，与其他索引方法相比，新方法能够显著降低搜索过程中的数据访问数量，提高k 近邻搜索性能。本文最后将pcDistance 方法应用到雷同视频片段检测中，采用pcDistance 索引视频片段特征-有界坐标系(Bounded Coordinate System)，通过在5 万规模的视频片段库中进行实验表明，采用pcDistance 方法能够加快雷同视频片段的检测速度。