LCS-Hist: taming massive high-dimensional data cube compression

ABSTRACT

The problem of efficiently compressing massive high-dimensional data cubes still waits for efficient solutions capable of overcoming well-recognized scalability limitations of state-of-the-art histogram-based techniques, which perform well on small-in-size low-dimensional data cubes, whereas their performance in both representing the input data domain and efficiently supporting approximate query answering against the generated compressed data structure decreases dramatically when data cubes grow in dimension number and size. To overcome this relevant research challenge, in this paper we propose LCS-Hist, an innovative multidimensional histogram devising a complex methodology that combines intelligent data modeling and processing techniques in order to tame the annoying problem of compressing massive high-dimensional data cubes. With respect to similar histogram-based proposals, our technique introduces (i) a surprising consumption of the storage space available to house the compressed representation of the input data cube, and (ii) a superior scalability on high-dimensional data cubes. Finally, several experimental results performed against various classes of data cubes confirm the advantages of LCS-Hist, even in comparison with those given by state-of-the-art similar techniques.

REFERENCES

• 1: Swarup Acharya , Viswanath Poosala , Sridhar Ramaswamy, Selectivity estimation in spatial databases, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.13-24, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 2: Anderson, T. W. 1958. Introduction to Multivariate Statistical Analysis, Wiley.
• 3: Nicolas Bruno , Surajit Chaudhuri , Luis Gravano, STHoles: a multidimensional workload-aware histogram, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.211-222, May 21-24, 2001, Santa Barbara, California, United States
• 4: Surajit Chaudhuri , Gautam Das , Vivek Narasayya, Optimized stratified sampling for approximate query processing, ACM Transactions on Database Systems (TODS), v.32 n.2, p.9-es, June 2007 [doi>10.1145/1242524.1242526]
• 5: George Colliat, OLAP, relational, and multidimensional database systems, ACM SIGMOD Record, v.25 n.3, p.64-69, Sept. 1996 [doi>10.1145/234889.234901]
• 6: Alfredo Cuzzocrea, Overcoming Limitations of Approximate Query Answering in OLAP, Proceedings of the 9th International Database Engineering & Application Symposium, p.200-209, July 25-27, 2005 [doi>10.1109/IDEAS.2005.41]
• 7: Alfredo Cuzzocrea , Wei Wang, Approximate range---sum query answering on data cubes with probabilistic guarantees, Journal of Intelligent Information Systems, v.28 n.2, p.161-197, April 2007 [doi>10.1007/s10844-006-0007-y]
• 8: Frank Dehne , Todd Eavis , Andrew Rau-Chaplin, The cgmCUBE project: Optimizing parallel data cube generation for ROLAP, Distributed and Parallel Databases, v.19 n.1, p.29-62, January 2006 [doi>10.1007/s10619-006-6575-6]
• 9: Minos Garofalakis , Amit Kumar, Deterministic wavelet thresholding for maximum-error metrics, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France [doi>10.1145/1055558.1055582]
• 10: Dimitrios Gunopulos , George Kollios , Vassilis J. Tsotras , Carlotta Domeniconi, Approximating multi-dimensional aggregate range queries over real attributes, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.463-474, May 15-18, 2000, Dallas, Texas, United States
• 11: Chris H. Hamilton , Andrew Rau-Chaplin, Compact Hilbert Indices for Multi-Dimensional Data, Proceedings of the First International Conference on Complex, Intelligent and Software Intensive Systems, p.139-146, April 10-12, 2007 [doi>10.1109/CISIS.2007.16]
• 12: Christopher Jermaine , Subramanian Arumugam , Abhijit Pol , Alin Dobra, Scalable approximate query processing with the DBO engine, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247560]
• 13: Joni-Kristian Kamarainen , Ville Kyrki , Jarmo Ilonen , Heikki Kälviäinen, Improving similarity measures of histograms using smoothing projections, Pattern Recognition Letters, v.24 n.12, p.2009-2019, August 2003 [doi>10.1016/S0167-8655(03)00039-4]
• 14: M. Muralikrishna , David J. DeWitt, Equi-depth multidimensional histograms, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.28-36, June 01-03, 1988, Chicago, Illinois, United States
• 15: S. Muthukrishnan , Viswanath Poosala , Torsten Suel, On Rectangular Partitionings in Two Dimensions: Algorithms, Complexity, and Applications, Proceedings of the 7th International Conference on Database Theory, p.236-256, January 10-12, 1999
• 16: Viswanath Poosala , Yannis E. Ioannidis, Selectivity Estimation Without the Attribute Value Independence Assumption, Proceedings of the 23rd International Conference on Very Large Data Bases, p.486-495, August 25-29, 1997
• 17: Yannis Sismanis , Antonios Deligiannakis , Nick Roussopoulos , Yannis Kotidis, Dwarf: shrinking the PetaCube, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564745]
• 18: Jeffrey Scott Vitter , Min Wang , Bala Iyer, Data cube approximation and histograms via wavelets, Proceedings of the seventh international conference on Information and knowledge management, p.96-104, November 02-07, 1998, Bethesda, Maryland, United States [doi>10.1145/288627.288645]
• 19: Condensed Cube: An Efficient Approach to Reducing Data Cube Size, Proceedings of the 18th International Conference on Data Engineering, p.155, February 26-March 01, 2002