Not Small Enough? SegPQ: A Learned Approach to Compress Product Quantization Codebooks

Summary: SegPQ presents a lossless learned compression for PQ codebooks using an error-bounded piecewise-linear approximation plus low-bit residuals, with a theoretical bound of 1.721+ceil(log2 epsilon_OPT) bits per codeword. SIMD-aware query routines yield up to 4.7× codebook reduction on billion-scale vectors with ~3.3% query overhead. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 13996
Venue: VLDB
Year: 2025
Pagerank: 4.1945683e-05
Overall Rank: 10,698 | 25.58%
DOI: 10.14778/3749646.3749650

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
102	The Case for Learned Index Structures	2018	SIGMOD	0.00049545203
575	Distance-Based Indexing For High-Dimensional Metric Spaces	1997	SIGMOD	0.00019882723
826	ALEX: An Updatable Adaptive Learned Index	2020	SIGMOD	0.00016224841
857	The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds	2020	VLDB	0.00015882892
1,269	Cache locality is not enough: High-Performance Nearest Neighbor Search with Product Quantization Fast Scan	2016	VLDB	0.00012930432
2,613	Decomposed Bounded Floats for Fast Compression and Queries	2021	VLDB	8.4503824e-05
3,225	DeltaPQ: Lossless Product Quantization Code Compression for High Dimensional Similarity Search	2020	VLDB	7.3463484e-05
4,446	Stable Learned Bloom Filters for Data Streams	2020	VLDB	6.1800659e-05
5,314	Can Learned Models Replace Hash Functions?	2023	VLDB	5.5724608e-05
8,650	HAP: An Efficient Hamming Space Index Based on Augmented Pigeonhole Principle	2022	SIGMOD	4.4761716e-05
9,746	Why Are Learned Indexes So Effective but Sometimes Ineffective?	2025	VLDB	4.2897489e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
10,260	JHQ: Johnson-Lindenstrauss Enhanced Hierarchical Quantization for High-Dimensional Approximate Nearest Neighbor Search	2026	VLDB	4.1945683e-05
8,485	Maximum Inner Product is Query-Scaled Nearest Neighbor	2025	VLDB	4.4999394e-05
8,646	Accelerating Product Quantization Query Execution Runtime	2021	SIGMOD	4.477163e-05
9,408	Experimental Analysis of Large-scale Learnable Vector Storage Compression	2024	VLDB	4.3441378e-05
2,324	RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search	2024	SIGMOD	9.0326444e-05
10,237	Quantization Meets Projection: A Happy Marriage for Approximate k-Nearest Neighbor Search	2026	VLDB	4.1945683e-05
3,609	Similarity search in the blink of an eye with compressed indices	2023	VLDB	6.9215236e-05
10,110	SAQ: Pushing the Limits of Vector Quantization through Code Adjustment and Dimension Segmentation	2026	SIGMOD	4.1945683e-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
3,225	DeltaPQ: Lossless Product Quantization Code Compression for High Dimensional Similarity Search	2020	VLDB	7.3463484e-05