The week's pick
Reseach Article
Space and Time Analysis on the Lattice of Cuboid for Data Warehouse
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 77 - Number 3 |
| Year of Publication: 2013 |
| Authors: Anjana Gosain, Suman Mann |
10.5120/13378-0993
|
Anjana Gosain, Suman Mann . Space and Time Analysis on the Lattice of Cuboid for Data Warehouse. International Journal of Computer Applications. 77, 3 ( September 2013), 47-52. DOI=10.5120/13378-0993
Abstract
Multidimensional analysis requires the computation of many aggregate functions over a large volume of collected data. To provide the various viewpoints for the analysts, these data are organized as a multi-dimensional data model called data cubes. Each cell in a data cube represents a unique set of values for the different dimensions and contains the metrics of interest. The different abstraction and concretization associated with a dimension may be represented as lattice. The focus is to move up and drill down within the lattice using an algorithm with optimal space and computation. In the lattice of cuboids, there exist multiple paths for summarization from a lower to an upper level of cuboid. The alternate paths involve different amounts of storage space and different volume of computations. Thus objective of this paper is to design an algorithm for formal analysis leading towards detection of an optimal path for any two given valid pair of cuboids at different levels. Algorithm is proposed based on branch and bound method for selection of optimal path. Experimental results in the last show that the solution obtained by the algorithm gives the optimal solution in terms of space and time computation.
References
- A. Shukla, Deshpande PM, Naughton JF, "materialized view selection for multicube data models" 7th international conference on extended database technology, Germany, March 2000, Springer, pp 269-284.
- A. Shukla, PM Deshpande, JF Naughton, "materialized view selection for multidimensional datasets", Proceeding of 24th international conference on very large databases, NEW York, August 1998,pp 488-499.
- Antoaneta Ivanova, Boris Rachev, "Multidimensional models – Constructing data cube", International Conference on Computer Systems and Technologies- CompSysTech'2004.
- C. Zhang and J. Yang, "Genetic algorithm for materialized view selection in data warehouse environments," Proceedings of the International Conference on data Warehousing and Knowledge Discovery, LNCS, vol. 1676,pp. 116-125, 1999
- Ellis Hororwitz, Sartaj Sahni, Sanguthevar Rajasekaran, "fundamentals of computer algorithms" Galgotia publication, 1999.
- G. Sanjay, C. Alok, "Parallel Data cube Construction for high performance On_line analytical processing", IEEE . Inter. Confer. 1997, pp10-14
- H. Gupta, "selection of views to materialize in a data Warehouse", ICDT, January 1997, Delphi Greece.
- H. Gupta, I. S. Mumick, Selection of views to materialize under maintenance cost constraint. In Proc. 7th International Conference on Database Theory (ICDT'99) Jerusalem, Israel, pp. 453–470, 1999
- I. Mami, R. Coletta, and Z. Bellahsene, "Modeling view selection as a constraint satisfaction problem", In DEXA, pp 396-410,2011
- I. Mami and Z. Bellahsene,"A survey of view selection method" SIGMOD Record, March 2012 (Vol. 41, No. 1), pp 20-30
- I. Antoaneta, R Boris, "Multidimensional models-constructing data cube" Int. conference on computer systems and technologies-CompSysTech'2004, V-5pp1-7
- J. Hen, J. Pei,G. D and K. Wang, 'Efffficient computation of iceberg cubes with complex measures," in proc. 2001 ACM-SIGMOD Int. conference Management of data (SIGMOD'01),May2001,PP1-12.
- J. Yang, K. Karlapalem, and Q. Li. "A framework for designing materialized views in data warehousing environment", proceedings of 17th IEEE International conference on Distributed Computing Systems, Maryland, U. S. A. , May 1997
- K. Aouiche, P. Jouve, and J. Darmont. Clustering-based materialized view selection in data warehouses. In ADBIS'06, volume 4152 of LNCS, pages 81–95, 2006.
- L. Y. Wen, K. I. Chung, "A genetic algorithm for OLAP data cubes" Knowledge and information systems, January 2004,volume 6,Issue1,pp 83-102.
- M. P. Deshpande ,S. Agarwal, J. F. Naughton, R. Ramakrishnan "Computation of Multidimensional Aggregates" University of Wisconsin Madison, Technical Report,1997
- M. P. Deshpande, S. Agarwal, R. Agarwal, A. Gupta, J. F. Naughton,R. Ramakrishnan and S. Sarawagi; "On the computation of multidimensional aggregates"; Proc. of 1996 International Conference on Very Large Data Bases VLDB'96.
- S. Amit, D Prasad, N. F. Jeffrey, "Materialized view selection for multi-cube data models, In Proc. of 7th Int. conference on Extending database Technology: Advances in Database Technology, Springer 2000, pp 269-284.
- S. D. Kuznetsov, Y. A. Kudryavtsev," A mathematicl model of the OLAP cubes" Programming and computer software, vol35,no5,2009, pp 257-265.
- Stefanovic, N. , Han, J. , Koperski, K. : Object-Based Selective Materialization for efficient Implementation of Spatial data cubes. IEEE transaction on Knowledge and DataEngineering,2000,pp 938-958
- S. Soumya,C. Nabendu, C. Agostino, "Optimal space and time complexity analysis on the lattice of cuboids using galois connections for the data warehousing" In proc 2009,Inter. conf. on computer science and convergence information technology,pp1271- 1275.
- S. Soumya, C. Nabendu, "Efficient traversal in data warehouse based on concept hierarchy using Galois Connections, In proc. of second Int. Con on Emerging applicationsof information technology,2011,pp 335- 339
- V. Harinarayan, Rajaraman, A. , Ullman," Implementing Data Cubes Efficiently", In ACM SIGMOD International Conference on Management of Data, ACM Press, New York (1996) pp. 205-216.
- W. H. Inmon, "building the data warehouse" Wiley, Fourth Edition, 2005.
- X. Li, J. Han, and H. Gonzalez, "High dimensional OLAP: a Minimal cubing approach,"in Proc. 2004 Int. Conf. Very Large Databases (VLDB'04),Toronto Canada,Aug. 2004,pp. 528-539.
- Y. Chen, G. Dong,J. Han, B. W. Wah, and J. Wang, "Multidimensional regression analysis of time series data streams," in proc. 2002 International conference on very large data Bases(VLDB'02),Hong Cong, Chiana, Aug. 2002,pp. 323-334
- Y. A Kudryavtsev, S. D. Kuznetsov, "A Mathematical model of the OLAP cubes",Programming and computer software,Vol35, No 5,2009, pp 257-265.
- Z. Shao. , J. Han, and d. Xin, "MM-cubing: computing iceberg cubes by factorizing the lattice space," In Proc. 2004 Int. Conf. on Scientific and statistical Database Management (SSDBM'04), Santorini Island, Greece, June 2004,pp. 213-22.
Index Terms
Keywords