Quantile Estimation with Duplicates

Summary: DupliSketch: a quantile sketch explicitly optimized for duplicate-heavy streams, compressing arrival duplicates and using randomized compaction plus separate tracking of frequent values. Provides rank-error/space/time guarantees under duplicates and beats KLL-style baselines (avg. 44% lower error), with an IoTDB UDF deployment. (summarized by gpt-5-mini on Apr 11 2026)

Paper ID: 7700
Venue: SIGMOD
Year: 2026
Pagerank: 5.093636e-05
Overall Rank: 10,487 | 28.05%
DOI: 10.1145/3786683

Incoming Non-self Citations Over Time

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

Authors

1. Tianrui Xia (Tsinghua University)
2. Ziling Chen (Tsinghua University)
3. Shaoxu Song (Tsinghua University)

BibTeX Citation

@inproceedings{xia_sigmod26,
        title = {{Quantile Estimation with Duplicates}},
        author = {Xia, Tianrui and Chen, Ziling and Song, Shaoxu},
        series = {{SIGMOD} '26},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3786683},
        url = {https://dl.acm.org/doi/10.1145/3786683},
        year = {2026}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

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
106	The MADlib Analytics Library or MAD Skills, the SQL	2012	VLDB	0.00033539462
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
691	Approximate Counts and Quantiles over Sliding Windows	2004	PODS	0.00014927798
2,455	DDSketch: A Fast and Fully-Mergeable Quantile Sketch with Relative-Error Guarantees	2019	VLDB	8.5552968e-05
4,472	Relative Error Streaming Quantiles	2021	PODS	6.6810874e-05
5,184	KLL± Approximate Quantile Sketches over Dynamic Datasets	2021	VLDB	6.3283918e-05
5,599	A Tight Lower Bound for Comparison-Based Quantile Summaries	2020	PODS	6.154479e-05
8,005	Together is Better: Heavy Hitters Quantile Estimation	2023	SIGMOD	5.5080221e-05
8,106	SpaceSaving±: An Optimal Algorithm for Frequency Estimation and Frequent Items in the Bounded-Deletion Model	2022	VLDB	5.4853605e-05
11,703	Approximating Median Absolute Deviation with Bounded Error	2021	VLDB	5.093636e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,618	SplineSketch: Even More Accurate Quantiles with Error Guarantees	2026	SIGMOD
2	7,091	Simple & Optimal Quantile Sketch: Combining Greenwald-Khanna with Khanna-Greenwald	2024	PODS
3	2,747	Moment-Based Quantile Sketches for Efficient High Cardinality Aggregation Queries	2018	VLDB
4	3,765	Quantiles over Data Streams: An Experimental Study	2013	SIGMOD
5	8,005	Together is Better: Heavy Hitters Quantile Estimation	2023	SIGMOD
6	4,472	Relative Error Streaming Quantiles	2021	PODS
7	9,318	Estimating Quantiles from the Union of Historical and Streaming Data	2017	VLDB
8	5,184	KLL± Approximate Quantile Sketches over Dynamic Datasets	2021	VLDB
9	10,675	Randomized Sketches for Quantile in LSM-tree based Store	2025	SIGMOD
10	9,386	Determining Exact Quantiles with Randomized Summaries	2024	SIGMOD