Searching in one billion vectors: re-rank with source coding
Abstract
Recent indexing techniques inspired by source coding have been shown successful to index billions of high-dimensional vectors in memory. In this paper, we propose an approach that re-ranks the neighbor hypotheses obtained by these compressed-domain indexing methods. In contrast to the usual post-verification scheme, which performs exact distance calculation on the short-list of hypotheses, the estimated distances are refined based on short quantization codes, to avoid reading the full vectors from disk.
中文速览
大规模图像检索系统每次查询都要从磁盘随机读取原始高维向量来做精确距离重排，这在十亿级数据库中极其缓慢且耗内存。本文提出在乘积量化（Product Quantization）索引框架下，用一个额外的"残差量化器"对第一轮检索的量化误差再编码，从而在纯内存、纯压缩码的条件下完成候选列表重排，完全绕开了读磁盘的瓶颈。为了支撑真实规模的评测，作者还发布了包含十亿条128维SIFT向量的公开基准数据集BIGANN。实验表明，该方法在仅用少量额外内存（每个向量多几个字节）的前提下，检索精度显著优于传统的精确距离后验证方案，在十亿规模上达到当时的最优水平，对此后大规模近似最近邻搜索研究具有重要的基准和方法论参考价值。
原文 arXiv:1102.3828;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1102.3828v1