Indexing 1G vectors

mdouze edited this page Mar 1, 2017 · 1 revision

For those datasets, compression becomes mandatory (we are talking here about 50M-1G per server). The main compression method used in Faiss is PQ (product quantizer) compression, with a pre-selection based on a coarse quantizer (see previous section).

Bigann dataset

The Bigann dataset is a classical benchmark used in computer vision. It contains 1 billion SIFT descriptors. The plot below shows that it is relatively easy to index:

These results were obtained with bench_polysemous_1bn.py:

python bench_polysemous_1bn.py SIFT1000M OPQ8_64,IMI2x14,PQ8 autotuneMT

Deep1B dataset

Another research dataset that was introduced in this CVPR'16 paper. It contains 1Bn 96D descriptors.

Comparison with the state-of-the-art

Bigann

A recent CVPR'16 paper has a GPU implementation for the search. We experiment with relatively low-precision operating points (8 bytes per code) to allow for a direct comparison with published papers. Note however that for high quality neighbors, more bytes would be required (see above).

Method Hardware R@10 query time (ms) / vector
Wieschollek et al. CVPR'16 Titan X 0.35 0.15
OPQ8_64,IMI2x13,PQ8x8 CPU (1 thread) 0.349 0.4852
" CPU (20 threads) 0.349 0.035
OPQ8_32,IVF262144,PQ8 Titan X 0.376 0.0340
" " 0.448 0.1214

(methods are described with their index_factory string)

Deep1B

The operating point we are interested in is one that takes ~25 GB of RAM, which corresponds to 20-byte PQ codes. The first row is the best operating point we are aware of at the time we made the comparison. The other rows correspond to different operating points achieved by CPU- and GPU-Faiss algorithms.

Method Hardware R@1 query time (ms) / vector
Babenko & al. CVPR'16 CPU (1 thread) 0.45 20
OPQ20_80,IMI2x14,PQ20 CPU (1 thread) 0.4561 3.66
OPQ20_80,IVF262144,PQ20 4*K40 0.488 0.18
" 4*K40 0.493 1.1
OPQ32,IVF262144,PQ32 8*TitanX 0.671 0.2328
OPQ64_128,IVF262144,PQ64 (float16 mode) 8*TitanX 0.856 0. 3207
You can’t perform that action at this time.
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.
Press h to open a hovercard with more details.