CSCI585 Flexible Data Cubes for Online Aggregation Mirek Riedewald Divyakant Agrawal and Arm El Abbadi Space Efficient Data Cubes for Dynamic Environments Mirek Riedewald Divyakant Agrawal Arm El Abbadi and Renato Pajarola C Shahabi CSCI585 Outline Introduction New Approach IDC Pre Aggregation Techniques Query and Update an IDC Selecting an IDC IDC with more than One Dimension Conclusion C Shahabi CSCI585 Introduction Data Cubes Similar to a multidimensional array Used in OLAP Online Analytical Processing Aggregate range query C Shahabi It selects range of the data cube and computes the aggregate of the values of the cells in the region CSCI585 Introduction Pre aggregate data cube Provide fast replies for the queries Increase update costs and storage costs New approach C Shahabi Iterative Data Cube IDC CSCI585 Outline Introduction New Approach IDC Pre Aggregation Techniques Query and Update an IDC Selecting an IDC IDC with more than One Dimension Conclusion C Shahabi CSCI585 New Approach Iterative Data Cube IDC C Shahabi Provide a modular framework for combining one dimensional aggregation techniques to create spaceoptimal high dimensional data cubes CSCI585 Iterative Data Cube IDC Contributions C Shahabi For each dimension a different onedimensional technique can be selected Combining the one dimensional techniques is easy A variety of cost tradeoffs between query and update Generalizing some of pre aggregation approaches CSCI585 Iterative Data Cube Technique IDC is constructed by applying onedimensional pre aggregation techniques along the dimensions Iterative Data Cubes generalize PS SRPS and SDDC C Shahabi PS Prefix Sum SRPS Space Efficient Relative Prefix Sum SDDC Space Efficient Dynamic Data Cube CSCI585 Outline Introduction New Approach IDC Pre Aggregation Techniques Query and Update an IDC Selecting an IDC IDC with more than One Dimension Conclusion C Shahabi CSCI585 Prefix Sum Original array 3 5 1 2 2 4 6 3 3 PS array 3 C Shahabi 8 9 11 13 17 23 26 29 CSCI585 Space Efficient Relative Prefix Sum The data cube is partitioned into a set of disjoint hyper rectangles of equal size termed boxes Any cell in box B stores the value SUM A l1 l2 ld A c where for all i 1 i d if ci ai li 0 li ai 1 if ai 1 ci ai k C Shahabi CSCI585 Space Efficient Relative Prefix Sum SRPS array Original array 0 0 1 2 3 4 5 6 7 8 0 3 5 1 2 2 4 6 3 3 0 1 7 3 2 6 8 7 1 2 4 1 2 2 4 2 3 3 3 4 5 7 2 3 3 2 1 5 3 5 2 8 2 3 4 4 2 1 3 3 4 7 1 3 4 5 2 6 7 8 Border cells Border cells include cells 3 3 6 1 8 5 1 1 from outside the block 4 5 2 7 1 9 3 3 4 into their aggregation 5 6 2 4 2 2 3 1 9 1 3 7 5 4 3 1 3 2 1 9 6 8 C Shahabi 1 2 block size 3 3 4 5 6 7 8 Inner cells Inner cells store sums local to the block Partition into blocks of equal size Space Efficient Relative Prefix Sum a1 0 a2 0 c1 0 c2 2 A 0 1 A 0 2 c1 1 c2 2 A 1 1 A 1 2 SRPS array Original array CSCI585 0 1 2 0 1 2 3 4 5 6 7 8 0 3 5 1 2 2 4 6 3 3 0 6 1 7 3 2 6 8 7 1 2 4 1 5 2 2 4 2 3 3 3 4 5 7 2 3 3 2 1 5 3 5 2 8 2 3 4 4 2 1 3 3 4 7 1 3 4 5 2 3 3 6 1 8 5 1 1 5 6 4 5 2 7 1 9 3 3 4 6 7 2 4 2 2 3 1 9 1 3 7 8 5 4 3 1 3 2 1 9 6 8 C Shahabi block size 3 3 4 5 6 7 8 Space Efficient Relative Prefix Sum a1 0 a2 0 c1 2 c2 0 A 1 0 A 2 0 c1 2 c2 1 A 1 1 A 2 1 SRPS array Original array CSCI585 0 1 2 0 1 2 3 4 5 6 7 8 0 3 5 1 2 2 4 6 3 3 0 6 1 7 3 2 6 8 7 1 2 4 1 5 2 2 4 2 3 3 3 4 5 7 2 3 3 2 1 5 3 5 2 8 2 3 4 4 2 1 3 3 4 7 1 3 4 5 2 3 3 6 1 8 5 1 1 5 6 4 5 2 7 1 9 3 3 4 6 7 2 4 2 2 3 1 9 1 3 7 8 5 4 3 1 3 2 1 9 6 8 C Shahabi 9 7 block size 3 3 4 5 6 7 8 Space Efficient Relative Prefix Sum CSCI585 SRPS array Original array 0 1 2 0 1 2 3 4 5 6 7 8 0 3 5 1 2 2 4 6 3 3 0 6 1 7 3 2 6 8 7 1 2 4 1 5 2 2 4 2 3 3 3 4 5 7 2 3 3 2 1 5 3 5 2 8 2 3 4 4 2 1 3 3 4 7 1 3 4 5 2 3 3 6 1 8 5 1 1 5 6 4 5 2 7 1 9 3 3 4 6 7 2 4 2 2 3 1 9 1 3 7 8 5 4 3 1 3 2 1 9 6 8 C Shahabi 9 7 11 block size 3 3 4 5 6 7 8 Space Efficient Relative Prefix Sum a1 0 a2 3 c1 0 c2 3 A 0 0 A 0 3 c1 1 c2 3 A 1 0 A 1 3 SRPS array Original array CSCI585 2 3 0 6 11 4 1 5 18 5 7 2 2 8 2 3 4 7 1 3 4 1 8 5 1 1 5 7 1 9 3 3 4 6 2 2 3 1 9 1 3 7 3 1 3 2 1 9 6 8 0 1 2 3 4 5 6 7 8 0 3 5 1 2 2 4 6 3 3 1 7 3 2 6 8 7 1 2 2 2 4 2 3 3 3 4 3 3 2 1 5 3 5 4 4 2 1 3 3 5 2 3 3 6 6 4 5 2 7 2 4 8 5 4 C Shahabi 0 9 1 block size 3 7 11 4 5 6 7 8 Space Efficient Relative Prefix Sum CSCI585 SRPS array Original array 2 3 0 6 11 4 1 5 18 5 7 2 9 2 8 2 3 15 14 4 7 1 3 4 1 8 5 1 1 5 7 1 9 3 3 4 6 …