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

3 Citations (Scopus)

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
Conference number: 9th
http://www.icmr2019.org/
https://dl.acm.org/doi/proceedings/10.1145/3323873

Conference

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

Keywords

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

Cite this