Product Quantization for Nearest Neighbor Search

This paper introduces a product quantization-based approach for approximate nearest neighbor search. The idea is to decompose the space into a Cartesian product of low-dimensional subspaces and to quantize each subspace separately. A vector is represented by a short code composed of its subspace quantization indices. The euclidean distance between two vectors can be efficiently estimated from their codes. An asymmetric version increases precision, as it computes the approximate distance between a vector and a code. Experimental results show that our approach searches for nearest neighbors efficiently, in particular in combination with an inverted file system. Results for SIFT and GIST image descriptors show excellent search accuracy, outperforming three state-of-the-art approaches. The scalability of our approach is validated on a data set of two billion vectors.

• Publication year

  2011

• Venue

  IEEE Transactions on Pattern Analysis and Machine Intelligence

• Publication date

  Unknown publication date

• Fields of study

  Mathematics, Computer Science, Medicine

• Identifiers
  DOI 10.1109/TPAMI.2010.57PMID 21088323
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar, PubMed

• No claims are published for this paper.

• No concepts are published for this paper.

• A new approach to interdomain routing based on secure multi-party computation

  2012cited by this paper
• Searching with expectations

  2010cited by this paper
• Nearest Neighbor

  2010cited by this paper
• Searching with quantization: approximate nearest neighbor search using short codes and distance estimators

  2009cited by this paper
• Packing bag-of-features

  2009cited by this paper
• Evaluation of GIST descriptors for web-scale image search

  2009cited by this paper
• Kernelized locality-sensitive hashing for scalable image search

  2009cited by this paper
• Fast Approximate Nearest Neighbors with Automatic Algorithm Configuration

  2009cited by this paper
• Efficient representation of local geometry for large scale object retrieval

  2009cited by this paper
• Lost in quantization: Improving particular object retrieval in large scale image databases

  2008cited by this paper
• Nearest-Neighbor Methods in Learning and Vision (Shakhnarovich, G. et al., Eds.; 2006) [Book review]

  2008cited by this paper
• 80 Million Tiny Images: A Large Data Set for Nonparametric Object and Scene Recognition

  2008cited by this paper
• Hamming Embedding and Weak Geometric Consistency for Large Scale Image Search

  2008influential reference
• Small codes and large image databases for recognition

  2008cited by this paper
• Nearest-Neighbor Methods in Learning and Vision

  2008cited by this paper
• Optimised KD-trees for fast image descriptor matching

  2008cited by this paper
• Object retrieval with large vocabularies and fast spatial matching

  2007cited by this paper
• A contextual dissimilarity measure for accurate and efficient image search

  2007cited by this paper
• Nearest-Neighbor Methods in Learning and Vision: Theory and Practice (Neural Information Processing)

  2006cited by this paper
• Scalable Recognition with a Vocabulary Tree

  2006cited by this paper
• Rapid object indexing using locality sensitive hashing and joint 3D-signature space estimation

  2006cited by this paper
• Distinctive Image Features from Scale-Invariant Keypoints

  2004cited by this paper
• Locality-sensitive hashing scheme based on p-stable distributions

  2004influential reference
• Minimum Sum-Squared Residue Co-Clustering of Gene Expression Data

  2004cited by this paper
• Efficient Near-duplicate Detection and Sub-image Retrieval

  2004cited by this paper
• An efficient parts-based near-duplicate and sub-image retrieval system

  2004cited by this paper
• Video Google: a text retrieval approach to object matching in videos

  2003influential reference
• Searching in high-dimensional spaces: Index structures for improving the performance of multimedia databases

  2001cited by this paper
• Modeling the Shape of the Scene: A Holistic Representation of the Spatial Envelope

  2001cited by this paper
• Similarity Search in High Dimensions via Hashing

  1999cited by this paper
• When Is ''Nearest Neighbor'' Meaningful?

  1999cited by this paper
• A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces

  1998cited by this paper
• An Algorithm for Finding Best Matches in Logarithmic Expected Time

  1977cited by this paper
• The art of computer programming: sorting and searching (volume 3)

  1973cited by this paper
• The Art of Computer Programming

  1968cited by this paper
• Ieee Transactions on Pattern Analysis and Machine Intelligence 1 80 Million Tiny Images: a Large Dataset for Non-parametric Object and Scene Recognition

  year unknowncited by this paper

• PiPNN: Ultra-Scalable Graph-Based Nearest Neighbor Indexing

  2026cites this paper
• CytoVerse: Single-Cell AI Foundation Models in the Browser

  2026cites this paper
• MERGE: Next-Generation Item Indexing Paradigm for Large-Scale Streaming Recommendation

  2026cites this paper
• SOM-VQ: Topology-Aware Tokenization for Interactive Generative Models

  2026cites this paper
• I/O Optimizations for Graph-Based Disk-Resident Approximate Nearest Neighbor Search: A Design Space Exploration

  2026cites this paper
• CURP: Codebook-based Continuous User Representation for Personalized Generation with LLMs

  2026cites this paper
• RAIRS: Optimizing Redundant Assignment and List Layout for IVF-Based ANN Search

  2026cites this paper
• Feature-Indexed Federated Recommendation with Residual-Quantized Codebooks

  2026cites this paper
• Kelix Technical Report

  2026cites this paper
• Multi-Vector Index Compression in Any Modality

  2026cites this paper
• Torus embeddings

  2026influential citation
• Parametric Chunk Quantization Algorithm for Fast Passive Emitter Localization

  2026cites this paper
• From vectors to knowledge graphs: A comprehensive analysis of modern retrieval-augmented generation architectures

  2026cites this paper
• Fast $k$-means Seeding Under The Manifold Hypothesis

  2026cites this paper
• Aggressive Compression Enables LLM Weight Theft

  2026cites this paper
• Multivector Reranking in the Era of Strong First-Stage Retrievers

  2026cites this paper
• LOOKAT: Lookup-Optimized Key-Attention for Memory-Efficient Transformers

  2026cites this paper
• A code distribution-based trajectory representation and its application to similarity, clustering and classification of AIS big data

  2026cites this paper
• Embedding Compression via Spherical Coordinates

  2026cites this paper
• Next Concept Prediction in Discrete Latent Space Leads to Stronger Language Models

  2026cites this paper
• Unleash the Potential of Long Semantic IDs for Generative Recommendation

  2026influential citation
• CQ-CiM: Hardware-Aware Embedding Shaping for Robust CiM-Based Retrieval

  2026cites this paper
• PP-EDUVec: Privacy-Preserving Intelligent Management Algorithms for Educational-Corpus Vector Databases Under Retrieval-Augmented Learning

  2026cites this paper
• VectorMaton: Efficient Vector Search with Pattern Constraints via an Enhanced Suffix Automaton

  2026cites this paper
• AQPIM: Breaking the PIM Capacity Wall for LLMs with in-Memory Activation Quantization

  2026cites this paper
• Optimizing SSD-Resident Graph Indexing for High-Throughput Vector Search

  2026cites this paper
• GPU-Accelerated Algorithms for Graph Vector Search: Taxonomy, Empirical Study, and Research Directions

  2026influential citation
• Deep Learning to Rank in Industrial Search Engines, Recommender Systems and Online Advertising: An Overview and New Perspectives

  2026cites this paper
• Deterministic Retrieval at Scale: Optimal-Space LCP Indexing and 308x Energy Reduction on Modern GPUs

  2026cites this paper
• Fast Autoregressive Video Diffusion and World Models with Temporal Cache Compression and Sparse Attention

  2026cites this paper
• Efficient low-rank index routing for high-dimensional approximate nearest neighbor search

  2026cites this paper
• LooC: Effective Low-Dimensional Codebook for Compositional Vector Quantization

  2026influential citation
• Curator: Efficient Vector Search with Low-Selectivity Filters

  2026cites this paper
• PROMISE: Process Reward Models Unlock Test-Time Scaling Laws in Generative Recommendations

  2026cites this paper
• SVFusion: A CPU-GPU Co-Processing Architecture for Large-Scale Real-Time Vector Search

  2026cites this paper
• FaTRQ: Tiered Residual Quantization for LLM Vector Search in Far-Memory-Aware ANNS Systems

  2026cites this paper
• Efficient Time-Restricted kNN Search in High-Dimensional Data Using Multi-Level Block Indexing, with Extensions to Multi-Attribute Filtering

  2026cites this paper
• SIVF: GPU-Resident IVF Index for Streaming Vector Analytics

  2026cites this paper
• Attention in Geometry: Scalable Spatial Modeling via Adaptive Density Fields and FAISS-Accelerated Kernels

  2026cites this paper
• QVCache: A Query-Aware Vector Cache

  2026cites this paper
• CSRv2: Unlocking Ultra-Sparse Embeddings

  2026cites this paper
• Prune, Don't Rebuild: Efficiently Tuning $\alpha$-Reachable Graphs for Nearest Neighbor Search

  2026cites this paper
• Filtered Approximate Nearest Neighbor Search in Vector Databases: System Design and Performance Analysis

  2026cites this paper
• GPU-Resident Inverted File Index for Streaming Vector Databases

  2026cites this paper
• Rethinking ANN-based Retrieval: Multifaceted Learnable Index for Large-scale Recommendation System

  2026cites this paper
• DeepInterestGR: Mining Deep Multi-Interest Using Multi-Modal LLMs for Generative Recommendation

  2026cites this paper
• Pancake: Hierarchical Memory System for Multi-Agent LLM Serving

  2026cites this paper
• AlayaLaser: Efficient Index Layout and Search Strategy for Large-scale High-dimensional Vector Similarity Search

  2026cites this paper
• HAVEN: High-Bandwidth Flash Augmented Vector Engine for Large-Scale Approximate Nearest-Neighbor Search Acceleration

  2026cites this paper
• Catapults to the Rescue: Accelerating Vector Search by Exploiting Query Locality

  2026cites this paper
• V3DB: Audit-on-Demand Zero-Knowledge Proofs for Verifiable Vector Search over Committed Snapshots

  2026influential citation
• Scalable mass-spectrometry-based molecular phylogeny with TreeMS2

  2026cites this paper
• CRISP: Correlation-Resilient Indexing via Subspace Partitioning

  2026cites this paper
• GPU-Native Approximate Nearest Neighbor Search with IVF-RaBitQ: Fast Index Build and Search

  2026influential citation
• AQR-HNSW: Accelerating Approximate Nearest Neighbor Search via Density-aware Quantization and Multi-stage Re-ranking

  2026influential citation
• pHNSW: PCA-Based Filtering to Accelerate HNSW Approximate Nearest Neighbor Search

  2026cites this paper
• Neighborhood Stability as a Measure of Nearest Neighbor Searchability

  2026cites this paper
• Efficient Approximate Nearest Neighbor Search under Multi-Attribute Range Filter

  2026cites this paper
• Fast Tuning the Index Construction Parameters of Proximity Graphs in Vector Databases

  2026cites this paper
• Hypersphere-Based Adaptive Filtration for Approximate Nearest Neighbor Search

  2026cites this paper
• Scaling Laws for Embedding Dimension in Information Retrieval

  2026cites this paper
• Multimodal Generative Recommendation for Fusing Semantic and Collaborative Signals

  2026cites this paper
• A High-Speed FPGA Implementation for IVF-PQ Index Construction

  2026cites this paper
• OdinANN: Direct Insert for Consistently Stable Performance in Billion-Scale Graph-Based Vector Search

  2026cites this paper
• Q-VESA: Accelerating Quantization-Aware Vector Search for Fast Retrieval in Prompt Engineering

  2026cites this paper
• LPPUBR: Lightweight Privacy-Preserving Unsupervised Medical Image Bitmap Retrieval in IoT

  2026cites this paper
• HyperJoin: LLM-augmented Hypergraph Link Prediction for Joinable Table Discovery

  2026cites this paper
• Vector Search for the Future: From Memory-Resident, Static Heterogeneous Storage, to Cloud-Native Architectures

  2026cites this paper
• MCGI: Manifold-Consistent Graph Indexing for Billion-Scale Disk-Resident Vector Search

  2026cites this paper
• ARGUS: Adaptive Rotation-Invariant Geometric Unsupervised System

  2026cites this paper
• GPU-Accelerated ANNS: Quantized for Speed, Built for Change

  2026cites this paper
• Predicting U3O8 powder processing conditions: An AI/ML approach analyzing deep learning embeddings of SEM micrographs

  2026cites this paper
• SpatCode: Rotary-based Unified Encoding Framework for Efficient Spatiotemporal Vector Retrieval

  2026cites this paper
• LLMs Meet Isolation Kernel: Lightweight, Learning-free Binary Embeddings for Fast Retrieval

  2026cites this paper
• An online chatter detection for milling based on a novel convolutional neural network and small probability hypothesis method

  2026cites this paper
• Reinforcement Learning-Based Resource Allocation for Multi-Task Multi-Codebook Semantic Communications

  2026cites this paper
• EffiPOI: A Product Quantization Framework Based on Knowledge Distillation for Efficient POI Recommendations

  2026cites this paper
• Correlation guided multi-teacher distillation for lightweight image retrieval

  2026cites this paper
• LEMUR: Learned Multi-Vector Retrieval

  2026cites this paper
• Hybrid Query of Boolean Filter and Vector Similarity Search: Benchmark, Comparison and Direction

  2025cites this paper
• BBQRec: Behavior-Bind Quantization for Multi-Modal Sequential Recommendation

  2025cites this paper
• DIGRA: A Dynamic Graph Indexing for Approximate Nearest Neighbor Search with Range Filter

  2025cites this paper
• Multi-Sense Embeddings for Language Models and Knowledge Distillation

  2025cites this paper
• Memory-Modular Classification: Learning to Generalize with Memory Replacement

  2025cites this paper
• dpBento: Benchmarking DPUs for Data Processing

  2025cites this paper
• Matryoshka Learning With Metric Transfer for Image-Text Matching

  2025cites this paper
• RaanA: A Fast, Flexible, and Data-Efficient Post-Training Quantization Algorithm

  2025cites this paper
• ESG: Elastic Graphs for Range-Filtering Approximate k-Nearest Neighbor Search

  2025cites this paper
• Bridging the Gap Between Continuous and Informative Discrete Representations by Random Product Quantization

  2025cites this paper
• Approximate nearest neighbor search by cyclic hierarchical product quantization

  2025influential citation
• Anomaly detection in pneumatic control valves using stacked re-optimized convolutional autoencoder and product quantization under imbalanced data conditions

  2025cites this paper
• MILLION: MasterIng Long-Context LLM Inference Via Outlier-Immunized KV Product QuaNtization

  2025cites this paper
• MicroNN: An On-device Disk-resident Updatable Vector Database

  2025cites this paper
• Efficient Dynamic Indexing for Range Filtered Approximate Nearest Neighbor Search

  2025cites this paper
• LLM-Assisted Proactive Threat Intelligence for Automated Reasoning

  2025cites this paper
• LIRA: A Learning-based Query-aware Partition Framework for Large-scale ANN Search

  2025cites this paper
• Cluster Tree for Nearest Neighbor Search

  2025cites this paper
• Groot: Graph-Centric Row Reordering with Tree for Sparse Matrix Multiplications on Tensor Cores

  2025cites this paper
• PilotANN: Memory-Bounded GPU Acceleration for Vector Search

  2025cites this paper
• Long-Tail Crisis in Nearest Neighbor Language Models

  2025influential citation