No Access

Materialized View Selection for Query Performance Enhancement Using Stochastic Ranking Based Cuckoo Search Algorithm

Anjana Gosain

University School of Info. Comm. and Technology, GGSIP University, Sector 16C, Dwarka, New Delhi-110078, India

E-mail Address: anjana_gosain@hotmail.com

Search for more papers by this author

and

Kavita Sachdeva

Shree Guru Gobind Singh Tricentenary University, Budhera, Gurugram-Badli road, Gurugram, Haryana-12250, India

E-mail Address: kavitasachdeva4@gmail.com

Corresponding author.

Search for more papers by this author

https://doi.org/10.1142/S0218539320500084Cited by:6 (Source: Crossref)

Abstract

Materialized view selection (MVS) improves the query processing efficiency and performance for making decisions effectively in a data warehouse. This problem is NP-hard and constrained optimization problem which involves space and cost constraint. Various optimization algorithms have been proposed in literature for optimal selection of materialized views. Few works exist for handling the constraints in MVS. In this study, authors have proposed the Cuckoo Search Algorithm (CSA) for optimization and Stochastic Ranking (SR) for handling the constraints in solving the MVS problem. The motivation behind integrating CS with SR is that fewer parameters have to be fine tuned in CS algorithm than in genetic and Particle Swarm Optimization (PSO) algorithm and the ranking method of SR handles the constraints effectively. For proving the efficiency and performance of our proposed algorithm Stochastic Ranking based Cuckoo Search Algorithm for Materialized View Selection (SRCSAMVS), it has been compared with PSO, genetic algorithm and the constrained evolutionary optimization algorithm proposed by Yu et al. SRCSAMVS outperforms in terms of query processing cost and scalability of the problem.

Keywords:

References

1. J. Han and M. Kamber , Data Mining: Concepts and Techniques (Morgan Kaufman, San Francisco, CA, USA, 2001). Google Scholar
2. S. Morse and D. Isaac , Parallel Systems in the Data Warehouse (Prentice Hall, Upper saddle River, NJ, USA, 1998). Google Scholar
3. H. Jain and A. Gosain , A comprehensive study of view maintenance approaches in data warehousing evolution, ACM SIGSOFT Softw. Eng. Notes 37(5) (2012) 1–8. Google Scholar
4. A. Nica and E. A. Rundensteiner , View maintenance after view synchronization, International Database Engineering and Application Symp. (2001), pp. 213–215. Google Scholar
5. Z. Bellahsene , Schema evolution in data warehouses, Knowl. Inf. Syst. 4 (2002) 283–304. Google Scholar
6. H. Gupta and I. S. Mumick , Selection of views to materialize under a maintenance cost constraint, in Proc. the 7th International Conference on Database Theory (Springer-Verlag, 1999), pp. 453–470. Google Scholar
7. X. Y. Jeffrey, X. Yao, C.-H. Choi and G. Gou , Materialized view selection as constrained evolutionary optimization, IEEE Trans. Syst. Man Cybernetics C Appl. Rev. 33(4) (2003) 458–467. Web of Science, Google Scholar
8. V. Harinarayan, A. Rajaraman and J. D. Ullman , Implementing data cubes efficiently, in Proc. 1996 ACM SIGMOD International Conference on Management of Data, Montreal, Que., Canada (1996), pp. 205–216. Google Scholar
9. J. Yang, K. Karlapalem and Q. Li , A framework for designing materialized views in data warehousing environment, in Proc. 17th International Conference on Distributed Computing Systems (1997), pp. 458–465. Google Scholar
10. H. Gupta and I. S. Mumick , Selection of views to materialize in a data warehouse, IEEE Trans. Knowl. Data Eng. 17(1) (2005) 24–43. Web of Science, Google Scholar
11. I. Mami, R. Coletta and Z. Bellahsene , Modeling view selection as a constraint satisfaction problem, in Database and Expert Systems Applications, Vol. 6861 (Springer Berlin Heidelberg, 2011), pp. 396–410. Google Scholar
12. Tamiozzo, S. Ayelén and J. M. Ale , A solution to the materialized view selection problem in data warehousing, Congreso Argentino de Ciencias de la Computación (Buenos Aires, 2014). Google Scholar
13. Horng, J. T. Yu, J. Chang, B. J. Lin and C. Y. Kao , Materialized view selection using genetic algorithms in a data warehouse system, in CEC 99, Proceedings of the 1999 Congress on Evolutionary Computation, Vol. 3 (IEEE, 1999). Google Scholar
14. T. V. Vijay Kumar and S. Kumar , Materialized view selection using differential evolution, Int. J. Innov. Comput. Appl. 6(2) (2014) 102–113. Google Scholar
15. A. Gosain and Heena , Materialized cube selection using particle swarm optimization algorithm, 7th International Conference on Communication, Computing and Virtualization, Vol. 79 (Elsevier, 2016), pp. 2–7. Google Scholar
16. X. Sun and W. Ziqiang , An efficient materialized views selection algorithm based on PSO, in Proc. International Workshop on Intelligent Systems and Applications, Wuhan, China (ISA 2009). Google Scholar
17. T. V. Vijay Kumar and B. Arun , Materialized view selection using improvement based bee colony optimization, Int. J. Softw. Sci. Comput. Intell. 7(4) (2015) 35–61. Google Scholar
18. M. X. Song and L. Gao , An ant colony based algorithm for optimal selection of materialized view, Int. Conf. on Intelligent Computing and Integrated Systems (ICISS) (2010), pp. 534–546. Google Scholar
19. H. Gupta , Selection of views to materialize in a data warehouse, in Proc. 6th International Conference on Database Theory (Springer-Verlag, 1997), pp. 98–112. Google Scholar
20. H. Gupta, V. Harinarayan, A. Rajaraman and J. D. Ullman , Index selection for OLAP’, in Proc. 13th International Conference on Data Engineering (1997), pp. 208–219. Google Scholar
21. A. Shukla, P. Deshpande and J. F. Naughton , Materialized view selection for multidimensional datasets, in Proc. 24th International Conference on Very Large Data Bases (1998), pp. 488–499. Google Scholar
22. Z. Wang and D. Zhang , Optimal genetic view selection algorithm under space constraint, Int. J. Inf. Technol. 11(5) (2005) 44–51. Google Scholar
23. M. Lee and J. Hammer , Speeding up materialized view selection in data warehouses using a randomized algorithm, Int. J. Cooperative Inf. Syst. 10(1) (2001) 327–353. Link, Web of Science, Google Scholar
24. X.-S. Yang and S. Deb , Cuckoo search via Lévy flights, in Proc. World Congress on Nature & Biologically Inspired Computing, USA (IEEE Publications, 2009), pp. 210–214. Google Scholar
25. K. Chandrasekaran and S. P. Simon , Multi-objective scheduling problem: Hybrid approach using fuzzy assisted cuckoo search algorithm, Swarm Evol. Comput. 5 (2012) 1–16. Web of Science, Google Scholar
26. A. H. Gandomi, X. S. Yang and A. H. Alavi , Cuckoo search algorithm: A metaheuristic approach to solve structural optimization problems, Eng. Computers 29 (2013) 17–35. Web of Science, Google Scholar
27. J. Piechocki, D. Ambroziak, A. Palkowski and G. Redlarski , Use of modified cuckoo search algorithm in the design process of integrated power systems for modern and energy self-sufficient farms, Appl. Energy 114 (2013) 901–908. Web of Science, Google Scholar
28. A. K. Bhandari, V. Soni, A. Kumar and G. K. Singh , Cuckoo search algorithm based satellite image contrast and brightness enhancement using DWT-SVD, ISA Trans. 53(4) (2014) 1286–1296. Web of Science, Google Scholar
29. A. K. Bhandari, V. K. Singh, A. Kumar and G. K. Singh , Cuckoo search algorithm and wind driven optimization based study of satellite image segmentation for multilevel thresholding using Kapur’s entropy, Exp. Syst. Appl. 41 (2014) 3538–3560. Web of Science, Google Scholar
30. A. C. Coello Coello , Theoretical and numerical constraint-handling techniques used with evolutionary algorithms: A survey of the state of the art, in Computer Methods in Applied Mechanics and Engineering (Elsevier, 2002), pp. 1245–1287. Google Scholar
31. A. C. Coello Coello , Constraint-handling techniques used with evolutionary algorithms, Genetic and Evolutionary Computation Conference GECCO’12, ACM (2012), pp. 849–872. Google Scholar
32. T. P. Runarsson and X. Yao , Stochastic ranking for constrained evolutionary optimization, IEEE Trans. Evol. Comput. 4 (2001) 284–294. Web of Science, Google Scholar
33. M. C. Hung, M. L. Huang, D. L. Yang and N. L. Hsueh , Efficient approaches for materialized views selection in a data warehouse, Inf. Sci. Elsevier 177(6) (2007) 1333–1348. Web of Science, Google Scholar
34. O’Neil, E. Patrick, J. Elizabeth O’Neil and X. Chen, The star schema benchmark (SSB)’ Pat. (2007). Google Scholar
35. W. Y. Lin and I. C. Kuo , A genetic selection algorithm for OLAP data cubes, Knowl. Inf. Syst. 6(1) (2004) 83–102. Web of Science, Google Scholar
36. D. B. Fogel , Evolutionary Computation. Toward a New Philosophy of Machine Intelligence (The Institute of Electrical and Electronic Engineers, New York, 1995). Google Scholar
37. Z. Michalewicz , Genetic Algorithms + Data Structures = Evolution Programs, 2nd edn. (Springer, Berlin, 1992). Google Scholar
38. V. W. Porto, N. Saravanan, D. Waagen and A. E. Eiben , Evolutionary programming, in Proc. Seventh Annual Conference on Evolutionary Programming, Lecture Notes in Computer Science, Vol. 1447 (Springer, San Diego, CA, 1998). Google Scholar
39. Z. Fan, J. Liu, T. Sorensen and P. Wang , Improved differential evolution based on stochastic ranking for robust layout synthesis of MEMS components, IEEE Trans. Ind. Electronics 56(4) (2009) 937–942. Web of Science, Google Scholar
40. G. Toscano, G. Larraga, R. Landa and G. Leguizamon , On the use of stochastic ranking for parent selection in differential evolution for constrained optimization, in Soft Computing (Springer, 2017), pp. 4617–4633. Google Scholar
41. B. Li, K. Tang, J. Li and X. Yao , Stochastic ranking algorithm for many-objective optimization based on multiple indicators, IEEE Trans. Evol. Comput. 20(6) (2016) 924–938. Web of Science, Google Scholar
42. L. Ali and S. L. Sabat , Particle swarm optimisation with stochastic ranking for constrained numerical and engineering benchmark problems, Int. J. Bio-Inspired Comput. 4(1) (2012) 155–166. Google Scholar
43. B. Meyer , Constraint handling and stochastic ranking in ACO, IEEE Congress on Evolutionary Computation (2005) pp. 2683–2690. Google Scholar