SplineSketch: Even More Accurate Quantiles with Error Guarantees

Summary: Introduces SplineSketch, a streaming quantile sketch for numeric data that maintains a dynamic subdivision of the value range and fits a monotone cubic spline to the empirical distribution for much tighter interpolation. Achieves near‑optimal uniformly bounded rank-error guarantees while empirically beating t‑digest by 2–20×. (summarized by gpt-5-mini on Feb 11 2026)

Paper ID: 7613
Venue: SIGMOD
Year: 2026
Pagerank: 5.2434488e-05
Overall Rank: 9,618 | 34.02%
DOI: 10.1145/3769827

Incoming Non-self Citations Over Time

Authors

1. Aleksander Łukasiewicz (Charles University)
2. Jakub Tětek (INSAIT; Sofia University St. Kliment Ohridski)
3. Pavel Veselý (Charles University)

BibTeX Citation

@inproceedings{ukasiewicz_sigmod26,
        title = {{SplineSketch: Even More Accurate Quantiles with Error Guarantees}},
        author = {Łukasiewicz, Aleksander and Tětek, Jakub and Veselý, Pavel},
        series = {{SIGMOD} '26},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3769827},
        url = {https://dl.acm.org/doi/10.1145/3769827},
        year = {2026}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,295	Sublime: Sublinear Error & Space for Unbounded Skewed Streams	2026	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
82	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00036378991
443	Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets	1999	SIGMOD	0.00018373044
451	Mergeable Summaries	2012	PODS	0.00018151445
847	Benchmarking Learned Indexes	2021	VLDB	0.0001365768
2,455	DDSketch: A Fast and Fully-Mergeable Quantile Sketch with Relative-Error Guarantees	2019	VLDB	8.5552968e-05
2,716	Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams	2006	PODS	8.2108958e-05
2,747	Moment-Based Quantile Sketches for Efficient High Cardinality Aggregation Queries	2018	VLDB	8.1711208e-05
4,472	Relative Error Streaming Quantiles	2021	PODS	6.6810874e-05
5,599	A Tight Lower Bound for Comparison-Based Quantile Summaries	2020	PODS	6.154479e-05
5,693	Exploiting Ordered Dictionaries to Efficiently Construct Histograms with Q-Error Guarantees in SAP HANA	2014	SIGMOD	6.1189424e-05
7,091	Simple & Optimal Quantile Sketch: Combining Greenwald-Khanna with Khanna-Greenwald	2024	PODS	5.7062634e-05
8,005	Together is Better: Heavy Hitters Quantile Estimation	2023	SIGMOD	5.5080221e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	783	A One-Pass Algorithm for Accurately Estimating Quantiles for Disk-Resident Data	1997	VLDB
2	82	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD
3	9,318	Estimating Quantiles from the Union of Historical and Streaming Data	2017	VLDB
4	10,487	Quantile Estimation with Duplicates	2026	SIGMOD
5	5,184	KLL± Approximate Quantile Sketches over Dynamic Datasets	2021	VLDB
6	9,386	Determining Exact Quantiles with Randomized Summaries	2024	SIGMOD
7	4,472	Relative Error Streaming Quantiles	2021	PODS
8	3,765	Quantiles over Data Streams: An Experimental Study	2013	SIGMOD
9	2,455	DDSketch: A Fast and Fully-Mergeable Quantile Sketch with Relative-Error Guarantees	2019	VLDB
10	7,091	Simple & Optimal Quantile Sketch: Combining Greenwald-Khanna with Khanna-Greenwald	2024	PODS