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
Contributor : Fabien André Connect in order to contact the contributor
Submitted on : Monday, December 7, 2015 - 2:11:26 PM
Last modification on : Tuesday, October 19, 2021 - 11:58:51 PM
Long-term archiving on: : Tuesday, March 8, 2016 - 12:51:13 PM


Publisher files allowed on an open archive


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


  • HAL Id : hal-01239055, version 1


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⟩



Record views


Files downloads