Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Quicker ADC : Unlocking the Hidden Potential of Product Quantization With SIMD
 
research article

Quicker ADC : Unlocking the Hidden Potential of Product Quantization With SIMD

Andre, Fabien
•
Kermarrec, Anne-Marie  
•
Le Scouarnec, Nicolas
May 1, 2021
Ieee Transactions On Pattern Analysis And Machine Intelligence

Efficient Nearest Neighbor (NN) search in high-dimensional spaces is a foundation of many multimedia retrieval systems. A common approach is to rely on Product Quantization, which allows the storage of large vector databases in memory and efficient distance computations. Yet, implementations of nearest neighbor search with Product Quantization have their performance limited by the many memory accesses they perform. Following this observation, Andre et al. proposed Quick ADC with up to 6x faster implementations of PQ m x 4 product quantizers (PQ) leveraging specific SIMD instructions. Quicker ADC is a generalization of Quick ADC not limited to PQ m x 4 codes and supporting AVX-512, the latest revision of SIMD instruction set. In doing so, Quicker ADC faces the challenge of using efficiently 5,6 and 7-bit shuffles that do not align to computer bytes or words. To this end, we introduce (i) irregular product quantizers combining sub-quantizers of different granularity and (ii) split tables allowing lookup tables larger than registers. We evaluate Quicker ADC with multiple indexes including Inverted Multi-Indexes and IVF HNSW and show that it outperforms the reference optimized implementations (i.e., FAISS and polysemous codes) for numerous configurations. Finally, we release an open-source fork of FAISS enhanced with Quicker ADC.

  • Details
  • Metrics
Type
research article
DOI
10.1109/TPAMI.2019.2952606
Web of Science ID

WOS:000637533800013

Author(s)
Andre, Fabien
Kermarrec, Anne-Marie  
Le Scouarnec, Nicolas
Date Issued

2021-05-01

Publisher

IEEE COMPUTER SOC

Published in
Ieee Transactions On Pattern Analysis And Machine Intelligence
Volume

43

Issue

5

Start page

1666

End page

1677

Subjects

Computer Science, Artificial Intelligence

•

Engineering, Electrical & Electronic

•

Computer Science

•

Engineering

•

image databases

•

information search and retrieval

•

nearest neighbor search

•

product quantization

•

simd

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
SACS  
Available on Infoscience
May 22, 2021
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/178193
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés