A DISCRETE PARTICLE SWARM ALGORITHM FOR OLAP DATA CUBE SELECTION

Jorge Loureiro, Orlando Belo

2006

Abstract

Multidimensional analysis supported by Online Analytical Processing (OLAP) systems demands for many aggregation functions over enormous data volumes. In order to achieve query answering times compatible with the OLAP systems’ users, and allowing all the business analytical views required, OLAP data is organized as a multidimensional model, known as data cube. The materialization of all the data cubes required for decision makers would allow fast and consistent answering times to OLAP queries. However, this also imply intolerable costs, concerning to storage space and time, even when a data warehouse had a medium size and dimensionality - this will be critical on refreshing operations. On the other hand, given a query profile, only a part of all subcubes are really interesting. Thus, cube selection must be made aiming to minimize query (and maintenance) costs, keeping as a constraint the materializing space. That is a complex problem: its solution is NP-hard. Many algorithms and several heuristics, especially of greedy nature and evolutionary approaches, have been used to provide an approximate solution. To this problem, a new algorithm is proposed in this paper: particle swarm optimization (PSO). According to our experimental results, the solution achieved by the PSO algorithm showed a speed of execution, convergence capacity and consistence that allow electing it to use in data warehouse systems of medium dimensionalities.

References

  1. Angeline, P., 1998. Using Selection to Improve Particle Swarm Optimization. In Proc. Of the IEEE International Conference on Evolutionary Computation (ICEC'98), Anchorage, Alaska, USA, May 4-9.
  2. Baralis, E., Paraboschi, S., and Teniente, E., 1997. Materialized View Selection in a Multidimensional Database. In Proceedings of the 23rd International Conference on Very Large Data Base (VLDB), Athens, Greece, pp. 156-165.
  3. Codd, E.F., Codd, S.B., and Sulley, C.T., 1993. Providing OLAP (On-Line Analytical Processing) to User Analysts: An IT Mandate. Technical Report.
  4. Chaudhuri, S. & Dayal, U., 1997. An Overview of Data Warehouse and OLAP Technology. In ACM SIGMOD Record 26(1), pp. 65-74.
  5. Eberhart, R.C., & Kennedy, J., 1995. A new Optimizer Using Particle Swarm Theory. In Proc. Os the Sixth International Symposium on Micro Machine and Human Science, Nagoya, Japan, IEEE Service Center, Piscataway, NJ, pp. 39-43.
  6. Gupta, A., Mumick, T., and Subrahmanian, V., 1993. Maintaining Views Incrementally. In Proceedings of ACM SIGMOD 1993 International Conference on Management of Data, Washington, DC.
  7. Gupta, H., Harinarayan, V., Rajaraman, A., and Ullman, J., 1997. Index Selection for OLAP. In Proceedings of the Intl. Conf. on Data Engineering, Birmingham, UK, pp. 208-219.
  8. Gupta, H., 1997. Selection of Views to Materialize in a Data Warehouse. In Proceedings of ICDT, Delphi, pp. 98-112.
  9. Gupta, H. & Mumick, I.S., 1999. Selection of Views to Materialize under a Maintenance-Time Constraint. In Proc. Of the International Conference on Database Theory.
  10. Harinarayan, V., Rajaraman, A., and Ullman, J., 1996. Implementing Data Cubes Efficiently. In Proc. of ACM SIGMOD, Montreal, Canada, pp. 205-216.
  11. Horng, J.T., Chang, Y.J., Liu, B.J., and Kao, C.Y., 1999. Materialized View Selection Using Genetic Algorithms in a Data Warehouse. In Proceedings of World Congress on Evolutionary Computation, Washington D.C.
  12. Kalnis, P., Mamoulis, N., and D. Papadias, 2002. View Selection Using Randomized Search. In Data Knowledge Engineering, vol. 42, number 1, pp. 89- 111.
  13. Kennedy, J., & Eberhart, R.C., 1995. Particle Swarm Optimization. In Proc. of IEEE Intl. Conference on Neural Networks (Perth, Australia), IEEE Service Center, Piscataway, NJ (1995) IV:1942-1948.
  14. Kennedy, J., and Eberhart, R.C., 1997. A Discrete Binary Version of the Particle Swarm Optimization Algorithm. In Proc. of the 1997 Conference on Systems, Man and Cybernetics (SMC'97), pp. 4104- 4109.
  15. Liang, W., Wang, H., and Orlowska, M.E., 2001. Materialized View Selection Under the Maintenance Cost Constraint. In Data and Knowledge Engineering, 37(2), pp. 203-216.
  16. Lin, W.-Y., & Kuo, I-C, 2004. A Genetic Selection Algorithm for OLAP Data Cubes. In Knowledge and Information Systems, Volume 6, Number 1, SpringerVerlag London Ltd., pp. 83-102.
  17. L?vbjerg, M., Rasmussen, T., and Krink, T., 2001. Hybrid Particle Swarm Optimization with Breeding and Subpopulations. In Proceedings of the 3rd Genetic and Evolutionary Computation Conference (GECCO2001).
  18. Mumick, I.S., Quass, D., Mumick, B.S., 1997. Maintenance of Data Cubes and Summary Tables in a Warehouse. In Peckham J (ed.). Proceedings of ACM SIGMOD International Conference on Management of Data, Tucson, Arizona, pp. 100-111.
  19. Shi, Y., & Eberhart, R., 1999. Empirical Study of Particle Swarm Optimization. In Proceedings of the 1999 Congress of Evolutionary Computation, vol. 3, IEEE Press, pp. 1945-1950.
  20. Shukla, A., Deshpande, P.M., and Naughton, J.F., 1998. Materialized View Selection for Multidimensional Datasets. In Proc. of VLDB.
  21. Shukla, A., Deshpande, P.M., and Naughton, J.F., 2000. Materialized View Selection form Multicube Data Models. In Zaniolo, C., Lockemann P.C., Scholl, M.H., Torsten, G. (eds.). In Proceedings of Advances in Database Technology (EDBT'00), Konstanz, Germany. Lecture Notes in Computer Science 1777, Springer, Berlin, pp. 269.284.
  22. Transaction Processing Performance Council (TPC): TPC Benchmark R (decision support) Standard Specification Revision 2.1.0. tpcr_2.1.0.pdf, available at http://www.tpc.org.
  23. Van den Bergh, F., and Engelbrecht, A.P., 2004. A Cooperative Approach to Particle Swarm Optimization. In IEEE Transactions on Evolutionary Computation, Vol. 8, No. 3, pp. 225-239.
  24. Zhang, C., Yao, X., and Yang, J., 2001. An Evolutionary Approach to Materialized Views Selection in a Data Warehouse Environment. In IEEE Trans. on Systems, Man and Cybernetics, Part C, Vol. 31, N.º 3.
Download


Paper Citation


in Harvard Style

Loureiro J. and Belo O. (2006). A DISCRETE PARTICLE SWARM ALGORITHM FOR OLAP DATA CUBE SELECTION . In Proceedings of the Eighth International Conference on Enterprise Information Systems - Volume 1: ICEIS, ISBN 978-972-8865-41-2, pages 46-53. DOI: 10.5220/0002496000460053


in Bibtex Style

@conference{iceis06,
author={Jorge Loureiro and Orlando Belo},
title={A DISCRETE PARTICLE SWARM ALGORITHM FOR OLAP DATA CUBE SELECTION},
booktitle={Proceedings of the Eighth International Conference on Enterprise Information Systems - Volume 1: ICEIS,},
year={2006},
pages={46-53},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0002496000460053},
isbn={978-972-8865-41-2},
}


in EndNote Style

TY - CONF
JO - Proceedings of the Eighth International Conference on Enterprise Information Systems - Volume 1: ICEIS,
TI - A DISCRETE PARTICLE SWARM ALGORITHM FOR OLAP DATA CUBE SELECTION
SN - 978-972-8865-41-2
AU - Loureiro J.
AU - Belo O.
PY - 2006
SP - 46
EP - 53
DO - 10.5220/0002496000460053