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: 3984
Venue: SIGMOD
Year: 2008
Pagerank: 4.9135157e-05
Overall Rank: 6,813 | 52.65%
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,430	A Scalable, Predictable Join Operator for Highly Concurrent Data Warehouses	2009	VLDB	0.0001202506
1,502	Discovering Queries based on Example Tuples	2014	SIGMOD	0.00011614522
8,247	A Generic Flow Algorithm for Shared Filter Ordering Problems	2008	PODS	4.5454359e-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.00073944756
140	Predicate Migration: Optimizing Queries with Expensive Predicates	1993	SIGMOD	0.00042289025
227	Efficient Filtering of XML Documents for Selective Dissemination of Information	2000	VLDB	0.0003240219
244	Continuously Adaptive Continuous Queries over Streams	2002	SIGMOD	0.00031037999
977	Pipelining in Multi-Query Optimization	2001	PODS	0.000148774
1,041	Adaptive Ordering of Pipelined Stream Filters	2004	SIGMOD	0.00014470785
1,110	Materialized View Selection and Maintenance Using Multi-Query Optimization	2001	SIGMOD	0.00013902997
4,267	Flow Algorithms for Two Pipelined Filter Ordering Problems	2006	PODS	6.2995545e-05
4,381	Optimization of Continuous Queries with Shared Expensive Filters	2007	PODS	6.2323251e-05
7,781	WebFilter: A High-throughput XML-based Publish and Subscribe System	2001	VLDB	4.6480919e-05
8,968	S-ToPSS: Semantic Toronto Publish/Subscribe System	2003	VLDB	4.4156532e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,006	Adaptive Filters for Continuous Queries over Distributed Data Streams	2003	SIGMOD	0.00014684829
3,505	Efficient and Provable Multi-Query Optimization	2017	PODS	7.0304901e-05
1,712	Approximate Join Processing Over Data Streams	2003	SIGMOD	0.00010786152
6,337	Adaptive Stream Filters for Entity-based Queries with Non-Value Tolerance	2005	VLDB	5.1008035e-05
7,146	Tight Trade-offs for the Maximum k-Coverage Problem in the General Streaming Model	2019	PODS	4.8133378e-05
5,064	Tight Space-Approximation Tradeoff for the Multi-Pass Streaming Set Cover Problem	2017	PODS	5.716891e-05
4,267	Flow Algorithms for Two Pipelined Filter Ordering Problems	2006	PODS	6.2995545e-05
8,247	A Generic Flow Algorithm for Shared Filter Ordering Problems	2008	PODS	4.5454359e-05
1,041	Adaptive Ordering of Pipelined Stream Filters	2004	SIGMOD	0.00014470785
4,381	Optimization of Continuous Queries with Shared Expensive Filters	2007	PODS	6.2323251e-05