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: h243ab67cf5d20833
Venue: SIGMOD
Year: 2023
Pagerank: 5.5160692e-05
Overall Rank: 7,415 | 50.30%
DOI: 10.1145/3588937

Incoming Non-self Citations Over Time

Authors

1. Rana Shahout (Technion)
2. Roy Friedman (Technion)
3. Ran Ben Basat (University College London)

BibTeX Citation

@inproceedings{shahout_sigmod23,
        title = {{Together is Better: Heavy Hitters Quantile Estimation}},
        author = {Shahout, Rana and Friedman, Roy and Basat, Ran Ben},
        series = {{SIGMOD} '23},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3588937},
        url = {https://dl.acm.org/doi/10.1145/3588937},
        year = {2023}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,837	SplineSketch: Even More Accurate Quantiles with Error Guarantees	2026	SIGMOD	5.2523304e-05
10,403	Near-Optimal Per-Key Streaming Quantile Estimation	2027	SIGMOD	4.9605343e-05
10,746	Quantile Estimation with Duplicates	2026	SIGMOD	4.9605343e-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
82	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00036097627
252	Approximate Medians and other Quantiles in One Pass and with Limited Memory	1998	SIGMOD	0.00023058622
442	Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets	1999	SIGMOD	0.00018182341
452	Mergeable Summaries	2012	PODS	0.00018032092
713	Approximate Counts and Quantiles over Sliding Windows	2004	PODS	0.00014582248
1,438	Power-Conserving Computation of Order-Statistics over Sensor Networks	2004	PODS	0.00010647197
2,472	Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles	2005	SIGMOD	8.3988741e-05
2,738	Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams	2006	PODS	8.0599809e-05
4,279	Relative Error Streaming Quantiles	2021	PODS	6.6731371e-05
4,353	Diamond in the Rough: Finding Hierarchical Heavy Hitters in Multi-Dimensional Data	2004	SIGMOD	6.6322269e-05
4,975	A Tight Lower Bound for Comparison-Based Quantile Summaries	2020	PODS	6.3194701e-05
5,336	Fast and Approximate Stream Mining of Quantiles and Frequencies Using Graphics Processors	2005	SIGMOD	6.1613661e-05
6,310	Sampling Based Algorithms for Quantile Computation in Sensor Networks	2011	SIGMOD	5.7992155e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,637	Simple & Optimal Quantile Sketch: Combining Greenwald-Khanna with Khanna-Greenwald	2024	PODS
2	2,472	Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles	2005	SIGMOD
3	11,928	Efficient and Error-bounded Spatiotemporal Quantile Monitoring in Edge Computing Environments	2022	VLDB
4	4,279	Relative Error Streaming Quantiles	2021	PODS
5	3,667	Quantiles over Data Streams: An Experimental Study	2013	SIGMOD
6	10,403	Near-Optimal Per-Key Streaming Quantile Estimation	2027	SIGMOD
7	3,932	Optimal Tracking of Distributed Heavy Hitters and Quantiles	2009	PODS
8	10,746	Quantile Estimation with Duplicates	2026	SIGMOD
9	2,738	Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams	2006	PODS
10	9,481	Estimating Quantiles from the Union of Historical and Streaming Data	2017	VLDB