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 上实现了开源分支。

更快的 ADC: 利用 SIMD 解锁产品量化的潜力

Quicker ADC : Unlocking the hidden potential of Product Quantization  with SIMD

Counting the number of ones in a binary stream is a common operation in
database, information-retrieval, cryptographic and machine-learning
applications. Most processors have dedicated instructions to count the number
of ones in a word (e.g., popcnt on x64 processors). Maybe surprisingly, we show
that a vectorized approach using SIMD instructions can be twice as fast as
using the dedicated instructions on recent Intel processors. The benefits can
be even greater for applications such as similarity measures (e.g., the Jaccard
index) that require additional Boolean operations. Our approach has been
adopted by LLVM: it is used by its popular C compiler (clang).

本文介绍一种使用 SIMD 指令来计算二进制流中数字 “1” 的数量的方法，该方法在最近的英特尔处理器上可以比专用指令快两倍以上，并且已被 LLVM 采用。

AVX2 指令加速人口统计速度

Faster Population Counts Using AVX2 Instructions

Sorted lists of integers are commonly used in inverted indexes and database
systems. They are often compressed in memory. We can use the SIMD instructions
available in common processors to boost the speed of integer compression
schemes. Our S4-BP128-D4 scheme uses as little as 0.7 CPU cycles per decoded
integer while still providing state-of-the-art compression.
However, if the subsequent processing of the integers is slow, the effort
spent on optimizing decoding speed can be wasted. To show that it does not have
to be so, we (1) vectorize and optimize the intersection of posting lists; (2)
introduce the SIMD Galloping algorithm. We exploit the fact that one SIMD
instruction can compare 4 pairs of integers at once.
We experiment with two TREC text collections, GOV2 and ClueWeb09 (Category
B), using logs from the TREC million-query track. We show that using only the
SIMD instructions ubiquitous in all modern CPUs, our techniques for conjunctive
queries can double the speed of a state-of-the-art approach.

本文阐述了如何使用 CPU 中常见的 SIMD 指令来压缩整数编码，并探究如何通过向量化和优化算法提高查询速度。

SIMD 压缩与排序整数的交集

SIMD Compression and the Intersection of Sorted Integers

In many important applications -- such as search engines and relational
database systems -- data is stored in the form of arrays of integers. Encoding
and, most importantly, decoding of these arrays consumes considerable CPU time.
Therefore, substantial effort has been made to reduce costs associated with
compression and decompression. In particular, researchers have exploited the
superscalar nature of modern processors and SIMD instructions. Nevertheless, we
introduce a novel vectorized scheme called SIMD-BP128 that improves over
previously proposed vectorized approaches. It is nearly twice as fast as the
previously fastest schemes on desktop processors (varint-G8IU and PFOR). At the
same time, SIMD-BP128 saves up to 2 bits per integer. For even better
compression, we propose another new vectorized scheme (SIMD-FastPFOR) that has
a compression ratio within 10% of a state-of-the-art scheme (Simple-8b) while
being two times faster during decoding.

本文介绍了一种基于 SIMD 指令的新型向量化方案，名为 SIMD-BP128，可以加速整数数组编码和解码，并提高节省存储空间。同时，还提出了一种名为 SIMD-FastPFOR 的新型向量化压缩方案，具有很好的压缩性能和解压速度。