CFP last date
15 April 2024
Reseach Article

The Near-Greedy Algorithm for Views Selection in Data Warehouses and its Performance Guarantees

by Omar H. Karam
International Journal of Applied Information Systems
Foundation of Computer Science (FCS), NY, USA
Volume 6 - Number 6
Year of Publication: 2013
Authors: Omar H. Karam
10.5120/ijais13-451069

Omar H. Karam . The Near-Greedy Algorithm for Views Selection in Data Warehouses and its Performance Guarantees. International Journal of Applied Information Systems. 6, 6 ( December 2013), 30-34. DOI=10.5120/ijais13-451069

@article{ 10.5120/ijais13-451069,
author = { Omar H. Karam },
title = { The Near-Greedy Algorithm for Views Selection in Data Warehouses and its Performance Guarantees },
journal = { International Journal of Applied Information Systems },
issue_date = { December 2013 },
volume = { 6 },
number = { 6 },
month = { December },
year = { 2013 },
issn = { 2249-0868 },
pages = { 30-34 },
numpages = {9},
url = { https://www.ijais.org/archives/volume6/number6/583-1069/ },
doi = { 10.5120/ijais13-451069 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2023-07-05T18:52:45.795535+05:30
%A Omar H. Karam
%T The Near-Greedy Algorithm for Views Selection in Data Warehouses and its Performance Guarantees
%J International Journal of Applied Information Systems
%@ 2249-0868
%V 6
%N 6
%P 30-34
%D 2013
%I Foundation of Computer Science (FCS), NY, 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.

References
  1. 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.
  2. 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.
  3. 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).
  4. W. H. Inmon, Building the Data Warehouse. John Wiley & Sons, 2005.
  5. 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.
  6. Himanshu Gupta, Selection of views to materialize in a data warehouse. In Database Theory—ICDT'97, pp. 98-112. Springer Berlin Heidelberg, 1997.
  7. 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.
  8. 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.
  9. 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.
  10. 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.
  11. Jiawei Han, Micheline Kamber, and Jian Pei. Data mining: concepts and techniques. Morgan Kaufmann, 2006.
Index Terms

Computer Science
Information Sciences

Keywords

Greedy algorithm near greedy algorithm performance guarantee.