DeltaPQ: Lossless Product Quantization Code Compression for High Dimensional Similarity Search

Summary: Compresses high-dimensional vectors by first quantizing into codes and then applying a tree-based delta encoding (DeltaPQ) to those codes. A linear-time algorithm selects the optimal tree, yielding up to 5× compression and enabling approximate nearest neighbor search directly on the compressed data across inner product, cosine, Euclidean, and Lp norms. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 12428
Venue: VLDB
Year: 2020
Pagerank: 8.4027322e-05
Overall Rank: 2,572 | 82.36%
DOI: 10.14778/3424573.3424580

Incoming Non-self Citations Over Time

Authors

1. Runhui Wang (Rutgers University)
2. Dong Deng (Rutgers University)

BibTeX Citation

@article{wang_vldb20,
        title = {{DeltaPQ: Lossless Product Quantization Code Compression for High Dimensional Similarity Search}},
        author = {Wang, Runhui and Deng, Dong},
        journal = {PVLDB},
        series = {{VLDB} '20},
        volume = {13},
        number = {13},
        pages = {3603--3616},
        doi = {10.14778/3424573.3424580},
        url = {https://doi.org/10.14778/3424573.3424580},
        year = {2020}
}

Incoming Citations (Sorted by Pagerank)

Showing 18 of 18 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,303	SeRF: Segment Graph for Range-Filtering Approximate Nearest Neighbor Search	2024	SIGMOD	8.7783079e-05
2,519	Similarity search in the blink of an eye with compressed indices	2023	VLDB	8.4741476e-05
2,920	SingleStore-V: An Integrated Vector Database System in SingleStore	2024	VLDB	7.9628307e-05
4,430	PQCache: Product Quantization-based KVCache for Long Context LLM Inference	2025	SIGMOD	6.7091071e-05
5,121	Point-to-Hyperplane Nearest Neighbor Search Beyond the Unit Hypersphere	2021	SIGMOD	6.3577317e-05
6,432	RetroInfer: A Vector Storage Engine for Scalable Long-Context LLM Inference	2026	VLDB	5.8801533e-05
7,124	GTI: Graph-based Tree Index with Logarithm Updates for Nearest Neighbor Search in High-Dimensional Spaces	2025	VLDB	5.6961208e-05
7,166	Accelerating Graph Indexing for ANNS on Modern CPUs	2025	SIGMOD	5.6846045e-05
7,426	Dynamic Range-Filtering Approximate Nearest Neighbor Search	2025	VLDB	5.6211019e-05
8,230	TOD: GPU-accelerated Outlier Detection via Tensor Operations	2023	VLDB	5.4619615e-05
10,209	CMANNS: GPU-Accelerated Graph Index Construction for ANNS via Compute-Memory Disaggregation	2026	SIGMOD	5.093636e-05
10,251	GPS: Revisiting the Data Layout for Disk-based High-Dimensional Vector Search	2026	SIGMOD	5.093636e-05
10,490	RAIRS: Optimizing Redundant Assignment and List Layout for IVF-Based ANN Search	2026	SIGMOD	5.093636e-05
10,525	Quantization Meets Projection: A Happy Marriage for Approximate k-Nearest Neighbor Search	2026	VLDB	5.093636e-05
10,548	JHQ: Johnson-Lindenstrauss Enhanced Hierarchical Quantization for High-Dimensional Approximate Nearest Neighbor Search	2026	VLDB	5.093636e-05
10,601	Elastic Index Selection for Label-Hybrid AKNN Search	2026	VLDB	5.093636e-05
10,619	DeXOR: Enabling xor in Decimal Space for Streaming Lossless Compression of Floating-point Data	2026	VLDB	5.093636e-05
10,944	Not Small Enough? SegPQ: A Learned Approach to Compress Product Quantization Codebooks	2025	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 16 of 16 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
2	R-Trees: A Dynamic Index Structure For Spatial Searching	1984	SIGMOD	0.0020210012
21	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00056760516
56	M-tree: An Efficient Access Method for Similarity Search in Metric Spaces	1997	VLDB	0.00040719947
85	The X-tree: An Index Structure for High-Dimensional Data	1996	VLDB	0.00035405879
93	Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph	2019	VLDB	0.00034701237
287	Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search	2007	VLDB	0.00022323585
332	Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search	2016	VLDB	0.00020920444
369	Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting	2012	SIGMOD	0.00019945234
580	SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index	2015	VLDB	0.00016157635
581	Quality and Efficiency in High Dimensional Nearest Neighbor Search	2009	SIGMOD	0.00016153395
705	HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces	2018	VLDB	0.00014829964
805	Cache locality is not enough: High-Performance Nearest Neighbor Search with Product Quantization Fast Scan	2016	VLDB	0.00013891999
1,084	A Data-adaptive and Dynamic Segmentation Index for Whole Matching on Time Series	2013	VLDB	0.00012256753
1,778	The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation	2000	VLDB	9.7769047e-05
2,734	Return of the Lernaean Hydra: Experimental Evaluation of Data Series Approximate Similarity Search	2020	VLDB	8.190416e-05
3,037	The Lernaean Hydra of Data Series Similarity Search: An Experimental Evaluation of the State of the Art	2019	VLDB	7.8275859e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	21	Similarity Search in High Dimensions via Hashing	1999	VLDB
2	10,548	JHQ: Johnson-Lindenstrauss Enhanced Hierarchical Quantization for High-Dimensional Approximate Nearest Neighbor Search	2026	VLDB
3	6,093	High-Dimensional Vector Similarity Search: From Time Series to Deep Network Embeddings	2020	SIGMOD
4	46	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB
5	8,655	A Non-Linear Dimensionality-Reduction Technique for Fast Similarity Search in Large Databases	2006	SIGMOD
6	10,525	Quantization Meets Projection: A Happy Marriage for Approximate k-Nearest Neighbor Search	2026	VLDB
7	3,108	Practical and Asymptotically Optimal Quantization of High-Dimensional Vectors in Euclidean Space for Approximate Nearest Neighbor Search	2025	SIGMOD
8	8,765	Contorting High Dimensional Data for Efficient Main Memory KNN Processing	2003	SIGMOD
9	10,944	Not Small Enough? SegPQ: A Learned Approach to Compress Product Quantization Codebooks	2025	VLDB
10	2,519	Similarity search in the blink of an eye with compressed indices	2023	VLDB