Improving Bilayer Product Quantization for Billion-Scale Approximate Nearest Neighbors in High Dimensions
Artem Babenko Victor Lempitsky Yandex Moscow Institute of Physics and Technology Skolkovo Institute of Science and Technology
Abstract
The top-performing systems for billion-scale high-dimensional approximate nearest neighbor (ANN) search are all based on two-layer architectures that include an indexing structure and a compressed datapoints layer. An indexing structure is crucial as it allows to avoid exhaustive search, while the lossy data compression is needed to fit the dataset into RAM. Several of the most successful systems use product quantization (PQ) [4] for both the indexing and the dataset compression layers. These systems are however limited in the way they exploit the interaction of product quantization processes that happen at different stages of these systems.
中文速览
现有十亿级高维近似最近邻搜索（Approximate Nearest Neighbor, ANN）的顶尖系统都采用"索引结构+压缩数据"两层架构，其中乘积量化（Product Quantization, PQ）被同时用于两层，但各层之间的协同潜力从未被充分利用。本文提出两个新系统：FBPQ通过引入快速非对称距离计算（ADC），避免了原有系统中显式重建位移向量的低效做法，将距离计算复杂度从线性于数据维度降至线性于PQ码长，实测速度比现有最优系统快数倍乃至15倍；HBPQ则利用两层均采用PQ的结构特性，为每个索引格子构建局部码本而非共用全局码本，以极小的内存开销换取显著更高的召回率，在十亿级BIGANN数据集上Recall@1提升10%、Recall@10提升17%。这两个系统刷新了十亿级高维向量ANN搜索在速度和精度两个维度上的最优记录，对大规模多媒体检索等实际应用具有重要价值。
原文 arXiv:1404.1831;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1404.1831v1