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

Summary: PQ Fast Scan converts cache-resident PQ tables into SIMD-sized in-register tables for fast in-register lookups. Maintains exact PQ accuracy with 4–6× speedup (25M vectors: 74 ms→13 ms), addressing cache-latency limits in high-dimensional NN search. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 11321
Venue: VLDB
Year: 2016
Pagerank: 0.00012930432
Overall Rank: 1,269 | 91.18%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 37 of 37 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
212	Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph	2019	VLDB	0.00033913475
495	Milvus: A Purpose-Built Vector Data Management System	2021	SIGMOD	0.00021767688
2,262	Manu: A Cloud Native Vector Database Management System	2022	VLDB	9.1624446e-05
2,324	RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search	2024	SIGMOD	9.0326444e-05
2,690	Starling: An I/O-Efficient Disk-Resident Graph Index Framework for High-Dimensional Vector Similarity Search on Data Segment	2024	SIGMOD	8.293714e-05
3,225	DeltaPQ: Lossless Product Quantization Code Compression for High Dimensional Similarity Search	2020	VLDB	7.3463484e-05
3,609	Similarity search in the blink of an eye with compressed indices	2023	VLDB	6.9215236e-05
3,624	SeRF: Segment Graph for Range-Filtering Approximate Nearest Neighbor Search	2024	SIGMOD	6.9056e-05
4,551	iRangeGraph: Improvising Range-dedicated Graphs for Range-filtering Nearest Neighbor Search	2024	SIGMOD	6.092287e-05
4,598	Practical and Asymptotically Optimal Quantization of High-Dimensional Vectors in Euclidean Space for Approximate Nearest Neighbor Search	2025	SIGMOD	6.0586236e-05
5,184	SymphonyQG: Towards Symphonious Integration of Quantization and Graph for Approximate Nearest Neighbor Search	2025	SIGMOD	5.6406991e-05
6,357	PQCache: Product Quantization-based KVCache for Long Context LLM Inference	2025	SIGMOD	5.0970739e-05
7,193	AquaPipe: A Quality-Aware Pipeline for Knowledge Retrieval and Large Language Models	2025	SIGMOD	4.8039257e-05
7,204	ARKGraph: All-Range Approximate K-Nearest-Neighbor Graph	2023	VLDB	4.8015761e-05
7,611	UNIFY: Unified Index for Range Filtered Approximate Nearest Neighbors Search	2025	VLDB	4.6964271e-05
8,157	TOD: GPU-accelerated Outlier Detection via Tensor Operations	2023	VLDB	4.5730908e-05
8,209	VSAG: An Optimized Search Framework for Graph-based Approximate Nearest Neighbor Search	2025	VLDB	4.5581054e-05
8,424	DIGRA: A Dynamic Graph Indexing for Approximate Nearest Neighbor Search with Range Filter	2025	SIGMOD	4.5163161e-05
8,425	Efficient Dynamic Indexing for Range Filtered Approximate Nearest Neighbor Search	2025	SIGMOD	4.5163161e-05
8,439	Accelerating Graph Indexing for ANNS on Modern CPUs	2025	SIGMOD	4.5128946e-05
8,646	Accelerating Product Quantization Query Execution Runtime	2021	SIGMOD	4.477163e-05
8,656	Dynamic Range-Filtering Approximate Nearest Neighbor Search	2025	VLDB	4.4737647e-05
8,712	ANN Softmax: Acceleration of Extreme Classification Training	2022	VLDB	4.4626362e-05
10,042	Accelerating High-Dimensional ANN Search via Skipping Redundant Distance Computations	2026	SIGMOD	4.1945683e-05
10,071	Dynamically Detect and Fix Hardness for Efficient Approximate Nearest Neighbor Search	2026	SIGMOD	4.1945683e-05
10,110	SAQ: Pushing the Limits of Vector Quantization through Code Adjustment and Dimension Segmentation	2026	SIGMOD	4.1945683e-05
10,111	Scalable Graph Indexing using GPUs for Approximate Nearest Neighbor Search	2026	SIGMOD	4.1945683e-05
10,124	TRIM: Accelerating High-Dimensional Vector Similarity Search with Enhanced Triangle-Inequality-Based Pruning	2026	SIGMOD	4.1945683e-05
10,129	WoW: A Window-to-Window Incremental Index for Range-Filtering Approximate Nearest Neighbor Search	2026	SIGMOD	4.1945683e-05
10,146	CANDOR-Bench: Benchmarking In-Memory Continuous ANNS under Dynamic Open-World Streams [Experiments & Analysis]	2026	SIGMOD	4.1945683e-05
10,154	Distribution-Aware Exploration for Adaptive HNSW Search	2026	SIGMOD	4.1945683e-05
10,201	RAIRS: Optimizing Redundant Assignment and List Layout for IVF-Based ANN Search	2026	SIGMOD	4.1945683e-05
10,237	Quantization Meets Projection: A Happy Marriage for Approximate k-Nearest Neighbor Search	2026	VLDB	4.1945683e-05
10,303	Elastic Index Selection for Label-Hybrid AKNN Search	2026	VLDB	4.1945683e-05
10,654	HAKES: Scalable Vector Database for Embedding Search Service	2025	VLDB	4.1945683e-05
10,698	Not Small Enough? SegPQ: A Learned Approach to Compress Product Quantization Codebooks	2025	VLDB	4.1945683e-05
10,703	Fast Graph Vector Search via Hardware Acceleration and Delayed-Synchronization Traversal	2025	VLDB	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
21	C-Store: A Column-oriented DBMS	2005	VLDB	0.00086087497
34	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00076637636
35	MonetDB/X100: Hyper-Pipelining Query Execution	2005	CIDR	0.00076197749
131	Integrating Compression and Execution in Column-Oriented Database Systems	2006	SIGMOD	0.0004370331
351	Sort vs. Hash Revisited: Fast Join Implementation on Modern Multi-Core CPUs	2009	VLDB	0.0002636504
404	Multi-Core, Main-Memory Joins: Sort vs. Hash Revisited	2014	VLDB	0.00024143076
605	Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting	2012	SIGMOD	0.000193396
867	SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index	2015	VLDB	0.00015792021
946	Efficient Implementation of Sorting on Multi-Core SIMD CPU Architecture	2008	VLDB	0.0001513324
1,229	SK-LSH : An Efficient Index Structure for Approximate Nearest Neighbor Search	2014	VLDB	0.00013157271

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
8,425	Efficient Dynamic Indexing for Range Filtered Approximate Nearest Neighbor Search	2025	SIGMOD	4.5163161e-05
682	Quality and Efficiency in High Dimensional Nearest Neighbor Search	2009	SIGMOD	0.00018201541
4,598	Practical and Asymptotically Optimal Quantization of High-Dimensional Vectors in Euclidean Space for Approximate Nearest Neighbor Search	2025	SIGMOD	6.0586236e-05
3,579	Efficient k-NN Search on Vertically Decomposed Data	2002	SIGMOD	6.9502303e-05
10,237	Quantization Meets Projection: A Happy Marriage for Approximate k-Nearest Neighbor Search	2026	VLDB	4.1945683e-05
5,882	Improving Adaptable Similarity Query Processing by Using Approximations	1998	VLDB	5.2892937e-05
3,061	Contrast Plots and P-Sphere Trees: Space vs. Time in Nearest Neighbor Searches	2000	VLDB	7.6382127e-05
3,609	Similarity search in the blink of an eye with compressed indices	2023	VLDB	6.9215236e-05
3,555	Fast Parallel Similarity Search in Multimedia Databases	1997	SIGMOD	6.9772546e-05
8,646	Accelerating Product Quantization Query Execution Runtime	2021	SIGMOD	4.477163e-05