Parallel pipelined filter ordering with precedence constraints

Amol Deshpande, Lisa Hellerstein

    Research output: Contribution to journalArticle

    Abstract

    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.

    Original languageEnglish (US)
    Article number2344431
    JournalACM Transactions on Algorithms
    Volume8
    Issue number4
    DOIs
    StatePublished - Sep 2012

    ASJC Scopus subject areas

    • Mathematics (miscellaneous)

    Fingerprint Dive into the research topics of 'Parallel pipelined filter ordering with precedence constraints'. Together they form a unique fingerprint.

  • Cite this