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: 11322
Venue: VLDB
Year: 2016
Pagerank: 0.00013023834
Overall Rank: 1,252 | 91.31%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 38 of 38 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
210	Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph	2019	VLDB	0.00034086264
494	Milvus: A Purpose-Built Vector Data Management System	2021	SIGMOD	0.00021769407
2,264	Manu: A Cloud Native Vector Database Management System	2022	VLDB	9.1587362e-05
2,287	RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search	2024	SIGMOD	9.1004806e-05
2,692	Starling: An I/O-Efficient Disk-Resident Graph Index Framework for High-Dimensional Vector Similarity Search on Data Segment	2024	SIGMOD	8.2857267e-05
3,182	DeltaPQ: Lossless Product Quantization Code Compression for High Dimensional Similarity Search	2020	VLDB	7.4280768e-05
3,541	Similarity search in the blink of an eye with compressed indices	2023	VLDB	6.9910982e-05
3,552	SeRF: Segment Graph for Range-Filtering Approximate Nearest Neighbor Search	2024	SIGMOD	6.9765275e-05
4,551	iRangeGraph: Improvising Range-dedicated Graphs for Range-filtering Nearest Neighbor Search	2024	SIGMOD	6.0864316e-05
4,600	Practical and Asymptotically Optimal Quantization of High-Dimensional Vectors in Euclidean Space for Approximate Nearest Neighbor Search	2025	SIGMOD	6.0528015e-05
5,186	SymphonyQG: Towards Symphonious Integration of Quantization and Graph for Approximate Nearest Neighbor Search	2025	SIGMOD	5.6352814e-05
6,350	PQCache: Product Quantization-based KVCache for Long Context LLM Inference	2025	SIGMOD	5.0957601e-05
6,970	AquaPipe: A Quality-Aware Pipeline for Knowledge Retrieval and Large Language Models	2025	SIGMOD	4.8740302e-05
7,198	ARKGraph: All-Range Approximate K-Nearest-Neighbor Graph	2023	VLDB	4.79852e-05
7,612	UNIFY: Unified Index for Range Filtered Approximate Nearest Neighbors Search	2025	VLDB	4.6919232e-05
8,161	TOD: GPU-accelerated Outlier Detection via Tensor Operations	2023	VLDB	4.5688249e-05
8,208	VSAG: An Optimized Search Framework for Graph-based Approximate Nearest Neighbor Search	2025	VLDB	4.5537353e-05
8,418	DIGRA: A Dynamic Graph Indexing for Approximate Nearest Neighbor Search with Range Filter	2025	SIGMOD	4.5119865e-05
8,419	Efficient Dynamic Indexing for Range Filtered Approximate Nearest Neighbor Search	2025	SIGMOD	4.5119865e-05
8,430	Accelerating Graph Indexing for ANNS on Modern CPUs	2025	SIGMOD	4.508568e-05
8,643	Accelerating Product Quantization Query Execution Runtime	2021	SIGMOD	4.4730679e-05
8,654	Dynamic Range-Filtering Approximate Nearest Neighbor Search	2025	VLDB	4.4694763e-05
8,709	ANN Softmax: Acceleration of Extreme Classification Training	2022	VLDB	4.4584416e-05
10,042	Accelerating High-Dimensional ANN Search via Skipping Redundant Distance Computations	2026	SIGMOD	4.1905499e-05
10,071	Dynamically Detect and Fix Hardness for Efficient Approximate Nearest Neighbor Search	2026	SIGMOD	4.1905499e-05
10,110	SAQ: Pushing the Limits of Vector Quantization through Code Adjustment and Dimension Segmentation	2026	SIGMOD	4.1905499e-05
10,111	Scalable Graph Indexing using GPUs for Approximate Nearest Neighbor Search	2026	SIGMOD	4.1905499e-05
10,124	TRIM: Accelerating High-Dimensional Vector Similarity Search with Enhanced Triangle-Inequality-Based Pruning	2026	SIGMOD	4.1905499e-05
10,129	WoW: A Window-to-Window Incremental Index for Range-Filtering Approximate Nearest Neighbor Search	2026	SIGMOD	4.1905499e-05
10,146	CANDOR-Bench: Benchmarking In-Memory Continuous ANNS under Dynamic Open-World Streams [Experiments & Analysis]	2026	SIGMOD	4.1905499e-05
10,154	Distribution-Aware Exploration for Adaptive HNSW Search	2026	SIGMOD	4.1905499e-05
10,201	RAIRS: Optimizing Redundant Assignment and List Layout for IVF-Based ANN Search	2026	SIGMOD	4.1905499e-05
10,237	Quantization Meets Projection: A Happy Marriage for Approximate k-Nearest Neighbor Search	2026	VLDB	4.1905499e-05
10,275	Balancing the Blend: An Experimental Analysis of Trade-offs in Hybrid Search	2026	VLDB	4.1905499e-05
10,315	Elastic Index Selection for Label-Hybrid AKNN Search	2026	VLDB	4.1905499e-05
10,662	HAKES: Scalable Vector Database for Embedding Search Service	2025	VLDB	4.1905499e-05
10,706	Not Small Enough? SegPQ: A Learned Approach to Compress Product Quantization Codebooks	2025	VLDB	4.1905499e-05
10,711	Fast Graph Vector Search via Hardware Acceleration and Delayed-Synchronization Traversal	2025	VLDB	4.1905499e-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
20	C-Store: A Column-oriented DBMS	2005	VLDB	0.00086163998
34	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00076824554
35	MonetDB/X100: Hyper-Pipelining Query Execution	2005	CIDR	0.00076209479
132	Integrating Compression and Execution in Column-Oriented Database Systems	2006	SIGMOD	0.00043697853
350	Sort vs. Hash Revisited: Fast Join Implementation on Modern Multi-Core CPUs	2009	VLDB	0.00026368305
403	Multi-Core, Main-Memory Joins: Sort vs. Hash Revisited	2014	VLDB	0.00024176677
579	Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting	2012	SIGMOD	0.0001982328
858	SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index	2015	VLDB	0.00015833075
944	Efficient Implementation of Sorting on Multi-Core SIMD CPU Architecture	2008	VLDB	0.0001512998
1,225	SK-LSH : An Efficient Index Structure for Approximate Nearest Neighbor Search	2014	VLDB	0.00013182109

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
8,419	Efficient Dynamic Indexing for Range Filtered Approximate Nearest Neighbor Search	2025	SIGMOD	4.5119865e-05
675	Quality and Efficiency in High Dimensional Nearest Neighbor Search	2009	SIGMOD	0.00018304179
4,600	Practical and Asymptotically Optimal Quantization of High-Dimensional Vectors in Euclidean Space for Approximate Nearest Neighbor Search	2025	SIGMOD	6.0528015e-05
3,574	Efficient k-NN Search on Vertically Decomposed Data	2002	SIGMOD	6.9520978e-05
10,237	Quantization Meets Projection: A Happy Marriage for Approximate k-Nearest Neighbor Search	2026	VLDB	4.1905499e-05
5,889	Improving Adaptable Similarity Query Processing by Using Approximations	1998	VLDB	5.2842168e-05
3,062	Contrast Plots and P-Sphere Trees: Space vs. Time in Nearest Neighbor Searches	2000	VLDB	7.6348035e-05
3,541	Similarity search in the blink of an eye with compressed indices	2023	VLDB	6.9910982e-05
3,549	Fast Parallel Similarity Search in Multimedia Databases	1997	SIGMOD	6.9792126e-05
8,643	Accelerating Product Quantization Query Execution Runtime	2021	SIGMOD	4.4730679e-05