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: h25fea2e18ac23163
Venue: VLDB
Year: 2020
Pagerank: 8.4494625e-05
Overall Rank: 2,448 | 83.55%
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 19 of 19 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,957	SeRF: Segment Graph for Range-Filtering Approximate Nearest Neighbor Search	2024	SIGMOD	9.3159589e-05
2,060	Similarity search in the blink of an eye with compressed indices	2023	VLDB	9.0983169e-05
2,085	SingleStore-V: An Integrated Vector Database System in SingleStore	2024	VLDB	9.0709364e-05
4,498	PQCache: Product Quantization-based KVCache for Long Context LLM Inference	2025	SIGMOD	6.5762771e-05
5,238	Point-to-Hyperplane Nearest Neighbor Search Beyond the Unit Hypersphere	2021	SIGMOD	6.2169207e-05
6,560	RetroInfer: A Vector Storage Engine for Scalable Long-Context LLM Inference	2026	VLDB	5.7482184e-05
6,768	Dynamic Range-Filtering Approximate Nearest Neighbor Search	2025	VLDB	5.686858e-05
6,919	GTI: Graph-based Tree Index with Logarithm Updates for Nearest Neighbor Search in High-Dimensional Spaces	2025	VLDB	5.644237e-05
7,004	Accelerating Graph Indexing for ANNS on Modern CPUs	2025	SIGMOD	5.6238624e-05
8,400	TOD: GPU-accelerated Outlier Detection via Tensor Operations	2023	VLDB	5.3395906e-05
10,163	GPS: Revisiting the Data Layout for Disk-based High-Dimensional Vector Search	2026	SIGMOD	5.0682654e-05
10,425	CMANNS: GPU-Accelerated Graph Index Construction for ANNS via Compute-Memory Disaggregation	2026	SIGMOD	4.9793485e-05
10,677	RAIRS: Optimizing Redundant Assignment and List Layout for IVF-Based ANN Search	2026	SIGMOD	4.9793485e-05
10,709	Quantization Meets Projection: A Happy Marriage for Approximate k-Nearest Neighbor Search	2026	VLDB	4.9793485e-05
10,730	JHQ: Johnson-Lindenstrauss Enhanced Hierarchical Quantization for High-Dimensional Approximate Nearest Neighbor Search	2026	VLDB	4.9793485e-05
10,769	Harmonizing Efficiency and Accuracy in Filtered Vector Search	2026	VLDB	4.9793485e-05
11,048	Elastic Index Selection for Label-Hybrid AKNN Search	2026	VLDB	4.9793485e-05
11,065	DeXOR: Enabling xor in Decimal Space for Streaming Lossless Compression of Floating-point Data	2026	VLDB	4.9793485e-05
11,332	Not Small Enough? SegPQ: A Learned Approach to Compress Product Quantization Codebooks	2025	VLDB	4.9793485e-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.001992968
20	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00057568153
56	M-tree: An Efficient Access Method for Similarity Search in Metric Spaces	1997	VLDB	0.00040370171
74	Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph	2019	VLDB	0.00037091678
90	The X-tree: An Index Structure for High-Dimensional Data	1996	VLDB	0.00034860244
280	Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search	2007	VLDB	0.0002230467
298	Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search	2016	VLDB	0.00021833987
338	Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting	2012	SIGMOD	0.00020585187
562	SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index	2015	VLDB	0.00016335405
576	Quality and Efficiency in High Dimensional Nearest Neighbor Search	2009	SIGMOD	0.00016121388
650	HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces	2018	VLDB	0.00015149775
713	Cache locality is not enough: High-Performance Nearest Neighbor Search with Product Quantization Fast Scan	2016	VLDB	0.00014571977
1,095	A Data-adaptive and Dynamic Segmentation Index for Whole Matching on Time Series	2013	VLDB	0.00012050625
1,793	The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation	2000	VLDB	9.6235776e-05
2,730	Return of the Lernaean Hydra: Experimental Evaluation of Data Series Approximate Similarity Search	2020	VLDB	8.0861221e-05
2,872	The Lernaean Hydra of Data Series Similarity Search: An Experimental Evaluation of the State of the Art	2019	VLDB	7.9228762e-05

Semantically Similar Papers

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