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

  • Zulfiqar Ali
    The University of Lahore, Lahore, Pakistan. zulfiqar.ali[at]cs.uol.edu.pk
  • Hafiza Maria Kiran
    The University of Lahore, Lahore.
  • Waseem Shahzad
    National University of Computer and Emerging Sciences

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.
  • Referencias
  • Cómo citar
  • Del mismo autor
  • Métricas
Abbasi, A. A., & Younis, M. (2007). A survey on clustering algorithms for wireless sensor networks. Computer communications, 30(14-15), 2826-2841. - https://doi.org/10.1016/j.comcom.2007.05.024

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. - https://doi.org/10.1023/A:1013324605452

Akkaya, K., & Younis, M. (2005). A survey on routing protocols for wireless sensor networks. Ad hoc networks, 3(3), 325-349. - https://doi.org/10.1016/j.adhoc.2003.09.010

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. - https://doi.org/10.1007/s00500-008-0323-y

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. - https://doi.org/10.1109/ICCNIT.2011.6020945

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. - https://doi.org/10.1007/s10586-017-0894-4

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. - https://doi.org/10.1016/j.cor.2004.09.002

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. - https://doi.org/10.1016/j.compeleceng.2007.05.010

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. - https://doi.org/10.1016/j.asoc.2011.04.007

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

Bose, R. (2009). Advanced analytics: opportunities and challenges. Industrial Management & Data Systems, 109(2), 155-172. - https://doi.org/10.1108/02635570910930073

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. - https://doi.org/10.1109/CROWNCOM.2008.4562536

Crainic, T. G., & Toulouse, M. (2003). Parallel strategies for meta-heuristics Handbook of metaheuristics (pp. 475-513): Springer. - https://doi.org/10.1007/0-306-48056-5_17

Das, S., Abraham, A., & Konar, A. (2008). Swarm intelligence algorithms in bioinformatics Computational Intelligence in Bioinformatics (pp. 113-147): Springer. - https://doi.org/10.1007/978-3-540-76803-6_4

Deulkar, K., & Narvekar, M. (2015). An Improved Memetic Algorithm for Web Search. Procedia Computer Science, 45, 52-59. - https://doi.org/10.1016/j.procs.2015.03.083

Deutsch, J. (2003). Evolutionary algorithms for finding optimal gene sets in microarray prediction. Bioinformatics, 19(1), 45-52. - https://doi.org/10.1093/bioinformatics/19.1.45

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. - https://doi.org/10.1109/ICAICT.2012.6398467

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. - https://doi.org/10.1145/1276958.1277193

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. - https://doi.org/10.1109/3477.484436

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. - https://doi.org/10.1109/ICECTECH.2011.5942069

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. - https://doi.org/10.1016/j.aei.2005.01.004

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. - https://doi.org/10.1080/15732470500254535

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. - https://doi.org/10.1007/0-387-25465-X_20

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. - https://doi.org/10.1016/j.cose.2008.08.003

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. - https://doi.org/10.14257/ijast.2014.72.02

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. - https://doi.org/10.1007/s10115-011-0384-6

Hill, D. L., Batchelor, P. G., Holden, M., & Hawkes, D. J. (2001). Medical image registration. Physics in medicine & biology, 46(3), R1. - https://doi.org/10.1088/0031-9155/46/3/201

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. - https://doi.org/10.1145/1391729.1391730

Jabbar, M. A., Deekshatulu, B. L., & Chandra, P. (2013). Heart disease prediction system using associative classification and genetic algorithm. arXiv preprint arXiv:1303.5919. - https://doi.org/10.1109/iMac4s.2013.6526381

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. - https://doi.org/10.1109/VETECS.2004.1391366

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. - https://doi.org/10.1109/HICSS.2013.645

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. - https://doi.org/10.1109/TIP.2007.909412

Kleinschmidt, J. H. (2009). Genetic Algorithms for Wireless Sensor Networks Encyclopedia of Artificial Intelligence (pp. 755-758): IGI Global. - https://doi.org/10.4018/978-1-59904-849-9.ch112

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. - https://doi.org/10.4018/ijsir.2013070104

Larrañaga, P., & Lozano, J. A. (2001). Estimation of distribution algorithms: A new tool for evolutionary computation (Vol. 2): Springer Science & Business Media. - https://doi.org/10.1007/978-1-4615-1539-5

Maulik, U. (2009). Medical image segmentation using genetic algorithms. IEEE Transactions on information technology in biomedicine, 13(2), 166-173. - https://doi.org/10.1109/TITB.2008.2007301

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. - https://doi.org/10.1023/B:DAPD.0000018574.71588.06

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. - https://doi.org/10.5120/1810-2331

Salimi, H. (2015). Stochastic fractal search: a powerful metaheuristic algorithm. Knowledge-Based Systems, 75, 1-18. - https://doi.org/10.1016/j.knosys.2014.07.025

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. - https://doi.org/10.1109/ARTCom.2009.219

Sevinç, E., & Co?ar, A. (2010). An evolutionary genetic algorithm for optimization of distributed database queries. The Computer Journal, 54(5), 717-725. - https://doi.org/10.1093/comjnl/bxp130

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. - https://doi.org/10.1007/PL00011648

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. - https://doi.org/10.3923/itj.2003.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). - https://doi.org/10.5120/ijca2017914185

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. - https://doi.org/10.1109/MMIT.2008.62

Zhou, Z. (2007). Using heuristics and genetic algorithms for large-scale database query optimization. Journal of Information and Computing Science, 2(4), 261-280.
Ali, Z., Kiran, H. M., & Shahzad, W. (2018). Evolutionary Algorithms for Query Op-timization in Distributed Database Sys-tems: A review. ADCAIJ: Advances in Distributed Computing and Artificial Intelligence Journal, 7(3), 115–128. https://doi.org/10.14201/ADCAIJ201873115128

Downloads

Download data is not yet available.

Author Biographies

Zulfiqar Ali

,
The University of Lahore, Lahore, Pakistan.
Department of Computer Science and Information Technology

Hafiza Maria Kiran

,
The University of Lahore, Lahore.
Department of Computer Science and Information Technology

Waseem Shahzad

,
National University of Computer and Emerging Sciences
Department of Computer Science ,National University of Computer and Emerging Sciences
+