Back to papers
Processing Complex Aggregate Queries over Data Streams
Summary: Sketch-based, memory-limited approximate aggregation for continuous streams. Domain-partitioned sketches with histogram priors tighten error guarantees and beat histograms in accuracy on real and synthetic data.
(summarized by gpt-5-nano on Feb 09 2026)
Paper ID
3400
Venue
SIGMOD
Year
2002
Pagerank
0.00013823702
Overall Rank
817 | 94.40%
DOI
10.1145/564691.564699
Incoming Non-self Citations Over Time
BibTeX Citation
@inproceedings{dobra_sigmod02,
title = {{Processing Complex Aggregate Queries over Data Streams}},
author = {Dobra, Alin and Garofalakis, Minos and Gehrke, Johannes and Rastogi, Rajeev},
series = {{SIGMOD} '02},
booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
publisher = {Association for Computing Machinery},
doi = {10.1145/564691.564699},
url = {https://dl.acm.org/doi/10.1145/564691.564699},
year = {2002}
}
Incoming Citations (Sorted by Pagerank)
Showing 37 of 37 citing papers.
Rank
Citing Paper
Year
Venue
Pagerank
26
Models and Issues in Data Stream Systems 2002
PODS
0.00052982574
737
Join Size Estimation Subject to Filter Conditions 2015
VLDB
0.00014490983
1,045
Sketching Streams Through the Net: Distributed Approximate Query Tracking 2005
VLDB
0.00012440928
1,082
A Transducer-Based XML Query Processor 2002
VLDB
0.00012257574
1,252
Streaming Pattern Discovery in Multiple Time-Series 2005
VLDB
0.00011483752
1,294
Augmented Sketch: Faster and More Accurate Stream Processing 2016
SIGMOD
0.00011291308
1,664
Two-Level Sampling for Join Size Estimation 2017
SIGMOD
0.00010070362
1,905
Cold Filter: A Meta-Framework for Faster and More Accurate Stream Processing 2018
SIGMOD
9.5034849e-05
2,271
Online Maintenance of Very Large Random Samples 2004
SIGMOD
8.8254873e-05
2,377
gSketch: On Query Estimation in Graph Streams 2012
VLDB
8.6710302e-05
2,513
Tuple Routing Strategies for Distributed Eddies 2003
VLDB
8.48462e-05
2,697
Sketching Probabilistic Data Streams 2007
SIGMOD
8.2451054e-05
3,023
Persistent Data Sketching 2015
SIGMOD
7.8398269e-05
3,044
Holistic UDAFs at Streaming Speeds 2004
SIGMOD
7.820774e-05
3,197
Processing Set Expressions over Continuous Update Streams 2003
SIGMOD
7.6439415e-05
3,617
Scalable Computation of Acyclic Joins (Extended Abstract) 2006
PODS
7.2557398e-05
3,657
Memory-Limited Execution of Windowed Stream Joins 2004
VLDB
7.2217692e-05
3,703
Approximation Techniques for Spatial Data 2004
SIGMOD
7.1829776e-05
3,788
Graph-Based Synopses for Relational Selectivity Estimation 2006
SIGMOD
7.1244416e-05
4,517
Window-Aware Load Shedding for Aggregation Queries over Data Streams 2006
VLDB
6.6481605e-05
4,630
Efficient Join Synopsis Maintenance for Data Warehouse 2020
SIGMOD
6.5955933e-05
4,900
COMPASS: Online Sketch-based Query Optimization for In-Memory Databases 2021
SIGMOD
6.4534715e-05
5,272
Adaptive, Hands-Off Stream Mining 2003
VLDB
6.2899363e-05
5,743
Joins on Samples: A Theoretical Guide for Practitioners 2020
VLDB
6.1025457e-05
6,033
Load Shedding in Stream Databases: A Control-Based Approach 2006
VLDB
5.9998228e-05
6,305
A Regression-Based Temporal Pattern Mining Scheme for Data Streams 2003
VLDB
5.9204295e-05
6,727
Fast Range-Summable Random Variables for Efficient Aggregate Estimation 2006
SIGMOD
5.7902041e-05
7,256
Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries 2021
SIGMOD
5.6625146e-05
7,388
Synopses for Query Optimization: A Space-Complexity Perspective 2004
PODS
5.6268292e-05
7,443
Histograms Revisited: When are histograms the best approximation method for aggregates over joins? 2005
PODS
5.6166792e-05
7,747
Convolution and Cross-Correlation of Count Sketches Enables Fast Cardinality Estimation of Multi-Join Queries 2024
SIGMOD
5.5529458e-05
7,752
Sketch-based Geometric Monitoring of Distributed Stream Queries 2013
VLDB
5.5521918e-05
8,155
Containment Join Size Estimation: Models and Methods 2003
SIGMOD
5.4766319e-05
9,027
JoinSketch: A Sketch Algorithm for Accurate and Unbiased Inner-Product Estimation 2023
SIGMOD
5.3293224e-05
12,671
Randomized Algorithms for Data Reconciliation in Wide Area Aggregate Query Processing 2007
VLDB
5.093636e-05
12,724
Join-Distinct Aggregate Estimation over Update Streams 2005
PODS
5.093636e-05
12,819
Estimating the Output Cardinality of Partial Preaggregation with a Measure of Clusteredness 2003
VLDB
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.
Semantically Similar Papers
#
Overall Rank
Paper
Year
Venue
1
7,443
Histograms Revisited: When are histograms the best approximation method for aggregates over joins? 2005
PODS
2
9,188
OmniSketch: Efficient Multi-Dimensional High-Velocity Stream Analytics with Arbitrary Predicates 2024
VLDB
3
2,377
gSketch: On Query Estimation in Graph Streams 2012
VLDB
4
1,962
Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee 2016
SIGMOD
5
7,752
Sketch-based Geometric Monitoring of Distributed Stream Queries 2013
VLDB
6
10,289
Sketch-based Secure Query Processing for Streaming Data 2026
SIGMOD
7
7,713
Sketch-based Querying of Distributed Sliding-Window Data Streams 2012
VLDB
8
12,467
Conditioning and Aggregating Uncertain Data Streams: Going Beyond Expectations 2010
VLDB
9
1,045
Sketching Streams Through the Net: Distributed Approximate Query Tracking 2005
VLDB
10
2,697
Sketching Probabilistic Data Streams 2007
SIGMOD