DBScholar

Back to papers

Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles

Summary: Proposes distributed-tracking schemes for continuous approximate quantiles over distributed streams, with space-per-site storage and low communication. A hybrid approach—local tracking plus simple prediction models—extends to holistic aggregates (e.g., heavy hitters), with experiments showing substantial savings. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
h88f1e21f7d78fd38
Venue
SIGMOD
Year
2005
Pagerank
8.3988741e-05
Overall Rank
2,472 | 83.44%
DOI
10.1145/1066157.1066161

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{cormode_sigmod05,
        title = {{Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles}},
        author = {Cormode, Graham and Garofalakis, Minos and Muthukrishnan, S. and Rastogi, Rajeev},
        series = {{SIGMOD} '05},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1066157.1066161},
        url = {https://dl.acm.org/doi/10.1145/1066157.1066161},
        year = {2005}
}

Incoming Citations (Sorted by Pagerank)

Showing 26 of 26 citing papers.

Rank Citing Paper Year Venue Pagerank
1,070 Sketching Streams Through the Net: Distributed Approximate Query Tracking 2005 VLDB 0.0001215545
1,471 Communication-Efficient Distributed Monitoring of Thresholded Counts 2006 SIGMOD 0.00010529345
2,230 Optimal Sampling From Distributed Streams 2010 PODS 8.7889857e-05
2,658 A Geometric Approach to Monitoring Threshold Functions Over Distributed Data Streams 2006 SIGMOD 8.1455298e-05
3,667 Quantiles over Data Streams: An Experimental Study 2013 SIGMOD 7.0967962e-05
3,932 Optimal Tracking of Distributed Heavy Hitters and Quantiles 2009 PODS 6.900511e-05
3,955 Randomized Algorithms for Tracking Distributed Count, Frequencies, and Ranks 2012 PODS 6.8843906e-05
5,140 Shape Sensitive Geometric Monitoring 2008 PODS 6.2436669e-05
5,399 At-the-time and Back-in-time Persistent Sketches 2021 SIGMOD 6.1336701e-05
6,310 Sampling Based Algorithms for Quantile Computation in Sensor Networks 2011 SIGMOD 5.7992155e-05
6,856 Continuous Matrix Approximation on Distributed Data 2014 VLDB 5.6470368e-05
7,037 Continuous Distributed Counting for Non-monotonic Streams 2012 PODS 5.5993909e-05
7,415 Together is Better: Heavy Hitters Quantile Estimation 2023 SIGMOD 5.5160692e-05
7,435 Streaming in a Connected World: Querying and Tracking Distributed Data Streams 2007 SIGMOD 5.5132769e-05
7,643 Distributed Online Tracking 2015 SIGMOD 5.4615983e-05
7,889 Sketch-based Querying of Distributed Sliding-Window Data Streams 2012 VLDB 5.4159519e-05
7,935 Sketch-based Geometric Monitoring of Distributed Stream Queries 2013 VLDB 5.4071076e-05
8,694 Prediction-Based Geometric Monitoring Over Distributed Data Streams 2012 SIGMOD 5.2718203e-05
9,369 Efficient Gossip-Based Aggregate Computation 2006 PODS 5.1725834e-05
9,644 Ranking Distributed Probabilistic Data 2009 SIGMOD 5.1334081e-05
9,931 Sharing Aggregate Computation for Distributed Queries 2007 SIGMOD 5.0956239e-05
11,921 MinMax Sampling: A Near-optimal Global Summary for Aggregation in the Wide Area 2022 SIGMOD 4.9605343e-05
11,928 Efficient and Error-bounded Spatiotemporal Quantile Monitoring in Edge Computing Environments 2022 VLDB 4.9605343e-05
11,988 Model Counting meets F0 Estimation 2021 PODS 4.9605343e-05
12,398 Scalable Approximate Query Tracking over Highly Distributed Data Streams 2016 SIGMOD 4.9605343e-05
12,917 LEE WAVE: Level-Wise Distribution of Wavelet Coefficients for Processing kNN Queries over Distributed Streams 2008 VLDB 4.9605343e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 16 of 16 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
124 Approximate Frequency Counts over Data Streams 2002 VLDB 0.00030503973
240 Gigascope: A Stream Database for Network Applications 2003 SIGMOD 0.00023371986
252 Approximate Medians and other Quantiles in One Pass and with Limited Memory 1998 SIGMOD 0.00023058622
268 Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports 2001 VLDB 0.00022654182
316 Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries 2001 VLDB 0.00021238056
343 Model-Driven Data Acquisition in Sensor Networks 2004 VLDB 0.00020486383
432 Tracking Join and Self-Join Sizes in Limited Storage 1999 PODS 0.00018400309
565 Distributed Top-K Monitoring 2003 SIGMOD 0.00016238411
738 Adaptive Filters for Continuous Queries over Distributed Data Streams 2003 SIGMOD 0.0001432185
852 The Design of an Acquisitional Query Processor For Sensor Networks 2003 SIGMOD 0.00013447072
860 What’s Hot and What’s Not: Tracking Most Frequent Items Dynamically 2003 PODS 0.00013382689
861 How to Summarize the Universe: Dynamic Maintenance of Quantiles 2002 VLDB 0.00013374869
1,438 Power-Conserving Computation of Order-Statistics over Sensor Networks 2004 PODS 0.00010647197
3,284 Processing Set Expressions over Continuous Update Streams 2003 SIGMOD 7.4455194e-05
5,666 Distributed Set-Expression Cardinality Estimation 2004 VLDB 6.0281748e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 861 How to Summarize the Universe: Dynamic Maintenance of Quantiles 2002 VLDB
2 738 Adaptive Filters for Continuous Queries over Distributed Data Streams 2003 SIGMOD
3 3,091 Holistic UDAFs at Streaming Speeds 2004 SIGMOD
4 6,310 Sampling Based Algorithms for Quantile Computation in Sensor Networks 2011 SIGMOD
5 3,932 Optimal Tracking of Distributed Heavy Hitters and Quantiles 2009 PODS
6 9,481 Estimating Quantiles from the Union of Historical and Streaming Data 2017 VLDB
7 12,398 Scalable Approximate Query Tracking over Highly Distributed Data Streams 2016 SIGMOD
8 7,435 Streaming in a Connected World: Querying and Tracking Distributed Data Streams 2007 SIGMOD
9 7,935 Sketch-based Geometric Monitoring of Distributed Stream Queries 2013 VLDB
10 1,070 Sketching Streams Through the Net: Distributed Approximate Query Tracking 2005 VLDB