Together is Better: Heavy Hitters Quantile Estimation

Summary: Per-ID quantile estimation in data streams, focusing on heavy hitters to avoid per-ID sketches. SQUAD—a hybrid sampling-sketching algorithm—bootstraps quantile sketches with background sampling to lower space, with theoretical guarantees and real-trace validation. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 6586
Venue: SIGMOD
Year: 2023
Pagerank: 4.5943269e-05
Overall Rank: 8,062 | 43.92%
DOI: 10.1145/3588937

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,113	SplineSketch: Even More Accurate Quantiles with Error Guarantees	2026	SIGMOD	4.1945683e-05
10,198	Quantile Estimation with Duplicates	2026	SIGMOD	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 13 of 13 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
126	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00044744986
275	Approximate Medians and other Quantiles in One Pass and with Limited Memory	1998	SIGMOD	0.00029364901
402	Mergeable Summaries	2012	PODS	0.00024196343
443	Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets	1999	SIGMOD	0.00022996573
848	Approximate Counts and Quantiles over Sliding Windows	2004	PODS	0.0001597308
1,566	Power-Conserving Computation of Order-Statistics over Sensor Networks	2004	PODS	0.00011343771
2,931	Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles	2005	SIGMOD	7.8697258e-05
2,955	Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams	2006	PODS	7.8239173e-05
4,334	Diamond in the Rough: Finding Hierarchical Heavy Hitters in Multi-Dimensional Data	2004	SIGMOD	6.2798179e-05
4,966	Relative Error Streaming Quantiles	2021	PODS	5.7959749e-05
5,457	Fast and Approximate Stream Mining of Quantiles and Frequencies Using Graphics Processors	2005	SIGMOD	5.4970777e-05
5,956	A Tight Lower Bound for Comparison-Based Quantile Summaries	2020	PODS	5.2566971e-05
6,495	Sampling Based Algorithms for Quantile Computation in Sensor Networks	2011	SIGMOD	5.0413486e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
9,237	Determining Exact Quantiles with Randomized Summaries	2024	SIGMOD	4.3690661e-05
8,130	Simple & Optimal Quantile Sketch: Combining Greenwald-Khanna with Khanna-Greenwald	2024	PODS	4.5784634e-05
2,931	Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles	2005	SIGMOD	7.8697258e-05
11,371	Efficient and Error-bounded Spatiotemporal Quantile Monitoring in Edge Computing Environments	2022	VLDB	4.1945683e-05
4,966	Relative Error Streaming Quantiles	2021	PODS	5.7959749e-05
4,076	Quantiles over Data Streams: An Experimental Study	2013	SIGMOD	6.4680854e-05
4,249	Optimal Tracking of Distributed Heavy Hitters and Quantiles	2009	PODS	6.3245666e-05
10,198	Quantile Estimation with Duplicates	2026	SIGMOD	4.1945683e-05
2,955	Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams	2006	PODS	7.8239173e-05
9,162	Estimating Quantiles from the Union of Historical and Streaming Data	2017	VLDB	4.3849295e-05