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, Andr\'e et al.
proposed Quick ADC with up to $6\times$ faster implementations of $m\times{}4$
product quantizers (PQ) leveraging specific SIMD instructions. Quicker ADC is a
generalization of Quick ADC not limited to $m\times{}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 at
this http URL

该研究提出了 Quicker ADC 算法，利用 SIMD 指令和不规则的产生量化器，实现了更高效的高维空间多媒体检索和最近邻搜索，且优于当前优化实现，并在 FAISS 上实现了开源分支。