Open Access   Article

Precomputing Shell Fragments for OLAP using Inverted Index Data Structure

D. Datta1 , A. Koley2 , A. Sarkar3 , S. Chatterjee4

1 Department of Computer Science, St. Xavier’s College, Kolkata, India.
2 Department of Computer Science, Banaras Hindu University, Varanasi, India.
3 Deloitte Consulting US-India Pvt. Ltd, Hyderabad, India.
4 Deloitte Consulting US-India Pvt. Ltd, Hyderabad, India.

Correspondence should be addressed to: debabrata.datta@sxccal.edu.

Section:Research Paper, Product Type: Journal Paper
Volume-6 , Issue-1 , Page no. 24-30, Jan-2018

CrossRef-DOI:   https://doi.org/10.26438/ijcse/v6i1.2430

Online published on Jan 31, 2018

Copyright © D. Datta, A. Koley, A. Sarkar, S. Chatterjee . This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

View this paper at   Google Scholar | DPI Digital Library

Citation

IEEE Style Citation: D. Datta, A. Koley, A. Sarkar, S. Chatterjee, “Precomputing Shell Fragments for OLAP using Inverted Index Data Structure”, International Journal of Computer Sciences and Engineering, Vol.6, Issue.1, pp.24-30, 2018.

MLA Style Citation: D. Datta, A. Koley, A. Sarkar, S. Chatterjee "Precomputing Shell Fragments for OLAP using Inverted Index Data Structure." International Journal of Computer Sciences and Engineering 6.1 (2018): 24-30.

APA Style Citation: D. Datta, A. Koley, A. Sarkar, S. Chatterjee, (2018). Precomputing Shell Fragments for OLAP using Inverted Index Data Structure. International Journal of Computer Sciences and Engineering, 6(1), 24-30.

VIEWS PDF XML
303 306 downloads 75 downloads
  
  
           

Abstract

Efficient methods to generate data cubes for On-Line Analytical Processing or OLAP are required for query processing and data analysis. OLAP involves multidimensional analysis of data and as well as selectively extracting and viewing data from different perspectives or points of view. In OLAP, a complex query can lead to many scans of the base relational database, leading to poor performance. This research paper provides an algorithm for the data cube generation suitable for OLAP systems in a fast way. The OLAP cube structure, based on aggregation operations and capable of fast retrieval of data, is extensively explored. The inverted index data structure, which is a mapping from content to index of the said content in any indexed data storage system, is used as an efficient tool for shell fragment computation. A study of efficiency and trade-offs involved in terms of processing complexity and storage space when compared to full cube computation are also provided here.

Key-Words / Index Term

OLAP, data cube, cube shell, shell fragmentation, inverted index data structure, multidimensional analysis

References

[1] X. Li, J. Han, and H. Gonzalez, “High-dimensional OLAP: A minimal cubing approach”, In Proceedings of 30th International Conference on VLDB, pp. 528 – 539, 2004.
[2] Chaudhari, S., U. Dayal, “An overview of Data Warehousing and OLAP Technology”, ACM SIGMOD, pp. 65 – 74, 1997.
[3] S. Agarwal, R. Agrawal, P. M. Deshpande, A. Gupta, J. F. Naughton, R. Ramakrishnan and S. Sarawagi. On the computation of multidimensional aggregates. In Proceedings of 22nd International Conference on VLDB, pp. 506 – 521, 1996.
[4] J. Gray, S. Chaudhuri, A. Bosworth, A. Layman, D. Reichart, M. Venkatrao, F. Pellow and H. Pirahesh. “Data cube: A relational aggregation operator generalizing group-by, cross-tab and subtotals”, Data Mining and Knowledge Discovery, pp. 29 – 54, 1997.
[5] V. Harinarayan, A. Rajaraman, and J. D. Ullman, “Implementing data cubes efficiently”, ACM SIGMOD, pp. 205 – 216, 1996.
[6] K. Beyer and R. Ramakrishnan, “Bottom-up computation of sparse and iceberg cubes”, ACM SIGMOD, pp. 359 – 370, 1999.
[7] Y. Zhao, P. M. Deshpande, and J. F. Naughton, “An array-based algorithm for simultaneous multidimensional aggregates”, ACM SIGMOD, pp. 159 – 170, 1997.
[8] J. Han, J. Pei, G. Dong, and K. Wang, “Efficient computation of iceberg cubes with complex measures”, ACM SIGMOD, pp. 1 – 12, 2001.
[9] D. Xin, J. Han, X. Li, Z> Shao and B. W. Wah, “Computing iceberg cubes by top-down and bottom-up integration, The StarCubing Approach”. IEEE Transactions on Knowledge and Data Engineering, Vol. 19, Issue – 1, pp. 111 – 126, 2007.
[10] W. Wang, H. Lu, J. Feng, and J. X. Yu, “Condensed cube: An effective approach to reducing data cube size”, In Proceedings of 18th International Conference on Data Engineering, 2002.
[11] Y. Sismanis, N. Roussopoulos, A. Deligianannakis, and Y. Kotidis, “Dwarf: Shrinking the petacube”. ACM SIGMOD, pp. 464 – 475, 2002.
[12] L. V. S. Lakshmanan, J. Pei, and J. Han, “Quotient cube: How to summarize the semantics of a data cube”, In Proceedings of 28th International Conference on VLDB, pp. 778 – 789, 2002.
[13] D. Barbara and M. Sullivan, “Quasi-cubes: Exploiting approximation in multidimensional databases. CM SIGMOD, pp. 12 – 17, 1997.