Abstract
The Performance and the efficiency of a distributed database system depend highly on the way data are allocated to the sites. The NP-completeness of the data allocation problem and the large size of its real occurrence, call for employing a fast and scalable heuristic algorithm. In this paper, we address the data allocation problem in terms of minimizing two different types of data transmission across the network, i.e., data transmissions due to site-fragment dependencies and those caused by inter-fragment dependencies. We propose a new heuristic algorithm which is based on the ant colony optimization meta-heuristic, with regards to the applied strategies for query optimization and integrity enforcement. The goal is to design an efficient data allocation scheme to minimize the total transaction response time under memory capacity constraints of the sites. Experimental tests indicate that our algorithm is capable of producing near- optimal solutions within a reasonable time. The results also reveal the flexibility and scalability of the proposed algorithm.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Ahmad I, Karlapalem K, Kwok YK et al (2002) Evolutionary algorithms for allocating data in distributed database systems. Int J Distrib Parallel Databases 11(1): 5–32. doi:10.1023/A:1013324605452
Bell DA (1984) Difficult data placement problems. Comput J 27(4): 315–320
Bell D, Grimson J (1992) Distributed database systems. Addison-Wesley Longman Publishing Co., Inc, Boston
Brunstrom A, Leutenegger ST, Simha R (1995) Experimental evaluation of dynamic data allocation strategies in a distributed database with changing workloads. ICASE: Institute for Computer Applications in Science and Engineering
Buchholz S, Buchholz T (2004) Replica placement in adaptive content distribution networks. In: SAC ’04: proceedings of the 2004 ACM symposium on applied computing, Nicosia, pp 1705–1710
Ceri S, Pelagatti G (1984) Distributed databases principles and systems. McGraw-Hill, Inc., New York
Chu WW (1969) Optimal file allocation in a multiple computer system. IEEE Trans Comput 18(10): 885–889
Cook SA, Pachl JK, Pressman IS (2002) The optimal location of replicas in a network using a READ-ONE-WRITE-ALL policy. Distrib Comput 15(1): 57–66
Corcoran AL, Hale J (1994) A genetic algorithm for fragment allocation in a distributed database system. In: SAC ’94: proceedings of the 1994 ACM symposium on applied computing, Phoenix, pp 247–250
Daellenbach HG, George JA, McNickle DC (1983) Introduction to operations research techniques (2nd edn). Allyn and Bacon, Boston
Di Caro G, Dorigo M (1998) An adaptive multi-agent routing algorithm inspired by ants behavior. In: Proceedings of PART98-5th annual Australasian conference on parallel and real-time systems, Singapore, pp 261–272
Dorigo M, Stutzle T (2004) Ant colony optimization. MIT Press, Cambridge
Frieder O, Siegelmann HT (1997) Multiprocessor document allocation: A genetic algorithm approach. IEEE Trans Knowl Data Eng 9(4): 640–642
Gu X, Lin W (2006) Practically realizable efficient data allocation and replication strategies for distributed databases with buffer constraints. IEEE Trans Parallel Distrib Syst 17(9): 1001–1013
Ibrahim H (2005) Checking integrity constraints in a distributed database. Encyclopedia of database technologies and applications, pp 66–73
Koopmans TC, Beckmann MJ (1957) Assignment problems and the location of economics activities. Econometrica 25: 53–76
Laning LJ, Leonard MS (1983) File allocation in a distributed computer communication network. IEEE Trans Comput 32(3): 232–244
Lee Z, Su S, Lee C et al (2003) A heuristic genetic algorithm for solving resource allocation problems. Knowl Inf Syst 5(4): 503–511
Maniezzo V (1999) Exact and approximate nondeterministic tree-search procedures for the quadratic assignment problem. Inf J Comput 11(4): 358–369
Maniezzo V, Colorni A (1999) The ant system applied to the quadratic assignment problem. IEEE Trans Knowl Data Eng 11(5): 769–778
Mei A, Mancini LV, Jajodia S (2003) Secure dynamic fragment and replica allocation in large-scale distributed file systems. IEEE Trans Parallel Distrib Syst 14(9): 885–896
Menon S (2005) Allocating fragments in distributed databases. IEEE Trans Parallel Distrib Syst 16(7): 577–585
Merkle D, Middendorf M (2003) Ant colony optimization with global pheromone evaluation for scheduling a single machine. Appl Intell 18(1): 105–111
Navathe S, Ceri S, Wiederhold G et al (1984) Vertical partitioning algorithms for database design. ACM Trans Database Syst 9(4): 680–710
Ozsu T, Valduriez P (1999) Principles of distributed database systems, 2nd edition
Peterson C, Soderberg B (1989) A new method for mapping optimization problems onto neural networks. Int J Neural Syst 1(1): 3–22
Ram S, Marsten RE (1991) A model for database allocation incorporating a concurrency control mechanism. IEEE Trans Knowl Data Eng 3(3): 389–395
Sahni S, Gonzalez T (1976) P-complete approximation problems. J ACM 23(3): 555–565
Sarathy R, Shetty B, Sen A (1997) A constrained nonlinear 0–1 program for data allocation. Eur J Oper Res 102(3): 626–647
Shahabi C, Khan L, McLeod D (2000) A probe-based technique to optimize join queries in distributed internet databases. Knowl Inf Syst 2(3): 373–385
Stutzle T (1997) MAX-MIN ant system for the quadratic assignment problem. In: Technical report AIDA-97-4, FG Intellectik, FB Informatik, TU Darmstadt
Stutzle T, Dorigo M (1999) ACO algorithms for the quadratic assignment problem, pp 33–50
Taillard E (1995) Comparison of iterative searches for the quadratic assignment problem. Location Sci 3: 87–105
Ulus T, Uysal M (2003) Heuristic approach to dynamic data allocation in distributed database systems. Pakistan J Inform Technol 2(3): 231–239
Zhu Q, Tao Y, Zuzarte C (2005) Optimizing complex queries based on similarities of subqueries. Knowl Inf Syst 8(3): 350–373
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Karimi Adl, R., Rouhani Rankoohi, S.M.T. A new ant colony optimization based algorithm for data allocation problem in distributed databases. Knowl Inf Syst 20, 349–373 (2009). https://doi.org/10.1007/s10115-008-0182-y
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10115-008-0182-y