Near-Optimal Algorithms for Shared Filter Evaluation in Data Stream Systems

Summary: Addresses evaluating multiple overlapping stream queries with shared filters, a hard extension of set cover, and proposes near-optimal approximations. An edge-coverage Greedy (1+log n+log α) and a randomized Harmonic (2β) algorithm, implemented in a prototype with multimedia stream experiments showing Greedy outperforms alternatives and scales. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 4045
Venue: SIGMOD
Year: 2008
Pagerank: 5.742719e-05
Overall Rank: 6,901 | 52.66%
DOI: 10.1145/1376616.1376633

Incoming Non-self Citations Over Time

Authors

1. Zhen Liu (IBM)
2. Srinivasan Parthasarathy (IBM)
3. Anand Ranganathan (IBM)
4. Hao Yang (IBM)

BibTeX Citation

@inproceedings{liu_sigmod08,
        title = {{Near-Optimal Algorithms for Shared Filter Evaluation in Data Stream Systems}},
        author = {Liu, Zhen and Parthasarathy, Srinivasan and Ranganathan, Anand and Yang, Hao},
        series = {{SIGMOD} '08},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1376616.1376633},
        url = {https://dl.acm.org/doi/10.1145/1376616.1376633},
        year = {2008}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,022	A Scalable, Predictable Join Operator for Highly Concurrent Data Warehouses	2009	VLDB	0.00012602841
1,262	Discovering Queries based on Example Tuples	2014	SIGMOD	0.00011427456
8,437	A Generic Flow Algorithm for Shared Filter Ordering Problems	2008	PODS	5.4252897e-05

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
25	NiagaraCQ: A Scalable Continuous Query System for Internet Databases	2000	SIGMOD	0.00054667018
132	Predicate Migration: Optimizing Queries with Expensive Predicates	1993	SIGMOD	0.00030378624
193	Continuously Adaptive Continuous Queries over Streams	2002	SIGMOD	0.00025964286
236	Efficient Filtering of XML Documents for Selective Dissemination of Information	2000	VLDB	0.00023721569
813	Adaptive Ordering of Pipelined Stream Filters	2004	SIGMOD	0.00013846487
822	Pipelining in Multi-Query Optimization	2001	PODS	0.00013807229
929	Materialized View Selection and Maintenance Using Multi-Query Optimization	2001	SIGMOD	0.00013152103
4,421	Flow Algorithms for Two Pipelined Filter Ordering Problems	2006	PODS	6.713113e-05
4,441	Optimization of Continuous Queries with Shared Expensive Filters	2007	PODS	6.7021508e-05
7,778	WebFilter: A High-throughput XML-based Publish and Subscribe System	2001	VLDB	5.5460387e-05
9,146	S-ToPSS: Semantic Toronto Publish/Subscribe System	2003	VLDB	5.3145098e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	722	Adaptive Filters for Continuous Queries over Distributed Data Streams	2003	SIGMOD
2	1,397	Approximate Join Processing Over Data Streams	2003	SIGMOD
3	3,268	Efficient and Provable Multi-Query Optimization	2017	PODS
4	7,027	Adaptive Stream Filters for Entity-based Queries with Non-Value Tolerance	2005	VLDB
5	7,698	Tight Trade-offs for the Maximum k-Coverage Problem in the General Streaming Model	2019	PODS
6	5,668	Tight Space-Approximation Tradeoff for the Multi-Pass Streaming Set Cover Problem	2017	PODS
7	4,421	Flow Algorithms for Two Pipelined Filter Ordering Problems	2006	PODS
8	8,437	A Generic Flow Algorithm for Shared Filter Ordering Problems	2008	PODS
9	813	Adaptive Ordering of Pipelined Stream Filters	2004	SIGMOD
10	4,441	Optimization of Continuous Queries with Shared Expensive Filters	2007	PODS