The Near-Greedy Algorithm for Views Selection in Data Warehouses and its Performance Guarantees
Omar H Karam. Article: The Near-Greedy Algorithm for Views Selection in Data Warehouses and its Performance Guarantees. International Journal of Applied Information Systems 6(6):30-34, December 2013. BibTeX
@article{key:article, author = "Omar H. Karam", title = "Article: The Near-Greedy Algorithm for Views Selection in Data Warehouses and its Performance Guarantees", journal = "International Journal of Applied Information Systems", year = 2013, volume = 6, number = 6, pages = "30-34", month = "December", note = "Published by Foundation of Computer Science, New York, USA" }
Abstract
In data warehouses, views or summaries can be materialized to obtain better performance. In this paper, the near greedy algorithm for views selection is proposed. It is a generalization of the greedy algorithm for views selection and defines a class of solutions existing in the range between the optimal and the greedy solutions. At each of its iterations, the algorithm selects multiple views in a greedy manner instead of just one. The iterations continue until the number of desired views is reached. The algorithm's complexity is presented and the performance guarantee for the greedy algorithm is expanded to obtain a general equation that specifies the minimum performance expected from each near greedy solution.
Reference
- Omar Boussaid, Jérôme Darmont, Fadila Bentayeb and Sabine Loudcher, Warehousing complex data from the web, International Journal of Web Engineering and Technology, vol. 4, no. 4, pp. 408-433.
- Laurent d'Orazio, and Sandro Bimonte, Multidimensional arrays for warehousing data on clouds. In Data Management in Grid and Peer-to-Peer Systems, pp. 26-37. Springer Berlin Heidelberg, 2010.
- Eya Ben Ahmed, Ahlem Nabli and Faïez Gargouri, A survey of user-centric data warehouses: from personalization to recommendation. arXiv preprint arXiv:1107. 1779 (2011).
- W. H. Inmon, Building the Data Warehouse. John Wiley & Sons, 2005.
- Venky Harinarayan, Anand Rajaraman, and Jeffrey D. Ullman. Implementing data cubes efficiently. In ACM SIGMOD Record, vol. 25, no. 2, pp. 205-216. ACM, 1996.
- Himanshu Gupta, Selection of views to materialize in a data warehouse. In Database Theory—ICDT'97, pp. 98-112. Springer Berlin Heidelberg, 1997.
- Himanshu Gupta and Inderpal Singh Mumick. Selection of views to materialize under a maintenance cost constraint. In Database Theory—ICDT'99, pp. 453-470. Springer Berlin Heidelberg, 1999.
- Kamel Aouiche and Jérôme Darmont, Data mining-based materialized view and index selection in data warehouses, Journal of Intelligent Information Systems vol. 33, no. 1. pp. 65-93.
- T. V. Vijay Kumar, Mohammad Haider, and Santosh Kumar, A view recommendation greedy algorithm for materialized views selection. In Information Intelligence, Systems, Technology and Management, pp. 61-70. Springer Berlin Heidelberg, 2011.
- Kamel Aouiche, Pierre-Emmanuel Jouve and Jérôme Darmont, Clustering-based materialized view selection in data warehouses. In Advances in Databases and Information Systems, pp. 81-95. Springer Berlin Heidelberg, 2006.
- Jiawei Han, Micheline Kamber, and Jian Pei. Data mining: concepts and techniques. Morgan Kaufmann, 2006.
Keywords
Greedy algorithm, near greedy algorithm, performance guarantee.