论文部分内容阅读
高吞吐的特征检索对于大规模视觉特征检索意义重大。研究人员对R*树索引、局部敏感哈希算法、倒排索引方法等进行了大量的研究。但是，随着数据规模的增长，现有算法仍面临性能急剧下降的问题。本文深入分析了局部敏感哈希算法在特征规模增大时性能下降的原因，提出对特征数据进行划分，进而分块索引的思想来提高特征检索的吞吐率，取得了如下主要研究成果: 1.提出了视觉特征数据划分及索引方法。针对数据划分所涉及的分块数、划分依据和划分方法等问题进行了深入分析和实验对比，针对直方图和Gist两类典型视觉特征数据，提出了两套划分方法，并使用信息熵和K-L散度对算法的性能进行评价;基于划分后的数据分块分别建立局部敏感哈希索引。实验结果表明，该数据划分方法能够使得局部敏感哈希算法在千万规模数据集上的检索速度平均提升55％左右，而召回率仅有较小的损失。 2.针对数据划分方法导致的召回率降低问题，提出基于查询数据和查询范围的两种查询扩展策略，一是通过检测可能的排序结果变化，将一条查询扩展为多条。二是依据计算查询数据与划分数据中心的欧式距离，确定查询扩展的范围。实验结果表明两种查询扩展方法能够召回率分别提升4.30％和2.86％。 3.基于上述成果，本文研发了一套面向多处理器平台的大规模视频检索系统，对算法的性能进行验证。表明上述成果可有效提高大规模特征检索的吞吐率。此外，本文利用NUMA架构本地访存更快的特点和局部敏感哈希算法在分块数据上的检索性能优势，通过将不同分块索引检索绑定到不同CPU核上，进一步提升检索速度，实验表明，此方法可以获得额外的10～30％的速度提升。