A New Approach Based on Greedy Minimizing Algorithm for Solving Data Allocation Problem

Abstract

Distributed database functionality depends on sites responsible for the allocation of fragments. The aims of the data allocation problem (DAP) are to achieve the minimum execution time and ensure the lowest transaction cost of queries. The solution for this NP-hard problem based on numerical methods is computationally expensive. Despite the success of such heuristic algorithms as GA and PSO in solving DAP, the initial control parameters tuning, the relatively high convergence speed, and hard adaptations to the problem are the most important disadvantages of these methods. This paper presents a simple well-formed greedy algorithm to optimize the total transmission cost of each site-fragment dependency and each inner-fragment dependency. To evaluate the effect of the proposed method, more than 20 standard DAP problems were used. Experimental results showed that the proposed approach had better quality in terms of execution time and total cost.