Flow Algorithms for Two Pipelined Filter Ordering Problems

Summary: Presents flow-based O(n^2) algorithms for two pipelined filter-ordering extensions: a distributional parallel-throughput maximization problem and an adversarial minimax multiplicative-regret formulation. Unified flow approach yields optimal orderings and improves prior O(n^3 log n) result. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1390
Venue: PODS
Year: 2006
Pagerank: 6.713113e-05
Overall Rank: 4,421 | 69.67%
DOI: 10.1145/1142351.1142379

Incoming Non-self Citations Over Time

Authors

1. Anne Condon (University of British Columbia)
2. Amol Deshpande (University of Maryland)
3. Lisa Hellerstein (Polytechnic University)
4. Ning Wu (Polytechnic University)

BibTeX Citation

@inproceedings{condon_pods06,
        address = {New York, NY, USA},
        series = {{PODS} '06},
        title = {{Flow Algorithms for Two Pipelined Filter Ordering Problems}},
        url = {https://dl.acm.org/doi/10.1145/1142351.1142379},
        doi = {10.1145/1142351.1142379},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Condon, Anne and Deshpande, Amol and Hellerstein, Lisa and Wu, Ning},
        year = {2006}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
739	Finding Related Tables	2012	SIGMOD	0.0001448231
2,578	Query Optimization over Web Services	2006	VLDB	8.3919147e-05
6,901	Near-Optimal Algorithms for Shared Filter Evaluation in Data Stream Systems	2008	SIGMOD	5.742719e-05
8,437	A Generic Flow Algorithm for Shared Filter Ordering Problems	2008	PODS	5.4252897e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
53	Eddies: Continuously Adaptive Query Processing	2000	SIGMOD	0.00041071971
143	Optimization of Nonrecursive Queries	1986	VLDB	0.0002959213
813	Adaptive Ordering of Pipelined Stream Filters	2004	SIGMOD	0.00013846487
1,106	WSQ/DSQ: A Practical Approach for Combined Querying of Databases and the Web*	2000	SIGMOD	0.00012151041
2,244	Join Queries with External Text Sources: Execution and Optimization Techniques	1995	SIGMOD	8.8737737e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,350	The Filter-Placement Problem and its Application to Minimizing Information Multiplicity	2012	VLDB
2	2,131	Optimization Algorithms for Exploiting the Parallelism-Communication Tradeoff in Pipelined Parallelism	1994	VLDB
3	9,612	Memory Efficient Scheduling of Query Pipeline Execution	2022	CIDR
4	722	Adaptive Filters for Continuous Queries over Distributed Data Streams	2003	SIGMOD
5	822	Pipelining in Multi-Query Optimization	2001	PODS
6	3,847	Operator Placement for In-Network Stream Query Processing	2005	PODS
7	6,901	Near-Optimal Algorithms for Shared Filter Evaluation in Data Stream Systems	2008	SIGMOD
8	4,441	Optimization of Continuous Queries with Shared Expensive Filters	2007	PODS
9	8,437	A Generic Flow Algorithm for Shared Filter Ordering Problems	2008	PODS
10	813	Adaptive Ordering of Pipelined Stream Filters	2004	SIGMOD