RobustiQ: a robust ANN search method for billion-scale similarity search on GPUs

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

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

Abstract

GPU-based methods represent state-of-the-art in approximate nearest neighbor (ANN) search, as they are scalable (billion-scale), accurate (high recall) as well as efficient (sub-millisecond query speed). Faiss, the representative GPU-based ANN system, achieves considerably faster query speed than the representative CPU-based systems. The query accuracy of Faiss critically depends on the number of indexing regions, which in turn is dependent on the amount of available memory. At the same time, query speed deteriorates dramatically with the increase in the number of partition regions. Thus, it can be observed that Faiss suffers from a lack of robustness, that the fine-grained partitioning of datasets is achieved at the expense of search speed, and vice versa. In this paper, we introduce a new GPU-based ANN search method, Robust Quantization (RobustiQ), that addresses the robustness limitations of existing GPU-based methods in a holistic way. We design a novel hierarchical indexing structure using vector and bilayer line quantization. This indexing structure, together with our indexing and encoding methods, allows RobustiQ to avoid the need for maintaining a large lookup table, hence reduces not only memory consumption but also query complexity. Our extensive evaluation on two public billion-scale benchmark datasets, SIFT1B and DEEP1B, shows that RobustiQ consistently obtains 2-3× speedup over Faiss while achieving better query accuracy for different codebook sizes. Compared to the best CPU-based ANN systems, RobustiQ achieves even more pronounced average speedups of 51.8× and 11× respectively.

Original languageEnglish
Title of host publicationProceedings of the 2019 on International Conference on Multimedia Retrieval
EditorsK. Selcuk Candan, Marco Bertini, Lixing Xie, Xiao-Yong Wei
Place of PublicationNew York NY USA
PublisherAssociation for Computing Machinery (ACM)
Pages132-140
Number of pages9
ISBN (Electronic)9781450367653
DOIs
Publication statusPublished - 2019
EventACM International Conference on Multimedia Retrieval 2019 - Ottawa, Canada
Duration: 10 Jun 201913 Jun 2019
http://www.icmr2019.org/

Conference

ConferenceACM International Conference on Multimedia Retrieval 2019
Abbreviated titleICMR 2019
CountryCanada
CityOttawa
Period10/06/1913/06/19
Internet address

Keywords

  • ANN search
  • Billion-scale
  • GPU
  • High-dimensional
  • Inverted index
  • Quantization
  • RobustiQ

Cite this

Chen, W., Chen, J., Zou, F., Li, Y-F., Lu, P., & Zhao, W. (2019). RobustiQ: a robust ANN search method for billion-scale similarity search on GPUs. In K. S. Candan, M. Bertini, L. Xie, & X-Y. Wei (Eds.), Proceedings of the 2019 on International Conference on Multimedia Retrieval (pp. 132-140). New York NY USA: Association for Computing Machinery (ACM). https://doi.org/10.1145/3323873.3325018
Chen, Wei ; Chen, Jincai ; Zou, Fuhao ; Li, Yuan-Fang ; Lu, Ping ; Zhao, Wei. / RobustiQ : a robust ANN search method for billion-scale similarity search on GPUs. Proceedings of the 2019 on International Conference on Multimedia Retrieval. editor / K. Selcuk Candan ; Marco Bertini ; Lixing Xie ; Xiao-Yong Wei. New York NY USA : Association for Computing Machinery (ACM), 2019. pp. 132-140
@inproceedings{097c767ade164b04b57f65684961f389,
title = "RobustiQ: a robust ANN search method for billion-scale similarity search on GPUs",
abstract = "GPU-based methods represent state-of-the-art in approximate nearest neighbor (ANN) search, as they are scalable (billion-scale), accurate (high recall) as well as efficient (sub-millisecond query speed). Faiss, the representative GPU-based ANN system, achieves considerably faster query speed than the representative CPU-based systems. The query accuracy of Faiss critically depends on the number of indexing regions, which in turn is dependent on the amount of available memory. At the same time, query speed deteriorates dramatically with the increase in the number of partition regions. Thus, it can be observed that Faiss suffers from a lack of robustness, that the fine-grained partitioning of datasets is achieved at the expense of search speed, and vice versa. In this paper, we introduce a new GPU-based ANN search method, Robust Quantization (RobustiQ), that addresses the robustness limitations of existing GPU-based methods in a holistic way. We design a novel hierarchical indexing structure using vector and bilayer line quantization. This indexing structure, together with our indexing and encoding methods, allows RobustiQ to avoid the need for maintaining a large lookup table, hence reduces not only memory consumption but also query complexity. Our extensive evaluation on two public billion-scale benchmark datasets, SIFT1B and DEEP1B, shows that RobustiQ consistently obtains 2-3× speedup over Faiss while achieving better query accuracy for different codebook sizes. Compared to the best CPU-based ANN systems, RobustiQ achieves even more pronounced average speedups of 51.8× and 11× respectively.",
keywords = "ANN search, Billion-scale, GPU, High-dimensional, Inverted index, Quantization, RobustiQ",
author = "Wei Chen and Jincai Chen and Fuhao Zou and Yuan-Fang Li and Ping Lu and Wei Zhao",
year = "2019",
doi = "10.1145/3323873.3325018",
language = "English",
pages = "132--140",
editor = "Candan, {K. Selcuk } and Bertini, {Marco } and Xie, {Lixing } and Wei, {Xiao-Yong }",
booktitle = "Proceedings of the 2019 on International Conference on Multimedia Retrieval",
publisher = "Association for Computing Machinery (ACM)",
address = "United States of America",

}

Chen, W, Chen, J, Zou, F, Li, Y-F, Lu, P & Zhao, W 2019, RobustiQ: a robust ANN search method for billion-scale similarity search on GPUs. in KS Candan, M Bertini, L Xie & X-Y Wei (eds), Proceedings of the 2019 on International Conference on Multimedia Retrieval. Association for Computing Machinery (ACM), New York NY USA, pp. 132-140, ACM International Conference on Multimedia Retrieval 2019, Ottawa, Canada, 10/06/19. https://doi.org/10.1145/3323873.3325018

RobustiQ : a robust ANN search method for billion-scale similarity search on GPUs. / Chen, Wei; Chen, Jincai; Zou, Fuhao; Li, Yuan-Fang; Lu, Ping; Zhao, Wei.

Proceedings of the 2019 on International Conference on Multimedia Retrieval. ed. / K. Selcuk Candan; Marco Bertini; Lixing Xie; Xiao-Yong Wei. New York NY USA : Association for Computing Machinery (ACM), 2019. p. 132-140.

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

TY - GEN

T1 - RobustiQ

T2 - a robust ANN search method for billion-scale similarity search on GPUs

AU - Chen, Wei

AU - Chen, Jincai

AU - Zou, Fuhao

AU - Li, Yuan-Fang

AU - Lu, Ping

AU - Zhao, Wei

PY - 2019

Y1 - 2019

N2 - GPU-based methods represent state-of-the-art in approximate nearest neighbor (ANN) search, as they are scalable (billion-scale), accurate (high recall) as well as efficient (sub-millisecond query speed). Faiss, the representative GPU-based ANN system, achieves considerably faster query speed than the representative CPU-based systems. The query accuracy of Faiss critically depends on the number of indexing regions, which in turn is dependent on the amount of available memory. At the same time, query speed deteriorates dramatically with the increase in the number of partition regions. Thus, it can be observed that Faiss suffers from a lack of robustness, that the fine-grained partitioning of datasets is achieved at the expense of search speed, and vice versa. In this paper, we introduce a new GPU-based ANN search method, Robust Quantization (RobustiQ), that addresses the robustness limitations of existing GPU-based methods in a holistic way. We design a novel hierarchical indexing structure using vector and bilayer line quantization. This indexing structure, together with our indexing and encoding methods, allows RobustiQ to avoid the need for maintaining a large lookup table, hence reduces not only memory consumption but also query complexity. Our extensive evaluation on two public billion-scale benchmark datasets, SIFT1B and DEEP1B, shows that RobustiQ consistently obtains 2-3× speedup over Faiss while achieving better query accuracy for different codebook sizes. Compared to the best CPU-based ANN systems, RobustiQ achieves even more pronounced average speedups of 51.8× and 11× respectively.

AB - GPU-based methods represent state-of-the-art in approximate nearest neighbor (ANN) search, as they are scalable (billion-scale), accurate (high recall) as well as efficient (sub-millisecond query speed). Faiss, the representative GPU-based ANN system, achieves considerably faster query speed than the representative CPU-based systems. The query accuracy of Faiss critically depends on the number of indexing regions, which in turn is dependent on the amount of available memory. At the same time, query speed deteriorates dramatically with the increase in the number of partition regions. Thus, it can be observed that Faiss suffers from a lack of robustness, that the fine-grained partitioning of datasets is achieved at the expense of search speed, and vice versa. In this paper, we introduce a new GPU-based ANN search method, Robust Quantization (RobustiQ), that addresses the robustness limitations of existing GPU-based methods in a holistic way. We design a novel hierarchical indexing structure using vector and bilayer line quantization. This indexing structure, together with our indexing and encoding methods, allows RobustiQ to avoid the need for maintaining a large lookup table, hence reduces not only memory consumption but also query complexity. Our extensive evaluation on two public billion-scale benchmark datasets, SIFT1B and DEEP1B, shows that RobustiQ consistently obtains 2-3× speedup over Faiss while achieving better query accuracy for different codebook sizes. Compared to the best CPU-based ANN systems, RobustiQ achieves even more pronounced average speedups of 51.8× and 11× respectively.

KW - ANN search

KW - Billion-scale

KW - GPU

KW - High-dimensional

KW - Inverted index

KW - Quantization

KW - RobustiQ

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

U2 - 10.1145/3323873.3325018

DO - 10.1145/3323873.3325018

M3 - Conference Paper

SP - 132

EP - 140

BT - Proceedings of the 2019 on International Conference on Multimedia Retrieval

A2 - Candan, K. Selcuk

A2 - Bertini, Marco

A2 - Xie, Lixing

A2 - Wei, Xiao-Yong

PB - Association for Computing Machinery (ACM)

CY - New York NY USA

ER -

Chen W, Chen J, Zou F, Li Y-F, Lu P, Zhao W. RobustiQ: a robust ANN search method for billion-scale similarity search on GPUs. In Candan KS, Bertini M, Xie L, Wei X-Y, editors, Proceedings of the 2019 on International Conference on Multimedia Retrieval. New York NY USA: Association for Computing Machinery (ACM). 2019. p. 132-140 https://doi.org/10.1145/3323873.3325018