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
h97fa1306f6bef282
Venue
SIGMOD
Year
2002
Pagerank
0.00013540697
Overall Rank
842 | 94.35%
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.00052121228
750
Join Size Estimation Subject to Filter Conditions 2015
VLDB
0.00014265196
1,066
Sketching Streams Through the Net: Distributed Approximate Query Tracking 2005
VLDB
0.00012192801
1,111
A Transducer-Based XML Query Processor 2002
VLDB
0.00011984202
1,278
Streaming Pattern Discovery in Multiple Time-Series 2005
VLDB
0.00011231952
1,319
Augmented Sketch: Faster and More Accurate Stream Processing 2016
SIGMOD
0.00011045888
1,678
Two-Level Sampling for Join Size Estimation 2017
SIGMOD
9.9088372e-05
1,970
Cold Filter: A Meta-Framework for Faster and More Accurate Stream Processing 2018
SIGMOD
9.2902522e-05
2,322
Online Maintenance of Very Large Random Samples 2004
SIGMOD
8.6361485e-05
2,420
gSketch: On Query Estimation in Graph Streams 2012
VLDB
8.4898523e-05
2,558
Tuple Routing Strategies for Distributed Eddies 2003
VLDB
8.3007355e-05
2,738
Sketching Probabilistic Data Streams 2007
SIGMOD
8.07308e-05
3,080
Persistent Data Sketching 2015
SIGMOD
7.6662346e-05
3,094
Holistic UDAFs at Streaming Speeds 2004
SIGMOD
7.6533343e-05
3,272
Processing Set Expressions over Continuous Update Streams 2003
SIGMOD
7.4734096e-05
3,660
Scalable Computation of Acyclic Joins (Extended Abstract) 2006
PODS
7.1218018e-05
3,727
Memory-Limited Execution of Windowed Stream Joins 2004
VLDB
7.0696489e-05
3,758
Approximation Techniques for Spatial Data 2004
SIGMOD
7.0437238e-05
3,851
Graph-Based Synopses for Relational Selectivity Estimation 2006
SIGMOD
6.9785886e-05
4,590
Window-Aware Load Shedding for Aggregation Queries over Data Streams 2006
VLDB
6.5139479e-05
4,642
Efficient Join Synopsis Maintenance for Data Warehouse 2020
SIGMOD
6.4898745e-05
5,003
COMPASS: Online Sketch-based Query Optimization for In-Memory Databases 2021
SIGMOD
6.3188773e-05
5,390
Adaptive, Hands-Off Stream Mining 2003
VLDB
6.1508226e-05
5,831
Joins on Samples: A Theoretical Guide for Practitioners 2020
VLDB
5.9782109e-05
6,160
Load Shedding in Stream Databases: A Control-Based Approach 2006
VLDB
5.8652029e-05
6,432
A Regression-Based Temporal Pattern Mining Scheme for Data Streams 2003
VLDB
5.78833e-05
6,865
Fast Range-Summable Random Variables for Efficient Aggregate Estimation 2006
SIGMOD
5.6603286e-05
7,364
Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries 2021
SIGMOD
5.5418075e-05
7,493
Synopses for Query Optimization: A Space-Complexity Perspective 2004
PODS
5.5103311e-05
7,566
Convolution and Cross-Correlation of Count Sketches Enables Fast Cardinality Estimation of Multi-Join Queries 2024
SIGMOD
5.4952834e-05
7,568
Histograms Revisited: When are histograms the best approximation method for aggregates over joins? 2005
PODS
5.49478e-05
7,916
Sketch-based Geometric Monitoring of Distributed Stream Queries 2013
VLDB
5.4276156e-05
8,035
JoinSketch: A Sketch Algorithm for Accurate and Unbiased Inner-Product Estimation 2023
SIGMOD
5.4025473e-05
8,325
Containment Join Size Estimation: Models and Methods 2003
SIGMOD
5.3540828e-05
12,961
Randomized Algorithms for Data Reconciliation in Wide Area Aggregate Query Processing 2007
VLDB
4.9793485e-05
13,014
Join-Distinct Aggregate Estimation over Update Streams 2005
PODS
4.9793485e-05
13,109
Estimating the Output Cardinality of Partial Preaggregation with a Measure of Clusteredness 2003
VLDB
4.9793485e-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,568
Histograms Revisited: When are histograms the best approximation method for aggregates over joins? 2005
PODS
2
9,367
OmniSketch: Efficient Multi-Dimensional High-Velocity Stream Analytics with Arbitrary Predicates 2024
VLDB
3
2,420
gSketch: On Query Estimation in Graph Streams 2012
VLDB
4
2,000
Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee 2016
SIGMOD
5
7,916
Sketch-based Geometric Monitoring of Distributed Stream Queries 2013
VLDB
6
10,501
Sketch-based Secure Query Processing for Streaming Data 2026
SIGMOD
7
7,870
Sketch-based Querying of Distributed Sliding-Window Data Streams 2012
VLDB
8
12,758
Conditioning and Aggregating Uncertain Data Streams: Going Beyond Expectations 2010
VLDB
9
1,066
Sketching Streams Through the Net: Distributed Approximate Query Tracking 2005
VLDB
10
2,738
Sketching Probabilistic Data Streams 2007
SIGMOD