Vector and line quantization for billion-scale similarity search on GPUs

Wei Chen, Jincai Chen, Fuhao Zou, Yuan Fang Li, Ping Lu, Qiang Wang, Wei Zhao

Research output: Contribution to journalArticleResearchpeer-review

Abstract

Billion-scale high-dimensional approximate nearest neighbor (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 publicly available online. 1

Original languageEnglish
Pages (from-to)295-307
Number of pages13
JournalFuture Generation Computer Systems
Volume99
DOIs
Publication statusPublished - Oct 2019

Keywords

  • Billion-scale similarity search
  • GPU
  • High dimensional data
  • Inverted index
  • Quantization

Cite this

Chen, Wei ; Chen, Jincai ; Zou, Fuhao ; Li, Yuan Fang ; Lu, Ping ; Wang, Qiang ; Zhao, Wei. / Vector and line quantization for billion-scale similarity search on GPUs. In: Future Generation Computer Systems. 2019 ; Vol. 99. pp. 295-307.
@article{1271efbcbe3e4a8195ded0ec534284b1,
title = "Vector and line quantization for billion-scale similarity search on GPUs",
abstract = "Billion-scale high-dimensional approximate nearest neighbor (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 publicly available online. 1",
keywords = "Billion-scale similarity search, GPU, High dimensional data, Inverted index, Quantization",
author = "Wei Chen and Jincai Chen and Fuhao Zou and Li, {Yuan Fang} and Ping Lu and Qiang Wang and Wei Zhao",
year = "2019",
month = "10",
doi = "10.1016/j.future.2019.04.033",
language = "English",
volume = "99",
pages = "295--307",
journal = "Future Generation Computer Systems",
issn = "0167-739X",
publisher = "Elsevier",

}

Vector and line quantization for billion-scale similarity search on GPUs. / Chen, Wei; Chen, Jincai; Zou, Fuhao; Li, Yuan Fang; Lu, Ping; Wang, Qiang; Zhao, Wei.

In: Future Generation Computer Systems, Vol. 99, 10.2019, p. 295-307.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Vector and line quantization for billion-scale similarity search on GPUs

AU - Chen, Wei

AU - Chen, Jincai

AU - Zou, Fuhao

AU - Li, Yuan Fang

AU - Lu, Ping

AU - Wang, Qiang

AU - Zhao, Wei

PY - 2019/10

Y1 - 2019/10

N2 - Billion-scale high-dimensional approximate nearest neighbor (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 publicly available online. 1

AB - Billion-scale high-dimensional approximate nearest neighbor (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 publicly available online. 1

KW - Billion-scale similarity search

KW - GPU

KW - High dimensional data

KW - Inverted index

KW - Quantization

UR - http://www.scopus.com/inward/record.url?scp=85065523797&partnerID=8YFLogxK

U2 - 10.1016/j.future.2019.04.033

DO - 10.1016/j.future.2019.04.033

M3 - Article

VL - 99

SP - 295

EP - 307

JO - Future Generation Computer Systems

JF - Future Generation Computer Systems

SN - 0167-739X

ER -