The HGEDA Hybrid Algorithm for OLAP Data Cubes

Abstract:

On-Line Analytical Processing (OLAP) tools are frequently used in business, science and health to extract useful knowledge from massive databases. An important and hard optimization problem in OLAP data warehouses is the view selection problem, consisting of selecting a set of aggregate views of the data for speeding up future query processing. In this paper we present a new approach, named HGEDA, which is a new hybrid algorithm based on genetic and estimation of distribution algorithms. The original objective is to get benefits from both approaches. Experimental results show that the HGEDA are competitive with the genetic algorithm on a variety of problem instances, often finding approximate optimal solutions in a reasonable amount of time.

• Periodical: Applied Mechanics and Materials (Volumes 130-134)
• Pages: 3158-3162
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.130-134.3158
• Online since: October 2011
• Authors: Chen Jia, Hong Wei Chen
• Keywords: Data Warehouse (DW), Estimation of Distribution Algorithms, OLAP, Query Optimization, View Selection

References

[1] V. Harinarayan, A. Rajaraman, and J. D. Ullman. Implementing data cubes efficiently. In Proc. SIGMOD 1996, pages 205–216, New York, NY, USA, 1996. ACM Press.

DOI: 10.1145/235968.233333

[2] P. Kalnis, N. Mamoulis, and D. Papadias. View selection using randomized search. J. Data Knowl. Eng., 42(1): 89–111, (2002).

DOI: 10.1016/s0169-023x(02)00045-9

[3] Wang ZQ, Zhang DX. Optimal genetic view selection algorithm under space constraint. Int'l Journal of Information Technology, 2005, 11(5): 44−51.

[4] Gorges-Schleuter, M. On the power of evolutionary optimization in the examples of ATSP and large TSP Problems. European Conference on Artificial Life. Brighton, UK, July (1997).

[5] Lin WY, Kuo IC. A genetic selection algorithm for OLAP data cubes. Knowledge and Information Systems, 2004, 6(1): 83−102.

DOI: 10.1007/s10115-003-0093-x

[6] C. Zhang, X. Yao, and J. Yang. An evolutionary approach to materialized views selection in a datawarehouse environment. IEEE Transactions on Systems, Man and Cybernetics, Part C, 31(3): 282–294, August (2001).

DOI: 10.1109/5326.971656

[7] M. Lee and J. Hammer, Speeding upmaterialized viewselection in data warehouses using a randomized algorithm, Int. J. Cooperative Inform. Syst., vol. 10, no. 3, p.327–353, (2001).

DOI: 10.1142/s0218843001000370

[8] Yu JX. Yao X, Choi CH, Gou G. Materialized view selection as constraint evolutionary optimization. IEEE Trans. on Systems, Man and Cybernetics⎯Part C, 2003, 33(4): 485−467.

DOI: 10.1109/tsmcc.2003.818494

[9] A. Shukla, P. Deshpande, J.F. Naughton, and K. Ramasamy. Storage estimation for multidimensional aggregates in the presence of hierarchies. In The VLDB Journal, pages 522–531, (1996).