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: 6648
Venue: SIGMOD
Year: 2023
Pagerank: 5.5080221e-05
Overall Rank: 8,005 | 45.08%
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 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,618	SplineSketch: Even More Accurate Quantiles with Error Guarantees	2026	SIGMOD	5.2434488e-05
10,487	Quantile Estimation with Duplicates	2026	SIGMOD	5.093636e-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.00036378991
261	Approximate Medians and other Quantiles in One Pass and with Limited Memory	1998	SIGMOD	0.00023097188
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
1,400	Power-Conserving Computation of Order-Statistics over Sensor Networks	2004	PODS	0.00010890603
2,406	Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles	2005	SIGMOD	8.6187297e-05
2,716	Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams	2006	PODS	8.2108958e-05
4,258	Diamond in the Rough: Finding Hierarchical Heavy Hitters in Multi-Dimensional Data	2004	SIGMOD	6.7994155e-05
4,472	Relative Error Streaming Quantiles	2021	PODS	6.6810874e-05
5,216	Fast and Approximate Stream Mining of Quantiles and Frequencies Using Graphics Processors	2005	SIGMOD	6.3121293e-05
5,599	A Tight Lower Bound for Comparison-Based Quantile Summaries	2020	PODS	6.154479e-05
6,178	Sampling Based Algorithms for Quantile Computation in Sensor Networks	2011	SIGMOD	5.949619e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,386	Determining Exact Quantiles with Randomized Summaries	2024	SIGMOD
2	7,091	Simple & Optimal Quantile Sketch: Combining Greenwald-Khanna with Khanna-Greenwald	2024	PODS
3	2,406	Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles	2005	SIGMOD
4	11,569	Efficient and Error-bounded Spatiotemporal Quantile Monitoring in Edge Computing Environments	2022	VLDB
5	4,472	Relative Error Streaming Quantiles	2021	PODS
6	3,765	Quantiles over Data Streams: An Experimental Study	2013	SIGMOD
7	3,832	Optimal Tracking of Distributed Heavy Hitters and Quantiles	2009	PODS
8	10,487	Quantile Estimation with Duplicates	2026	SIGMOD
9	2,716	Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams	2006	PODS
10	9,318	Estimating Quantiles from the Union of Historical and Streaming Data	2017	VLDB