  Billion-scale high-dimensional approximate nearest neighbour (ANN) search has
become an important problem for searching similar objects among the vast amount
of images and videos available online. The existing ANN methods are usually
characterized by their specific indexing structures, including the inverted
index and the inverted multi-index structure. The inverted index structure is
amenable to GPU-based implementations, and the state-of-the-art systems such as
Faiss are able to exploit the massive parallelism offered by GPUs. However, the
inverted index requires high memory overhead to index the dataset effectively.
The inverted multi-index structure is difficult to implement for GPUs, and also
ineffective in dealing with database with different data distributions. In this
paper we propose a novel hierarchical inverted index structure generated by
vector and line quantization methods. Our quantization method improves both
search efficiency and accuracy, while maintaining comparable memory
consumption. This is achieved by reducing search space and increasing the
number of indexed regions. We introduce a new ANN search system, VLQ-ADC, that
is based on the proposed inverted index, and perform extensive evaluation on
two public billion-scale benchmark datasets SIFT1B and DEEP1B. Our evaluation
shows that VLQ-ADC significantly outperforms the state-of-the-art GPU- and
CPU-based systems in terms of both accuracy and search speed. The source code
of VLQ-ADC is available at
https://github.com/zjuchenwei/vector-line-quantization.
