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: 3983
Venue: SIGMOD
Year: 2008
Pagerank: 4.9177481e-05
Overall Rank: 6,815 | 52.59%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,429	A Scalable, Predictable Join Operator for Highly Concurrent Data Warehouses	2009	VLDB	0.00012033518
1,509	Discovering Queries based on Example Tuples	2014	SIGMOD	0.00011612727
8,252	A Generic Flow Algorithm for Shared Filter Ordering Problems	2008	PODS	4.5497007e-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
41	NiagaraCQ: A Scalable Continuous Query System for Internet Databases	2000	SIGMOD	0.00073964959
139	Predicate Migration: Optimizing Queries with Expensive Predicates	1993	SIGMOD	0.00042299329
226	Efficient Filtering of XML Documents for Selective Dissemination of Information	2000	VLDB	0.00032431532
244	Continuously Adaptive Continuous Queries over Streams	2002	SIGMOD	0.00031066222
977	Pipelining in Multi-Query Optimization	2001	PODS	0.0001488881
1,043	Adaptive Ordering of Pipelined Stream Filters	2004	SIGMOD	0.00014476247
1,112	Materialized View Selection and Maintenance Using Multi-Query Optimization	2001	SIGMOD	0.00013917776
4,272	Flow Algorithms for Two Pipelined Filter Ordering Problems	2006	PODS	6.3052723e-05
4,384	Optimization of Continuous Queries with Shared Expensive Filters	2007	PODS	6.2371282e-05
7,781	WebFilter: A High-throughput XML-based Publish and Subscribe System	2001	VLDB	4.6525408e-05
8,963	S-ToPSS: Semantic Toronto Publish/Subscribe System	2003	VLDB	4.4198771e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,003	Adaptive Filters for Continuous Queries over Distributed Data Streams	2003	SIGMOD	0.00014698435
1,717	Approximate Join Processing Over Data Streams	2003	SIGMOD	0.00010793312
3,462	Efficient and Provable Multi-Query Optimization	2017	PODS	7.0703696e-05
6,335	Adaptive Stream Filters for Entity-based Queries with Non-Value Tolerance	2005	VLDB	5.1056594e-05
7,145	Tight Trade-offs for the Maximum k-Coverage Problem in the General Streaming Model	2019	PODS	4.8179617e-05
5,066	Tight Space-Approximation Tradeoff for the Multi-Pass Streaming Set Cover Problem	2017	PODS	5.7223891e-05
4,272	Flow Algorithms for Two Pipelined Filter Ordering Problems	2006	PODS	6.3052723e-05
8,252	A Generic Flow Algorithm for Shared Filter Ordering Problems	2008	PODS	4.5497007e-05
1,043	Adaptive Ordering of Pipelined Stream Filters	2004	SIGMOD	0.00014476247
4,384	Optimization of Continuous Queries with Shared Expensive Filters	2007	PODS	6.2371282e-05