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

By Fabien André, Anne-Marie Kermarrec, Nicolas Le Scouarnec. 2015

134 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Information Retrieval & Search

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Information Retrieval & Search

Citations in the corpus

Billion-Scale Similarity Search with GPUs (2017, methodology): “L1 cache with little eort, and L1 cache latency and bandwidth remains a limiting factor. Other similarity search components, like PQ code manipulation, tend to have greater impact on CPU performance [2]. GPU heaps. Heaps can be similarly implemented on a GPU [7]. However, a straightforward GPU heap ”
Approximate Nearest Neighbor Search on High Dimensional Data - Experiments, Analyses, and Improvement (v1.0) (2016, methodology): “We exclude a recent work [4] optimizing the performance of product quantization-based method as it is mainly based on utilizing the hardware-specific features.”
Milvus: A Purpose-Built Vector Data Management System (2021, background): “Prior works on approximate search can be roughly classified in four categories: LSH-based [23, 23, 24, 32, 40, 44, 45, 48, 73], tree-based [17, 46, 54, 57], graph-based [20, 43, 49, 61, 72], and quantization-based [3, 6, 22, 27, 33, 35].”
Multiscale Quantization for Fast Similarity Search (2017, methodology): “product codes under the same bitrate, and ADC can be computed with similar speed ([2, 21], Section 4.”
LLMs Meet Isolation Kernel: Lightweight, Learning-free Binary Embeddings for Fast Retrieval (2026, unknown): “…in high-dimensional spaces, techniques such as dimensionality reduction (Van Der Maaten et al., 2009), product quantization (Guo et al., 2020; Jégou et al., 2011; André et al., 2015), hashing (Charikar, 2002; Xu and Ting, 2025) are commonly applied, though often at the expense of accuracy.”