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

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

作　　者：陈慧中[1,2] 陈永光[3] 景宁[1] 陈荦[1] 

机构地区：[1]国防科学技术大学电子科学与工程学院,长沙410073 [2]西南电子电信技术研究所上海分所,上海200434 [3]军械工程学院,石家庄050003

出　　处：《计算机学报》2011年第10期2009-2017,共9页Chinese Journal of Computers

基　　金：国家"八六三"高技术研究发展计划项目基金(2008AA12A211;2011AA12A306);国家自然科学基金(60902036)资助~~

摘　　要：提高特征向量的匹配效率是将高维局部特征运用于多媒体数据检索的关键.面向多核处理器架构,提出一种新的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.

关 键 词：特征向量匹配 多媒体检索 BBF 高维kNN查询 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]