量化编码的分层可通航小世界图算法

摘要：

随着大数据和人工智能的高速发展,针对多媒体数据的结构化处理与基于内容的检索受到极大的关注,面对多媒体数据结构化后的海量高维特征向量,如何快速、准确地检索是人工智能处理大规模数据所必须解决的问题.最近提出的分层可通航小世界图HNSW检索算法在多个公开数据集取得了最佳的性能表现,但该算法存在内存开销大的问题.而基于量化编码的检索算法能够压缩数据集向量,大幅度降低内存占用.将量化编码和分层可通航小世界图算法结合,提出了2种基于量化编码改进的HNSW算法,分别是使用标量量化编码向量的HNSWSQ算法和使用乘积量化编码向量的HNSWPQ算法,2种算法使用不同的量化策略存储原始向量编码,以降低内存开销,再通过HNSW算法建立索引达到缩短检索耗时的目的.其中HNSWSQ算法在多个数据集上获得了与HNSW算法相近的查全率和平均检索耗时,而内存开销大幅降低.实验结果表明,HNSWSQ算法在SIFT-1M和GIST-1M数据集上的内存开销比HNSW算法分别降低了45.1％和70.4％.

关键词：近似最近邻检索、分层可通航小世界图算法、乘积量化、标量量化、相似性搜索、高维数据索引

所属期刊栏目：41

分类号：TP311.13(计算技术、计算机技术)

资助基金：军委装备发展部科研订购局“十三五”装备预研领域基金61401320501

在线出版日期：2019-07-09（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：618-625