PCPF:一种面向多媒体数据库中高维向量匹配的并行索引结构

PCPF:A Parallel Index for Matching the High-Dimensional Vectors in Multimedia Databases

提高特征向量的匹配效率是将高维局部特征运用于多媒体数据检索的关键.面向多核处理器架构,提出一种新的PCPF索引以及PCPF并行构建与并行查询匹配算法.PCPF并行构建算法通过量化特征向量构建近似向量空间上的高维索引结构,并进行空间划分并行构建多个子索引分支;PCPF并行查询匹配算法利用优先队列在邻近子分支上并行过滤得到近似近邻候选集,精确计算候选实际特征向量得到最终近邻.实验及分析表明,与经典的BBF算法相比较,PCPF通过降低了磁盘I/O和浮点运算次数以及并行优化,显著提升了查询匹配效率,总体匹配精度也有所提高.

The key point in applying high-dimensional local features to retrieval in multimedia databases is to improve the efficiency of feature matching.Facing the multi-processor architecture,we have investigated a novel Parallel Compressed Priority Filter（PCPF） index,together with the corresponding parallel construct and query algorithms.The PCPF quantizes the feature vectors to compress the search space,constructs a high-dimensional index with several branches,searches candidates via priority queue in different branches,and calculates the exact feature vectors to get the nearest neighbors in parallel.It has been proved by experiments and via analysis that PCPF can reduce disk I/O and float-pointing calculation.It is also optimized by parallel.It is much faster and more precise than the classical BBF algorithm with no increase of constructive time.