Flexible Data Cubes for Online AggregationMirek Riedewald, Divyakant Agrawal, and Arm El AbbadiCSCI585CSCI585C. Shahabi(Space-Efficient Data Cubes for Dynamic EnvironmentsMirek Riedewald, Divyakant Agrawal, Arm El Abbadi, and Renato Pajarola)CSCI585CSCI585C. ShahabiOutlineIntroductionNew Approach: IDCPre-Aggregation TechniquesQuery and Update an IDCSelecting an IDCIDC with more than One DimensionConclusionCSCI585CSCI585C. ShahabiIntroductionData CubesSimilar to a multidimensional arrayUsed in OLAP (Online Analytical Processing)Aggregate range queryIt selects range of the data cube and computes the aggregate of the values of the cells in the region.CSCI585CSCI585C. ShahabiIntroductionPre-aggregate data cubeProvide fast replies for the queriesIncrease update costs and storage costs.New approachIterative Data Cube (IDC)CSCI585CSCI585C. ShahabiOutlineIntroductionNew Approach: IDCNew Approach: IDCPre-Aggregation TechniquesQuery and Update an IDCSelecting an IDCIDC with more than One DimensionConclusionCSCI585CSCI585C. ShahabiNew ApproachIterative Data Cube (IDC)Provide a modular framework for combining one-dimensionalaggregation techniques to create space-optimal high-dimensional data cubes.CSCI585CSCI585C. ShahabiIterative Data Cube (IDC)ContributionsFor each dimension a different one-dimensional 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.CSCI585CSCI585C. ShahabiIterative Data Cube TechniqueIDC is constructed by applying one-dimensional pre-aggregationtechniques along the dimensions.Iterative Data Cubes generalize PS, SRPS, and SDDC.PS (Prefix Sum)SRPS (Space-Efficient Relative Prefix Sum)SDDC (Space-Efficient Dynamic Data Cube)CSCI585CSCI585C. ShahabiOutlineIntroductionNew Approach: IDCPrePre--Aggregation TechniquesAggregation TechniquesQuery and Update an IDCSelecting an IDCIDC with more than One DimensionConclusionCSCI585CSCI585C. ShahabiPrefix Sum3 5 1 2 2 4 6 3 3Original arrayPS array…………292623171311983CSCI585CSCI585C. ShahabiSpace-Efficient Relative Prefix SumThe 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]) wherefor all i : 1 <= i <= dli=0 , if ci=aili=ai+1 , if ai+1 <= ci< ai+kCSCI585CSCI585C. Shahabi0 1 2 3 4 5 6 7 80 3 5 1 2 2 4 6 3 31 7 3 2 6 8 7 1 2 42 2 4 2 3 3 3 4 5 73 3 2 1 5 3 5 2 8 24 4 2 1 3 3 4 7 1 35 2 3 3 6 1 8 5 1 16 4 5 2 7 1 9 3 3 47 2 4 2 2 3 1 9 1 38 5 4 3 1 3 2 1 9 60 1 2 3 4 5 6 7 8012345678Space-Efficient Relative Prefix SumOriginal arraySRPS array(block size 3)Partition into blocks of equal size691231345831913224274339172546115816332531743312442825351233754333242242178623713364221530876543210876543210876543210Inner cellsBorder cellsBorder cells include cells from outside the block into their aggregation.Inner cells store sums local to the block.CSCI585CSCI585C. Shahabi56Space-Efficient Relative Prefix SumOriginal array0 1 2 3 4 5 6 7 80 3 5 1 2 2 4 6 3 31 7 3 2 6 8 7 1 2 42 2 4 2 3 3 3 4 5 73 3 2 1 5 3 5 2 8 24 4 2 1 3 3 4 7 1 35 2 3 3 6 1 8 5 1 16 4 5 2 7 1 9 3 3 47 2 4 2 2 3 1 9 1 38 5 4 3 1 3 2 1 9 6SRPS array(block size 3)0 1 2 3 4 5 6 7 8012345678a1=0, a2=0c1=0, c2=2  A[0,1]:A[0,2]c1=1, c2=2  A[1,1]:A[1,2]CSCI585CSCI585C. ShahabiOriginal array0 1 2 3 4 5 6 7 80 3 5 1 2 2 4 6 3 31 7 3 2 6 8 7 1 2 42 2 4 2 3 3 3 4 5 73 3 2 1 5 3 5 2 8 24 4 2 1 3 3 4 7 1 35 2 3 3 6 1 8 5 1 16 4 5 2 7 1 9 3 3 47 2 4 2 2 3 1 9 1 38 5 4 3 1 3 2 1 9 60 1 2 3 4 5 6 7 80 61 52 9 7345678SRPS array(block size 3)Space-Efficient Relative Prefix Suma1=0, a2=0c1=2, c2=0  A[1,0]:A[2,0]c1=2, c2=1  A[1,1]:A[2,1]CSCI585CSCI585C. ShahabiOriginal array0 1 2 3 4 5 6 7 80 3 5 1 2 2 4 6 3 31 7 3 2 6 8 7 1 2 42 2 4 2 3 3 3 4 5 73 3 2 1 5 3 5 2 8 24 4 2 1 3 3 4 7 1 35 2 3 3 6 1 8 5 1 16 4 5 2 7 1 9 3 3 47 2 4 2 2 3 1 9 1 38 5 4 3 1 3 2 1 9 60 1 2 3 4 5 6 7 80 61 52 9 7 11345678SRPS array(block size 3)Space-Efficient Relative Prefix SumCSCI585CSCI585C. ShahabiOriginal array0 1 2 3 4 5 6 7 80 3 5 1 2 2 4 6 3 31 7 3 2 6 8 7 1 2 42 2 4 2 3 3 3 4 5 73 3 2 1 5 3 5 2 8 24 4 2 1 3 3 4 7 1 35 2 3 3 6 1 8 5 1 16 4 5 2 7 1 9 3 3 47 2 4 2 2 3 1 9 1 38 5 4 3 1 3 2 1 9 60 1 2 3 4 5 6 7 80 6 111 5 182 9 7 11345678SRPS array(block size 3)Space-Efficient Relative Prefix Suma1=0, a2=3c1=0, c2=3  A[0,0]:A[0,3]c1=1, c2=3  A[1,0]:A[1,3]CSCI585CSCI585C. ShahabiOriginal array0 1 2 3 4 5 6 7 80 3 5 1 2 2 4 6 3 31 7 3 2 6 8 7 1 2 42 2 4 2 3 3 3 4 5 73 3 2 1 5 3 5 2 8 24 4 2 1 3 3 4 7 1 35 2 3 3 6 1 8 5 1 16 4 5 2 7 1 9 3 3 47 2 4 2 2 3 1 9 1 38 5 4 3 1 3 2 1 9 60 1 2 3 4 5 6 7 80 6 111 5 182 9 7 113 15 1445678SRPS array(block size 3)Space-Efficient Relative Prefix SumCSCI585CSCI585C. ShahabiOriginal array0 1 2 3 4 5 6 7 80 3 5 1 2 2 4 6 3 31 7 3 2 6 8 7 1 2 42 2 4 2 3 3 3 4 5 73 3 2 1 5 3 5 2 8 24 4 2 1 3 3 4 7 1 35 2 3 3 6 1 8 5 1 16 4 5 2 7 1 9 3 3 47 2 4 2 2 3 1 9 1 38 5 4 3 1 3 2 1 9 60 1 2 3 4 5 6 7 80 6 111 5 182 9 7 11 293 15 1445678SRPS array(block size 3)Space-Efficient Relative Prefix Suma1=0, a2=3c1=2, c2=3  A[1,0]:A[2,3]CSCI585CSCI585C. ShahabiOriginal array0 1 2 3 4 5 6 7 80 3 5 1 2 2 4 6 3 31 7 3 2 6 8 7 1 2 42 2 4 2 3 3 3 4 5 73 3 2 1 5 3 5 2 8 24 4 2 1 3 3 4 7 1 35 2 3 3 6 1 8 5 1 16 4 5 2 7 1 9 3 3 47 2 4 2 2 3 1 9 1 38 5 4 3 1 3 2 1 9 60 1 2 3 4 5 6 7 80 6 111 5 182 9 7 11 293 15 14 2045678SRPS array(block size 3)Space-Efficient Relative Prefix SumCSCI585CSCI585C. ShahabiSpace-Efficient Relative …