Practical algorithms for execution engine selection in data flows

Georgia Kougka

doi:10.1016/j.future.2014.11.011

Return

Practical algorithms for execution engine selection in data flows

2015-04-01

PRE

Georgia Kougka *

Anastasios Gounaris

Kostas Tsichlas

DOI：10.1016/j.future.2014.11.011

Original

Original request for help

Save

Abstract

En 中文

Data-intensive flows are increasingly encountered in various settings, including business intelligence and scientific scenarios. At the same time, flow technology is evolving. Instead of resorting to monolithic solutions, current approaches tend to employ multiple execution engines, such as Hadoop clusters, traditional DBMSs, and stand-alone tools. We target the problem of allocating flow activities to specific heterogeneous and interdependent execution engines while minimizing the flow execution cost. To date, the state-of-the-art is limited to simple heuristics. Although the problem is intractable, we propose practical anytime solutions that are capable of outperforming those simple heuristics and yielding allocation plans in seconds even when optimizing large flows on ordinary machines. Moreover, we prove the NP-hardness of the problem in the generic case and we propose an exact polynomial solution for a specific form of flows, namely, linear flows. We thoroughly evaluate our solutions in both real-world and flows synthetic, and the results show the superiority of our solutions. Especially in real-world scenarios, we can decrease execution time up to more than 3 times. (C) 2014 Elsevier B.V. All rights reserved.

Keywords:

Data flows

Resource allocation

Heterogeneous machines

Anytime algorithms

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.