高维空间近邻检索的双层组合量化GPU加速算法

作者：邓理睿; 包涵; 陈靓; 全成斌; 赵有健

来源：小型微型计算机系统, 2019, 40(02): 390-394.

• 近似近邻检索
• 组合量化
• GPU
• 高维索引

在大规模视频、图像、文本检索等许多实际应用中,高维空间内海量数据的索引及近邻检索一直是难点和关键问题之一.传统的K-D树等树形索引方法在高维空间中容易陷入"维度灾难",而主流的哈希散列方法(如局部敏感哈希)空间复杂度较高,在大规模数据下难以应用.本文总结了近年来基于向量量化的检索算法的相关研究,提出了一种基于GPU优化的高维数据近似近邻检索算法,在组合量化算法的基础上融合双层索引树结构与局部子空间最优化思想,在提高算法准确率的同时针对GPU模型优化算法,极大改善了检索性能,在单张GPU上实现了十亿量级高维数据的高效近似近邻检索.

• 单位
  中国石油勘探开发研究院; 清华大学