Database Paper Browser

Back to papers

Sketching Probabilistic Data Streams

Summary: First sublinear-space, sublinear-time algorithms for aggregating probabilistic data streams under possible-worlds semantics. Introduces concise streaming sketches extending conventional sketching to probabilistic streams to approximate distributions of complex aggregates (distinct counts, joins) with randomized guarantees. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
3859
Venue
SIGMOD
Year
2007
Pagerank
7.6537004e-05
Overall Rank
3,047 | 78.83%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 11 of 11 citing papers.

Rank Citing Paper Year Venue Pagerank
1,863 Approximation Algorithms for Clustering Uncertain Data 2008 PODS 0.00010287379
3,391 Estimating Statistical Aggregates on Probabilistic Data Streams 2007 PODS 7.1427968e-05
3,395 Event Queries on Correlated Probabilistic Streams 2008 SIGMOD 7.1402267e-05
4,328 Sliding-Window Top-k Queries on Uncertain Streams 2008 VLDB 6.2765138e-05
5,771 PODS: A New Model and Processing Algorithms for Uncertain Data Streams 2010 SIGMOD 5.3319881e-05
5,807 Finding Frequent Items in Probabilistic Data 2008 SIGMOD 5.3189104e-05
6,837 Capturing Data Uncertainty in High-Volume Stream Processing 2009 CIDR 4.9063121e-05
8,092 Probabilistic Histograms for Probabilistic Data 2009 VLDB 4.5847443e-05
9,041 TreeSensing: Linearly Compressing Sketches with Flexibility 2023 SIGMOD 4.3997447e-05
12,116 Space-Efficient Estimation of Statistics over Sub-Sampled Streams 2012 PODS 4.1905499e-05
12,280 Conditioning and Aggregating Uncertain Data Streams: Going Beyond Expectations 2010 VLDB 4.1905499e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
43 Models and Issues in Data Stream Systems 2002 PODS 0.00072660894
74 Efficient Query Evaluation on Probabilistic Databases 2004 VLDB 0.00057797415
103 ULDBs: Databases with Uncertainty and Lineage 2006 VLDB 0.00049520051
126 Space-Efficient Online Computation of Quantile Summaries 2001 SIGMOD 0.00044753012
168 Approximate Frequency Counts over Data Streams 2002 VLDB 0.0003915627
344 Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries 2001 VLDB 0.00026698826
550 Tracking Join and Self-Join Sizes in Limited Storage 1999 PODS 0.00020346247
1,065 Processing Complex Aggregate Queries over Data Streams 2002 SIGMOD 0.00014344675
1,222 Querying and Mining Data Streams: You Only Get One Look 2002 SIGMOD 0.00013205769
2,952 Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams 2006 PODS 7.8230109e-05
3,391 Estimating Statistical Aggregates on Probabilistic Data Streams 2007 PODS 7.1427968e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
463 Evaluating Probabilistic Queries over Imprecise Data 2003 SIGMOD 0.00022497894
7,625 Optimizing Probabilistic Query Processing on Continuous Uncertain Data 2011 VLDB 4.6888879e-05
5,807 Finding Frequent Items in Probabilistic Data 2008 SIGMOD 5.3189104e-05
7,697 Sketch-based Geometric Monitoring of Distributed Stream Queries 2013 VLDB 4.6701245e-05
1,394 Sketching Streams Through the Net: Distributed Approximate Query Tracking 2005 VLDB 0.00012218557
8,092 Probabilistic Histograms for Probabilistic Data 2009 VLDB 4.5847443e-05
7,839 Sketch-based Querying of Distributed Sliding-Window Data Streams 2012 VLDB 4.6338068e-05
3,391 Estimating Statistical Aggregates on Probabilistic Data Streams 2007 PODS 7.1427968e-05
1,065 Processing Complex Aggregate Queries over Data Streams 2002 SIGMOD 0.00014344675
12,280 Conditioning and Aggregating Uncertain Data Streams: Going Beyond Expectations 2010 VLDB 4.1905499e-05