Evolutionary Algorithms for Query Op-timization in Distributed Database Sys-tems: A review

Zulfiqar ALI, Hafiza Maria KIRAN, Waseem SHAHZAD

Abstract


Evolutionary Algorithms are bio-inspired optimization problem-solving approaches that exploit principles of biological evolution. , such as natural selection and genetic inheritance. This review paper provides the application of evolutionary and swarms intelligence based query optimization strategies in Distributed Database Systems. The query optimization in a distributed environment is challenging task and hard problem. However, Evolutionary approaches are promising for the optimization problems. The problem of query optimization in a distributed database environment is one of the complex problems. There are several techniques which exist and are being used for query optimization in a distributed database. The intention of this research is to focus on how bio-inspired computational algorithms are used in a distributed database environment for query optimization. This paper provides working of bio-inspired computational algorithms in distributed database query optimization which includes genetic algorithms, ant colony algorithm, particle swarm optimization and Memetic Algorithms.

Keywords


Query optimization; Distributed data-base; Evolutionary Computation;Bio-inspired algorithms

Full Text:

PDF

References


Abbasi, A. A., & Younis, M. (2007). A survey on clustering algorithms for wireless sensor networks. Computer communications, 30(14-15), 2826-2841.

Ahmad, I., Karlapalem, K., Kwok, Y.-K., & So, S.-K. (2002). Evolutionary algorithms for allocating data in distributed database systems. Distributed and Parallel Databases, 11(1), 5-32.

Akkaya, K., & Younis, M. (2005). A survey on routing protocols for wireless sensor networks. Ad hoc networks, 3(3), 325-349.

Alcalá-Fdez, J., Sanchez, L., Garcia, S., del Jesus, M. J., Ventura, S., Garrell, J. M., . . . Rivas, V. M. (2009). KEEL: a software tool to assess evolutionary algorithms for data mining problems. Soft Computing, 13(3), 307-318.

Ali, Z., & Shahzad, W. (2011). Critical analysis of swarm intelligence based routing protocols in adhoc and sensor wireless networks. Paper presented at the Computer Networks and Information Technology (ICCNIT), 2011 International Conference on.

Ali, Z., & Shahzad, W. (2013). Analysis of routing protocols in ad hoc and sensor wireless networks based on swarm intelligence. International Journal of Networks and Communications, 3(1), 1-11.

Ali, Z., & Shahzad, W. (2017). EPACO: a novel ant colony optimization for emerging patterns based classification. Cluster Computing, 1-15.

Aljanaby, A., Abuelrub, E., & Odeh, M. (2005). A Survey of Distributed Query Optimization. Int. Arab J. Inf. Technol., 2(1), 48-57.

Allahverdi, A., & Al-Anzi, F. S. (2006). A PSO and a Tabu search heuristics for the assembly scheduling problem of the two-stage distributed database application. Computers & Operations Research, 33(4), 1056-1080.

Back, T. (1996). Evolutionary algorithms in theory and practice: evolution strategies, evolutionary programming, genetic algorithms: Oxford university press.

Banković, Z., Stepanović, D., Bojanić, S., & Nieto-Taladriz, O. (2007). Improving network security using genetic algorithm approach. Computers & Electrical Engineering, 33(5-6), 438-451.

Bara’a, A. A., & Khalil, E. A. (2012). A new evolutionary based routing protocol for clustered heterogeneous wireless sensor networks. Applied Soft Computing, 12(7), 1950-1957.

Blum, C., & Roli, A. (2003). Metaheuristics in combinatorial optimization: Overview and conceptual comparison. ACM Computing Surveys (CSUR), 35(3), 268-308.

Bose, R. (2009). Advanced analytics: opportunities and challenges. Industrial Management & Data Systems, 109(2), 155-172.

Bounsaythip, C., & Alander, J. T. (1997). Genetic algorithms in image processing-a review. Paper presented at the Proceedings of the Third Nordic Workshop on Genetic Algorithms and their Applications (3NWGA).

Burbank, J. L. (2008). Security in cognitive radio networks: The required evolution in approaches to wireless network security. Paper presented at the Cognitive Radio Oriented Wireless Networks and Communications, 2008. CrownCom 2008. 3rd International Conference on.

Crainic, T. G., & Toulouse, M. (2003). Parallel strategies for meta-heuristics Handbook of metaheuristics (pp. 475-513): Springer.

Das, S., Abraham, A., & Konar, A. (2008). Swarm intelligence algorithms in bioinformatics Computational Intelligence in Bioinformatics (pp. 113-147): Springer.

Deulkar, K., & Narvekar, M. (2015). An Improved Memetic Algorithm for Web Search. Procedia Computer Science, 45, 52-59.

Deutsch, J. (2003). Evolutionary algorithms for finding optimal gene sets in microarray prediction. Bioinformatics, 19(1), 45-52.

Dokeroglu, T., Tosun, U., & Cosar, A. (2012). Particle Swarm Intelligence as a new heuristic for the optimization of distributed database queries. Paper presented at the Application of Information and Communication Technologies (AICT), 2012 6th International Conference on.

Dong, H., & Liang, Y. (2007). Genetic algorithms for large join query optimization. Paper presented at the Proceedings of the 9th annual conference on Genetic and evolutionary computation.

Dorigo, M. (1992). Optimization, learning and natural algorithms. Ph. D. Thesis, Politecnico di Milano, Italy.

Dorigo, M., Maniezzo, V., & Colorni, A. (1996). Ant system: optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 26(1), 29-41.

Dorigo, M., Maniezzo, V., Colorni, A., & Maniezzo, V. (1991). Positive feedback as a search strategy.

Doshi, P., & Raisinghani, V. (2011). Review of dynamic query optimization strategies in distributed database. Paper presented at the Electronics Computer Technology (ICECT), 2011 3rd International Conference on.

Eberhart, R. C., & Kennedy, J. (1995). Particle swarm optimization. Paper presented at the Proceedings of the IEEE international conference on neural networks.

Elbeltagi, E., Hegazy, T., & Grierson, D. (2005). Comparison among five evolutionary-based optimization algorithms. Advanced engineering informatics, 19(1), 43-53.

Elbeltagi, E., Hegazy, T., & Grierson, D. (2007). A modified shuffled frog-leaping optimization algorithm: applications to project management. Structure and Infrastructure Engineering, 3(1), 53-60.

Fogel, L. J. (1999). Intelligence through simulated evolution: forty years of evolutionary programming: John Wiley & Sons, Inc.

Freitas, A. A. (2005). Evolutionary algorithms for data mining Data mining and knowledge discovery handbook (pp. 435-467): Springer.

Garcia-Teodoro, P., Diaz-Verdejo, J., Maciá-Fernández, G., & Vázquez, E. (2009). Anomaly-based network intrusion detection: Techniques, systems and challenges. computers & security, 28(1-2), 18-28.

Ghatasheh, N. (2014). Business analytics using random forest trees for credit risk prediction: A comparison study. International Journal of Advanced Science and Technology, 72(2014), 19-30.

Goli, M., & Rankoohi, S. M. T. R. (2012). A new vertical fragmentation algorithm based on ant collective behavior in distributed database systems. Knowledge and Information Systems, 30(2), 435-455.

Hill, D. L., Batchelor, P. G., Holden, M., & Hawkes, D. J. (2001). Medical image registration. Physics in medicine & biology, 46(3), R1.

Holland, J. H. (1975). Adaptation in natural and artificial systems. An introductory analysis with application to biology, control, and artificial intelligence. Ann Arbor, MI: University of Michigan Press, 439-444.

Ilyas, I. F., Beskales, G., & Soliman, M. A. (2008). A survey of top-k query processing techniques in relational database systems. ACM Computing Surveys (CSUR), 40(4), 11.

Jabbar, M. A., Deekshatulu, B. L., & Chandra, P. (2013). Heart disease prediction system using associative classification and genetic algorithm. arXiv preprint arXiv:1303.5919.

Jourdan, D. B., & de Weck, O. L. (2004). Layout optimization for a wireless sensor network using a multi-objective genetic algorithm. Paper presented at the Vehicular technology conference, 2004. VTC 2004-Spring. 2004 IEEE 59th.

Kaisler, S., Armour, F., Espinosa, J. A., & Money, W. (2013). Big data: Issues and challenges moving forward. Paper presented at the System sciences (HICSS), 2013 46th Hawaii international conference on.

Klein, S., Staring, M., & Pluim, J. P. (2007). Evaluation of optimization methods for nonrigid medical image registration using mutual information and B-splines. IEEE transactions on image processing, 16(12), 2879-2890.

Kleinschmidt, J. H. (2009). Genetic Algorithms for Wireless Sensor Networks Encyclopedia of Artificial Intelligence (pp. 755-758): IGI Global.

Koza, J. R. (1992). Genetic Programming II, Automatic Discovery of Reusable Subprograms: MIT Press, Cambridge, MA.

Kumar, T. V., Kumar, A., & Singh, R. (2013). Distributed query plan generation using particle swarm optimization. International Journal of Swarm Intelligence Research (IJSIR), 4(3), 58-82.

Larrañaga, P., & Lozano, J. A. (2001). Estimation of distribution algorithms: A new tool for evolutionary computation (Vol. 2): Springer Science & Business Media.

Maulik, U. (2009). Medical image segmentation using genetic algorithms. IEEE Transactions on information technology in biomedicine, 13(2), 166-173.

Melita, L., Gopinath, G., & Sebsibe, H. (2015). Web Search Query Result Optimization based on Memetic Algorithms: A Comparative Study. International Journal of Computer Science Issues (IJCSI), 12(3), 240.

MMICT, , B., MMU, H., Garg, I. A., & Juneja, I. D. (2012). A Comparison and analysis of various extended techniques of query optimization.

Moscato, P. (1989). On evolution, search, optimization, genetic algorithms and martial arts: Towards memetic algorithms. Caltech concurrent computation program, C3P Report, 826, 1989.

Novak, P. K., Lavrač, N., & Webb, G. I. (2009). Supervised descriptive rule discovery: A unifying survey of contrast set, emerging pattern and subgroup mining. Journal of Machine Learning Research, 10(Feb), 377-403.

Ouzzani, M., & Bouguettaya, A. (2004). Query processing and optimization on the web. Distributed and Parallel Databases, 15(3), 187-218.

Ozsu, M. T., & Valduriez, P. (1994). Distributed data management: unsolved problems and new issues. Readings in Distributed Computing Systems, 512-544.

Padia, S., Khulge, S., Gupta, A., & Khadilikar, P. Query Optimization Strategies in Distributed Databases.

Parker, J. R. (2010). Algorithms for image processing and computer vision: John Wiley & Sons.

Rini, D. P., Shamsuddin, S. M., & Yuhaniz, S. S. (2011). Particle swarm optimization: technique, system and challenges. International Journal of Computer Applications, 14(1), 19-26.

Salimi, H. (2015). Stochastic fractal search: a powerful metaheuristic algorithm. Knowledge-Based Systems, 75, 1-18.

Senthilkumaran, N., & Rajesh, R. (2009). Edge detection techniques for image segmentation–a survey of soft computing approaches. International journal of recent trends in engineering, 1(2), 250-254.

Sevinç, E., & Coşar, A. (2010). An evolutionary genetic algorithm for optimization of distributed database queries. The Computer Journal, 54(5), 717-725.

Shahabi, C., Khan, L., & McLeod, D. (2000). A probe-based technique to optimize join queries in distributed internet databases. Knowledge and information systems, 2(3), 373-385.

Shahzad, W. (2010). Classification and Associative Classification Rule Discovery Using Ant Colony Optimization. National University.

Shahzad, W., & Baig, A. (2011). Hybrid associative classification algorithm using ant colony optimization. International Journal of Innovative Computing, Information and Control, 7(12), 6815-6826.

Silberschatz, A., Korth, H. F., & Sudarshan, S. (1997). Database system concepts (Vol. 4): McGraw-Hill New York.

Sohal, M., Singh, A., & Virk, R. S. (2015). A Framework For Optimizing Distributed Database Queries Based On Stochastic Fractal Search. Int. J. Comp. Sc. and Mob. Computing (JCSMC), 4(6), 544-551.

Soliman, O. S., & Adly, A. (2012). Bio-inspired algorithm for classification association rules. Paper presented at the Informatics and Systems (INFOS), 2012 8th International Conference on.

Stanchev, L. (2001). Semantic Data Control in Distributed Database Environment. Survey Paper for CS748T Distributed Database Management, University of Waterloo, 1-25.

Tiwari, M. P., & Chande, S. V. (2013). Query optimization strategies in distributed databases. International Journal of Advances in Engineering Sciences, 3(3), 23-29.

Tiwari, P., & Chande, S. V. (2013). Optimization of distributed database queries using hybrids of Ant colony optimization algorithm. International Journal of Advanced Research in Computer Science and Software Engineering.

Ulus, T., & Uysal, M. (2003). Heuristic approach to dynamic data allocation in distributed database systems. Pakistan Journal of Information and Technology, 2(3), 231-239.

Umar, Y. R., & Welekar, A. R. (2014). Query Optimization in Distributed Database: A Review. Query Optimization in Distributed Database: A.

Wagh, A., & Nemade, V. (2017). Query Optimization using Modified Ant Colony Algorithm. International Journal of Computer Applications, 167(2).

Wang, Z., & Sun, X. (2008). An efficient web query optimization algorithm based on LDA and MA. Paper presented at the MultiMedia and Information Technology, 2008. MMIT'08. International Conference on.

Zhou, Z. (2007). Using heuristics and genetic algorithms for large-scale database query optimization. Journal of Information and Computing Science, 2(4), 261-280.




DOI: http://dx.doi.org/10.14201/ADCAIJ201873115128





Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.

Clarivate Analytics