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: 3500
Venue: SIGMOD
Year: 2003
Pagerank: 7.6439415e-05
Overall Rank: 3,197 | 78.07%
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,252	Streaming Pattern Discovery in Multiple Time-Series	2005	VLDB	0.00011483752
2,013	Space Efficient Mining of Multigraph Streams	2005	PODS	9.3068345e-05
2,128	Summarizing and Mining Inverse Distributions on Data Streams via Dynamic Inverse Sampling	2005	VLDB	9.1271562e-05
2,406	Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles	2005	SIGMOD	8.6187297e-05
5,516	Distributed Set-Expression Cardinality Estimation	2004	VLDB	6.1895841e-05
6,727	Fast Range-Summable Random Variables for Efficient Aggregate Estimation	2006	SIGMOD	5.7902041e-05
7,400	Effective Variation Management for Pseudo Periodical Streams	2007	SIGMOD	5.6255397e-05
7,752	Sketch-based Geometric Monitoring of Distributed Stream Queries	2013	VLDB	5.5521918e-05
9,718	Sharing Aggregate Computation for Distributed Queries	2007	SIGMOD	5.2323504e-05
10,310	A Fast, Mergeable, and LDP Compatible Sketch for Counting the Number of Distinct Values in Fully Dynamic Tables	2026	SIGMOD	5.093636e-05
12,760	Online Estimation For Subset-Based SQL Queries	2005	VLDB	5.093636e-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
75	Sampling-Based Estimation of the Number of Distinct Values of an Attribute	1995	VLDB	0.00037277061
255	Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports	2001	VLDB	0.00023174541
288	Towards Estimation Error Guarantees for Distinct Values	2000	PODS	0.00022296371
418	Tracking Join and Self-Join Sizes in Limited Storage	1999	PODS	0.00018812821
817	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD	0.00013823702
842	How to Summarize the Universe: Dynamic Maintenance of Quantiles	2002	VLDB	0.00013671191
1,274	Querying and Mining Data Streams: You Only Get One Look	2002	SIGMOD	0.00011377527
2,061	Selectivity Estimation For Boolean Queries	2000	PODS	9.2445049e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	11,123	Streaming Algorithms with Few State Changes	2024	PODS
2	12,669	A Simple and Efficient Estimation Method for Stream Expression Cardinalities	2007	VLDB
3	817	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD
4	122	Approximate Frequency Counts over Data Streams	2002	VLDB
5	11,638	Frequent Elements with Witnesses in Data Streams	2021	PODS
6	722	Adaptive Filters for Continuous Queries over Distributed Data Streams	2003	SIGMOD
7	1,656	Characterizing Memory Requirements for Queries over Continuous Data Streams	2002	PODS
8	7,321	Update-Pattern-Aware Modeling and Processing of Continuous Queries	2005	SIGMOD
9	5,516	Distributed Set-Expression Cardinality Estimation	2004	VLDB
10	12,724	Join-Distinct Aggregate Estimation over Update Streams	2005	PODS