Thumbnail
Access Restriction
Open

Author Benoit, Anne ♦ Casanova, Henri ♦ Rehn-Sonigo, Veronika ♦ Robert, Yves
Source Hyper Articles en Ligne (HAL)
Content type Text
File Format PDF
Language English
Subject Keyword Complexity results ♦ In-network stream processing ♦ Operator mapping ♦ Optimization ♦ Polynomial heuristics ♦ Trees of operators ♦ Traitement de flux en réseau ♦ Arbres d'opérateurs ♦ Heuristiques polynomiales ♦ Optimisation ♦ Placement d'opérateurs ♦ Résultats de complexité ♦ info ♦ Computer Science [cs]
Abstract In this paper we consider the operator mapping problem for in-networkstream processing applications. In-network stream processing consists inapplying a tree of operators in steady-state to multiple data objects thatare continually updated at various locations on a network. Examples ofin-network stream processing include the processing of data in a sensornetwork, or of continuous queries on distributed relational databases.We study the operator mapping problem in a “constructive” scenario, i.e.,a scenario in which one builds a platform dedicated to the applicationbuy purchasing processing servers with various costs and capabilities.The objective is to minimize the cost of the platform while ensuringthat the application achieves a minimum steady-state throughput.The first contribution of this paper is the formalization of a set of relevantoperator-placement problems as linear programs, and a proof thateven simple versions of the problem are NP-complete. Our second contributionis the design of several polynomial time heuristics, which areevaluated via extensive simulations and compared to theoretical boundsfor optimal solutions.
Educational Use Research
Learning Resource Type Report ♦ Article
Publisher Date 2008-06-01
Publisher Institution Laboratoire de l'informatique du parallélisme