Dynamic Programming with Ant Colony Optimization Metaheuristic for Optimization of Distributed Database Queries

Date

2011-09-28

Author

Dokeroglu, Tansel
Coşar, Ahmet

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

146
views

0
downloads

In this paper, we introduce and evaluate a new query optimization algorithm based on Dynamic Programming (DP) and Ant Colony Optimization (ACO) metaheuristic for distributed database queries. DP algorithm is widely used for relational query optimization, however its memory, and time requirements are very large for the query optimization problem in a distributed database environment which is an NP-hard combinatorial problem. Our aim is to combine the power of DP with heuristic approaches so that we can have a polynomial time approximation algorithm based on a constructive method. DP and ACO algorithms together provide execution plans that are very close to the best performing solutions, and achieve this in polynomial time. This makes our algorithm viable for large multi-way join queries.

Subject Keywords

Query optimization, Dynamic programming, Ant colony, Metaheuristic

URI

https://hdl.handle.net/11511/31205

DOI

https://doi.org/10.1007/978-1-4471-2155-8_13

Conference Name

26th Annual International Symposium on Computer and Information Science

Collections

Graduate School of Natural and Applied Sciences, Conference / Seminar

Suggestions

OpenMETU
Core

Integer Linear Programming Solution for the Multiple Query Optimization Problem Dokeroglu, Tansel; Bayir, Murat Ali; Coşar, Ahmet (2014-10-28) Multiple Query Optimization (MQO) is a technique for processing a batch of queries in such a way that shared tasks in these queries are executed only once, resulting in significant savings in the total evaluation. The first phase of MQO requires producing alternative query execution plans so that the shared tasks between queries are identified and maximized. The second phase of MQO is an optimization problem where the goal is selecting exactly one of the alternative plans for each query to minimize the tota...
Using object-oriented materialized views to answer selection-based complex queries Alhajj, R; Polat, Faruk (1999-09-01) Presented in this paper is a model that utilizes existing materialized views to handle a wide range of complex selection-based queries, including linear recursive queries. Such queries are complex because it is almost impossible for naive users to predict the formulation of their predicate expressions. Object variables bound to objects in the result of a query are allowed to appear in the predicate of that query. Also, the predicate definition is extended to make it possible to have in the output only a sub...
Improving the performance of Hadoop/Hive by sharing scan and computation tasks Özal, Serkan; Toroslu, İsmail Hakkı; Doğaç, Asuman; Department of Computer Engineering (2013) MapReduce is a popular model of executing time-consuming analytical queries as a batch of tasks on large scale data. During simultaneous execution of multiple queries, many oppor- tunities can arise for sharing scan and/or computation tasks. Executing common tasks only once can reduce the total execution time of all queries remarkably. Therefore, we propose to use Multiple Query Optimization (MQO) techniques to improve the overall performance of Hadoop Hive, an open source SQL-based distributed warehouse sy...
Stochastic dynamic programming based resource allocation for multi target tracking for electronically steered antenna radar / Uzun, Çağlar; Demirekler, Mübeccel; Department of Electrical and Electronics Engineering (2015) In this work, the concept of sensor management is introduced and stochastic dynamic programming based resource allocation approach is proposed to track multiple targets. The core of this approach is to use Lagrange relaxation for decreasing the state space dimension. By this approximation, the overall problem is separated into components instead of using joint Markov model to optimize large scale stochastic control problem. The aim of this study is to adaptively allocate radar resources in an optimal way in...
Continuous optimization approaches for clustering via minimum sum of squares Akteke-Ozturk, Basak; Weber, Gerhard Wilhelm; Kropat, Erik (2008-05-23) In this paper, we survey the usage of semidefinite programming (SDP), and nonsmooth optimization approaches for solving the minimum sum of squares problem which is of fundamental importance in clustering. We point out that the main clustering idea of support vector clustering (SVC) method could be interpreted as a minimum sum of squares problem and explain the derivation of semidefinite programming and a nonsmooth optimization formulation for the minimum sum of squares problem. We compare the numerical resu...

Citation Formats

T. Dokeroglu and A. Coşar, “Dynamic Programming with Ant Colony Optimization Metaheuristic for Optimization of Distributed Database Queries,” presented at the 26th Annual International Symposium on Computer and Information Science, Royal Soc London, London, ENGLAND, 2011, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/31205.