Abstract | ||
---|---|---|
While recurring queries over evolving data are the bedrock of the analytical applications, resources demanded to process a large amount of data for each recurring execution can be a fatal bottleneck in cost-sensitive cloud computing environments. It is thus imperative to design a system responsive to users’ preferences regarding how resources should be utilized. In this work, we propose PRO, a preference-aware recurring query processing system that optimizes recurring query executions complying with user preferences. First, we show that finding an optimal execution configuration is an NP-complete problem due to the cost interdependencies between consecutive executions. We propose an execution relation graph (ERG) model that effectively incorporates these dependencies between executions. This model enables us to transform our problem into a well-known graph problem. We then design a graph-based approach (called PRO-OPT) leveraging dynamic programming and pruning techniques with pseudo-polynomial complexity. Moreover, we introduce adaptive re-optimization techniques that tackle the challenge of fluctuating stream workloads. Our experimental evaluation on a 40-node cluster confirms that PRO consistently outperforms state-of-the-art solutions under a rich variety of circumstances by 9 fold on the Wikipedia datasets. |
Year | DOI | Venue |
---|---|---|
2016 | 10.1145/2983323.2983664 | ACM International Conference on Information and Knowledge Management |
Keywords | Field | DocType |
recurring query,preference-aware,execution selection | Interdependence,Query optimization,Data mining,Graph problem,Dynamic programming,Graph,Bottleneck,Computer science,Cloud computing | Conference |
Citations | PageRank | References |
0 | 0.34 | 10 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Zhongfang Zhuang | 1 | 8 | 3.54 |
Chuan Lei | 2 | 20 | 7.54 |
Elke A. Rundensteiner | 3 | 4076 | 700.65 |
Mohamed Y. Eltabakh | 4 | 355 | 26.13 |