Skip to Main content Skip to Navigation
Conference papers

Cache locality is not enough: High-Performance Nearest Neighbor Search with Product Quantization Fast Scan

Abstract : Nearest Neighbor (NN) search in high dimension is an important feature in many applications (e.g., image retrieval, multimedia databases). Product Quantization (PQ) is a widely used solution which offers high performance, i.e., low response time while preserving a high accuracy. PQ represents high-dimensional vectors (e.g., image descriptors) by compact codes. Hence, very large databases can be stored in memory, allowing NN queries without resorting to slow I/O operations. PQ computes distances to neighbors using cache-resident lookup tables, thus its performance remains limited by (i) the many cache accesses that the algorithm requires, and (ii) its inability to leverage SIMD instructions available on modern CPUs. In this paper, we advocate that cache locality is not sufficient for efficiency. To address these limitations, we design a novel algorithm, PQ Fast Scan, that transforms the cache-resident lookup tables into small tables, sized to fit SIMD registers. This transformation allows (i) in-register lookups in place of cache accesses and (ii) an efficient SIMD implementation. PQ Fast Scan has the exact same accuracy as PQ, while having 4 to 6 times lower response time (e.g., for 25 million vectors, scan time is reduced from 74ms to 13ms).
Complete list of metadata

Cited literature [23 references]  Display  Hide  Download

https://hal.inria.fr/hal-01239055
Contributor : Fabien André <>
Submitted on : Monday, December 7, 2015 - 2:11:26 PM
Last modification on : Thursday, January 7, 2021 - 4:20:37 PM
Long-term archiving on: : Tuesday, March 8, 2016 - 12:51:13 PM

File

p288-andre.pdf
Publisher files allowed on an open archive

Licence


Distributed under a Creative Commons Attribution - NonCommercial - NoDerivatives 4.0 International License

Identifiers

  • HAL Id : hal-01239055, version 1

Citation

Fabien André, Anne-Marie Kermarrec, Nicolas Le Scouarnec. Cache locality is not enough: High-Performance Nearest Neighbor Search with Product Quantization Fast Scan. 42nd International Conference on Very Large Data Bases, Sep 2016, New Delhi, India. pp.12. ⟨hal-01239055⟩

Share

Metrics

Record views

3028

Files downloads

801