Processing Set Expressions over Continuous Update Streams

Summary: First space-efficient algorithm for estimating the cardinality of general set expressions over update streams (inserts and deletes). Extends beyond insert-only models, handling distributed streams and complex expressions under tight memory. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h93afd6740ea54ca2
Venue: SIGMOD
Year: 2003
Pagerank: 7.4734096e-05
Overall Rank: 3,272 | 78.01%
DOI: 10.1145/872757.872790

Incoming Non-self Citations Over Time

Authors

1. Sumit Ganguly (AT&T)
2. Minos Garofalakis (AT&T)
3. Rajeev Rastogi (AT&T)

BibTeX Citation

@inproceedings{ganguly_sigmod03,
        title = {{Processing Set Expressions over Continuous Update Streams}},
        author = {Ganguly, Sumit and Garofalakis, Minos and Rastogi, Rajeev},
        series = {{SIGMOD} '03},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/872757.872790},
        url = {https://dl.acm.org/doi/10.1145/872757.872790},
        year = {2003}
}

Incoming Citations (Sorted by Pagerank)

Showing 11 of 11 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,278	Streaming Pattern Discovery in Multiple Time-Series	2005	VLDB	0.00011231952
2,054	Space Efficient Mining of Multigraph Streams	2005	PODS	9.1135465e-05
2,171	Summarizing and Mining Inverse Distributions on Data Streams via Dynamic Inverse Sampling	2005	VLDB	8.9239861e-05
2,465	Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles	2005	SIGMOD	8.4253671e-05
5,654	Distributed Set-Expression Cardinality Estimation	2004	VLDB	6.0507163e-05
6,865	Fast Range-Summable Random Variables for Efficient Aggregate Estimation	2006	SIGMOD	5.6603286e-05
7,530	Effective Variation Management for Pseudo Periodical Streams	2007	SIGMOD	5.5009752e-05
7,916	Sketch-based Geometric Monitoring of Distributed Stream Queries	2013	VLDB	5.4276156e-05
9,890	Sharing Aggregate Computation for Distributed Queries	2007	SIGMOD	5.1149505e-05
10,521	A Fast, Mergeable, and LDP Compatible Sketch for Counting the Number of Distinct Values in Fully Dynamic Tables	2026	SIGMOD	4.9793485e-05
13,050	Online Estimation For Subset-Based SQL Queries	2005	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
77	Sampling-Based Estimation of the Number of Distinct Values of an Attribute	1995	VLDB	0.00036828234
267	Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports	2001	VLDB	0.00022722971
295	Towards Estimation Error Guarantees for Distinct Values	2000	PODS	0.00021914399
428	Tracking Join and Self-Join Sizes in Limited Storage	1999	PODS	0.0001845349
842	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD	0.00013540697
862	How to Summarize the Universe: Dynamic Maintenance of Quantiles	2002	VLDB	0.00013396995
1,290	Querying and Mining Data Streams: You Only Get One Look	2002	SIGMOD	0.00011157506
2,093	Selectivity Estimation For Boolean Queries	2000	PODS	9.0578876e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,959	A Simple and Efficient Estimation Method for Stream Expression Cardinalities	2007	VLDB
2	11,471	Streaming Algorithms with Few State Changes	2024	PODS
3	842	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD
4	124	Approximate Frequency Counts over Data Streams	2002	VLDB
5	11,945	Frequent Elements with Witnesses in Data Streams	2021	PODS
6	734	Adaptive Filters for Continuous Queries over Distributed Data Streams	2003	SIGMOD
7	1,666	Characterizing Memory Requirements for Queries over Continuous Data Streams	2002	PODS
8	7,462	Update-Pattern-Aware Modeling and Processing of Continuous Queries	2005	SIGMOD
9	5,654	Distributed Set-Expression Cardinality Estimation	2004	VLDB
10	13,014	Join-Distinct Aggregate Estimation over Update Streams	2005	PODS