A Generic Flow Algorithm for Shared Filter Ordering Problems

Summary: Flow-maximization for evaluating overlapping conjunctive boolean queries with shared filters on heterogeneous parallel processors, maximizing throughput under processor capacity constraints. Generic iterative algorithm uses a single-processor min-cost filter-ordering oracle to build parallel plans while preserving essentially the oracle’s approximation ratio, enabling many filter-ordering variants to be optimized in parallel. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1447
Venue: PODS
Year: 2008
Pagerank: 5.4252897e-05
Overall Rank: 8,437 | 42.12%
DOI: 10.1145/1376916.1376929

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_pods08,
        address = {New York, NY, USA},
        series = {{PODS} '08},
        title = {{A Generic Flow Algorithm for Shared Filter Ordering Problems}},
        url = {https://dl.acm.org/doi/10.1145/1376916.1376929},
        doi = {10.1145/1376916.1376929},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Liu, Zhen and Parthasarathy, Srinivasan and Ranganathan, Anand and Yang, Hao},
        year = {2008}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,022	A Scalable, Predictable Join Operator for Highly Concurrent Data Warehouses	2009	VLDB	0.00012602841

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 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
132	Predicate Migration: Optimizing Queries with Expensive Predicates	1993	SIGMOD	0.00030378624
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
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
6,901	Near-Optimal Algorithms for Shared Filter Evaluation in Data Stream Systems	2008	SIGMOD	5.742719e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,018	Dependency-Aware Reordering for Parallelizing Query Optimization in Multi-Core CPUs	2009	SIGMOD
2	2,131	Optimization Algorithms for Exploiting the Parallelism-Communication Tradeoff in Pipelined Parallelism	1994	VLDB
3	3,847	Operator Placement for In-Network Stream Query Processing	2005	PODS
4	2,337	Multi-dimensional Resource Scheduling for Parallel Queries	1996	SIGMOD
5	4,534	Shared Arrangements: practical inter-query sharing for streaming dataflows	2020	VLDB
6	2,068	Scheduling Problems in Parallel Query Optimization	1995	PODS
7	4,441	Optimization of Continuous Queries with Shared Expensive Filters	2007	PODS
8	6,901	Near-Optimal Algorithms for Shared Filter Evaluation in Data Stream Systems	2008	SIGMOD
9	813	Adaptive Ordering of Pipelined Stream Filters	2004	SIGMOD
10	4,421	Flow Algorithms for Two Pipelined Filter Ordering Problems	2006	PODS