TY - JOUR

T1 - Parallel pipelined filter ordering with precedence constraints

AU - Deshpande, Amol

AU - Hellerstein, Lisa

N1 - Copyright:
Copyright 2012 Elsevier B.V., All rights reserved.

PY - 2012/9

Y1 - 2012/9

N2 - In the parallel pipelined filter ordering problem, we are given a set of n filters that run in parallel. The filters need to be applied to a stream of elements, to determine which elements pass all filters. Each filter has a rate limit ri on the number of elements it can process per unit time, and a selectivity pi, which is the probability that a random element will pass the filter. The goal is to maximize throughput. This problem appears naturally in a variety of settings, including parallel query optimization in databases and query processing over Web services. We present an O(n3) algorithm for this problem, given tree-structured precedence constraints on the filters. This extends work of Condon et al. [2009] and Kodialam [2001], who presented algorithms for solving the problem without precedence constraints. Our algorithm is combinatorial and produces a sparse solution. Motivated by join operators in database queries, we also give algorithms for versions of the problem in which "filter" selectivities may be greater than or equal to 1. We prove a strong connection between the more classical problem of minimizing total work in sequential filter ordering (A), and the parallel pipelined filter ordering problem (B). More precisely, we prove that A is solvable in polynomial time for a given class of precedence constraints if and only if B is as well. This equivalence allows us to show that B is NP-Hard in the presence of arbitrary precedence constraints (since A is known to be NP-Hard in that setting.

AB - In the parallel pipelined filter ordering problem, we are given a set of n filters that run in parallel. The filters need to be applied to a stream of elements, to determine which elements pass all filters. Each filter has a rate limit ri on the number of elements it can process per unit time, and a selectivity pi, which is the probability that a random element will pass the filter. The goal is to maximize throughput. This problem appears naturally in a variety of settings, including parallel query optimization in databases and query processing over Web services. We present an O(n3) algorithm for this problem, given tree-structured precedence constraints on the filters. This extends work of Condon et al. [2009] and Kodialam [2001], who presented algorithms for solving the problem without precedence constraints. Our algorithm is combinatorial and produces a sparse solution. Motivated by join operators in database queries, we also give algorithms for versions of the problem in which "filter" selectivities may be greater than or equal to 1. We prove a strong connection between the more classical problem of minimizing total work in sequential filter ordering (A), and the parallel pipelined filter ordering problem (B). More precisely, we prove that A is solvable in polynomial time for a given class of precedence constraints if and only if B is as well. This equivalence allows us to show that B is NP-Hard in the presence of arbitrary precedence constraints (since A is known to be NP-Hard in that setting.

UR - http://www.scopus.com/inward/record.url?scp=84870226281&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84870226281&partnerID=8YFLogxK

U2 - 10.1145/2344422.2344431

DO - 10.1145/2344422.2344431

M3 - Article

AN - SCOPUS:84870226281

SN - 1549-6325

VL - 8

JO - ACM Transactions on Algorithms

JF - ACM Transactions on Algorithms

IS - 4

M1 - 2344431

ER -