Mergeable Summaries
Summary: Show heavy-hitter and quantile summaries can be made mergeable: deterministic heavy-hitters size O(1/ε) and randomized fully-mergeable quantiles size O((1/ε)log^{3/2}(1/ε)). Extend to geometric ε-approximations/ε-kernels and show MG=SpaceSaving. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Pankaj K. Agarwal (Duke University)
- 2. Graham Cormode (AT&T Labs — Research)
- 3. Zengfeng Huang (Hong Kong University of Science and Technology)
- 4. Jeff M. Phillips (University of Utah)
- 5. Zhewei Wei (Hong Kong University of Science and Technology)
- 6. Ke Yi (Hong Kong University of Science and Technology)
BibTeX Citation
@inproceedings{agarwal_pods12,
address = {New York, NY, USA},
series = {{PODS} '12},
title = {{Mergeable Summaries}},
url = {https://dl.acm.org/doi/10.1145/2213556.2213562},
doi = {10.1145/2213556.2213562},
booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
publisher = {Association for Computing Machinery},
author = {Agarwal, Pankaj K. and Cormode, Graham and Huang, Zengfeng and Phillips, Jeff M. and Wei, Zhewei and Yi, Ke},
year = {2012}
}Incoming Citations (Sorted by Pagerank)
Showing 50 of 52 citing papers.
Outgoing Citations (Sorted by Pagerank)
Showing 9 of 9 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 83 | Space-Efficient Online Computation of Quantile Summaries | 2001 | SIGMOD | 0.00035978046 |
| 252 | Approximate Medians and other Quantiles in One Pass and with Limited Memory | 1998 | SIGMOD | 0.00023050233 |
| 494 | An Optimal Algorithm for the Distinct Elements Problem | 2010 | PODS | 0.00017387321 |
| 862 | How to Summarize the Universe: Dynamic Maintenance of Quantiles | 2002 | VLDB | 0.00013396995 |
| 909 | Finding Frequent Items in Data Streams | 2008 | VLDB | 0.00013125647 |
| 1,434 | Power-Conserving Computation of Order-Statistics over Sensor Networks | 2004 | PODS | 0.00010665845 |
| 1,636 | Space-optimal Heavy Hitters with Strong Error Bounds | 2009 | PODS | 0.00010016656 |
| 2,124 | Tributaries and Deltas: Efficient and Robust Aggregation in Sensor Network Streams | 2005 | SIGMOD | 9.0056375e-05 |
| 4,446 | Fast Manhattan Sketches in Data Streams | 2010 | PODS | 6.5969248e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 2,750 | Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams | 2006 | PODS |
| 2 | 7,513 | Computing A Well-Representative Summary of Conjunctive Query Results | 2024 | PODS |
| 3 | 3,917 | Optimal Tracking of Distributed Heavy Hitters and Quantiles | 2009 | PODS |
| 4 | 7,239 | Simple & Optimal Quantile Sketch: Combining Greenwald-Khanna with Khanna-Greenwald | 2024 | PODS |
| 5 | 2,798 | Moment-Based Quantile Sketches for Efficient High Cardinality Aggregation Queries | 2018 | VLDB |
| 6 | 9,570 | Determining Exact Quantiles with Randomized Summaries | 2024 | SIGMOD |
| 7 | 252 | Approximate Medians and other Quantiles in One Pass and with Limited Memory | 1998 | SIGMOD |
| 8 | 4,564 | Relative Error Streaming Quantiles | 2021 | PODS |
| 9 | 83 | Space-Efficient Online Computation of Quantile Summaries | 2001 | SIGMOD |
| 10 | 5,320 | A Tight Lower Bound for Comparison-Based Quantile Summaries | 2020 | PODS |