Solution Manual for Data Mining Chapter 5

Chapter 5 Data Cube Technology 5.1 Exercises 1. Assume a base cuboid of 10 dimensions contains only three base cells: (1) (a1 , d2 , d3 , d4 , . . . , d9 , d10 ), (2) (d1 , b2 , d3 , d4 , . . . , d9 , d10 ), and (3) (d1 , d2 , c3 , d4 , . . . , d9 , d10 ), where a1 = d1 , b2 = d2 , and c3 = d3 . The measure of the cube is count. (a) How many nonempty cuboids will a full data cube contain? (b) How many nonempty aggregate (i.e., nonbase) cells will a full cube contain? (c) How many nonempty aggregate cells will an iceberg cube contain if the condition of the iceberg cube is “count ≥ 2”? (d) A cell, c, is a closed cell if there exists no cell, d , such that d is a specialization of cell c (i.e., d is obtained by replacing a ∗ in c by a non-∗ value) and d has the same measure value as c. A closed cube is a data cube consisting of only closed cells. How many closed cells are in the full cube? Answer: (a) How many nonempty cuboids will a complete data cube contain? 210. (b) How many nonempty aggregated (i.e., nonbase) cells a complete cube will contain? (1) Each cell generates 210 − 1 nonempty aggregated cells, thus in total we should have 3 × 210 − 3 cells with overlaps removed. (2) We have 3 × 27 cells overlapped once (thus count 2) and 1 × 27 (which is (∗, ∗, ∗, d4 , ..., d10 )) overlapped twice (thus count 3). Thus we should remove in total 1 × 3 × 27 + 2 × 1 × 27 = 5 × 27 overlapped cells. (3) Thus we have: 3 × 8 × 27 − 5 × 27 − 3 = 19 × 27 − 3. (c) How many nonempty aggregated cells will an iceberg cube contain if the condition of the iceberg cube is “count ≥ 2”? Analysis: (1) (∗, ∗, d3 , d4 , . . . , d9 , d10 ) has count 2 since it is generated by both cell 1 and cell 2; similarly, we have (2) (∗, d2 , ∗, d4 , . . . , d9 , d10 ):2, (3) (∗, ∗, d3 , d4 , . . . , d9 , d10):2; and (4) (∗, ∗, ∗, d4 , . . . , d9 , d10 ):3. Therefore we have, 4 × 27 = 29 . (d) A cell, c, is a closed cell if there exists no cell, d, such that d is a specialization of cell c (i.e., d is obtained by replacing a ∗ in c by a non-∗ value) and d has the same measure value as c. A closed cube is a data cube consisting of only closed cells. How many closed cells are in the full cube? There are seven cells, as follows (1) (a1 , d2 , d3 , d4 , . . . , d9 , d10 ) : 1, (2) (d1 , b2 , d3 , d4 , . . . , d9 , d10 ) : 1, (3) (4) (5) (6) (d1 , d2 , c3 , d4 , . . . , d9 , d10 ) : 1, (∗, ∗, d3 , d4 , . . . , d9 , d10 ) : 2, (∗, d2 , ∗, d4 , . . . , d9 , d10 ) : 2, (d1 , ∗, ∗, d4 , . . . , d9 , d10 ) : 2, and (7) (∗, ∗, ∗, d4 , . . . , d9 , d10 ) : 3. 2. There are several typical cube computation methods, such as Multiway array computation (MultiWay) [ZDN97], BUC (bottom-up computation) [BR99], and Star-Cubing [XHLW03]. Briefly describe these three methods (i.e., use one or two lines to outline the key points), and compare their feasibility and performance under the following conditions: (a) Computing a dense full cube of low dimensionality (e.g., less than 8 dimensions) (b) Computing an iceberg cube of around 10 dimensions with a highly skewed data distribution (c) Computing a sparse iceberg cube of high dimensionality (e.g., over 100 dimensions) Answer: Note that the textbook adopts the application worldview of a data cube as a lattice of cuboids, where a drill-down moves from the apex (all) cuboid, downward in the lattice. Multiway: bottom-up, simultaneous array aggregation, sharing precomputed results, and minimizing memory requirement. It cannot take advantages of Apriori pruning and is hard to be applied to high dimensional case. BUC: top-down (see above note), recursive partition and conquer, shared sorting. It is sensitive to the ordering of the dimensions and to skew in the data. Star-Cubing: top-down and bottom-up integration using star-tree, enables simultaneous computation while allows Apriori pruning. It is sensitive to the ordering of dimensions. (a) Computing dense full cube of low dimensionality (e.g., less than 8 dimensions) Both MultiWay and Star-Cubing work fine and better than BUC. (b) Computing an iceberg cube of around 10 dimensions with a highly skewed data distribution MultiWay does work for iceberg cubes. Star-Cubing works better than BUC for highly skewed data sets. (c) Computing a sparse iceberg cube of high dimensionality (e.g., over 100 dimensions) MultiWay does work for iceberg cubes. Neither BUC nor Star-Cubing work efficiently for highdimensional data. The closed-cube and shell-fragment approaches should be explored. 3. Suppose a data cube, C, has D dimensions, and the base cuboid contains k distinct tuples. (a) Present a formula to calculate the minimum number of cells that the cube, C, may contain. (b) Present a formula to calculate the maximum number of cells that C may contain. (c) Answer parts (a) and (b) above as if the count in each cube cell must be no less than a threshold, v. (d) Answer parts (a) and (b) above as if only closed cells are considered (with the minimum count threshold, v). Answer: (a) Present a formula to calculate the minimum number of cells that the cube, C, may contain. To achieve the minimum case, we need to “merge” k distinct tuples as soon as possible so that, on higher levels, there will be fewer cells (there are always k cells in the base cuboid ). Here, we have two cases, which represent two possible extremes, 1. If we drop one specific dimension, say A, then k tuples are immediately “merged” into one. The k tuples are organized like the following: t1 = (a1 , t′ ), t2 = (a2 , t′ ), · · · , tk = (ak , t′ ), where t′ is a (D − 1)-dimensional tuple. However, this scheme is not effective if we keep dimension A and instead drop B, because obviously there would still be k tuples remaining, which is not desirable. 2. Case 1 describes an extreme, where the specified “quantity reduction” only occurs when one particular dimension, A, is rolled-up to all. We can imagine another situation in which the “reduction” occurs in an distributive and “average” manner. Let’s look at an example that illustrates these two processes. Suppose that we have an 8(A) × 8(B) × 8(C) three-dimensional cube, and k = 8. If we follow case 1, then there will be 8 base cells, 1(roll up to all on A)+8+8=17 2-D cells, 1+1+8(roll up to all on two dimensions other than A)=10 1-D cells, and 1 0-D cell. However, if we try case 2, that is building a 2 × 2 × 2 3-dimensional subcube on one “corner” of the full cube and then fill it with 8 tuples, we will get 8 base cells, 4+4+4=12 2-D cells (a roll up in either dimension results in 4 cells), 2+2+2 = 6 1-D cells (likewise), and 1 0-D cell. Since 36 = 8 + 17 + 10 + 1 > 8 + 12 + 6 + 1 = 27, case 2 is better than case 1. It seems that case 2 is always better. Say k = 4, then for case 1 we have 4 base cells, 1+4+4=9 2-D cells, 1+1+4=6 1-D cells, and 1 0-D cell, that is, 4+9+6+1=20 cells in total. For case 2, 22 = 4, then we can only build a 2(B) × 2(C) 2-dimensional subcube: 4 base cells, 2+2+4(roll up to all on A)=8 2-D cells, 1(roll up to all on B and C)+2+2=5 1-D cells, and 1 0-D cell, that is, 4+8+5+1=18 cells in total. A heuristic way to think this over is as follows: we want to put k distinct tuples√in an√a × b √ ×c 3 subcube. Case 1 does this in a 1 × 1 × k manner, whereas that of case 2 is k × 3 k × 3 k. Obviously, a + b + c is the number of 1-D cells, and we all know how a + b + c can reach its minimum given the condition that abc = k . To summarize, in order to have the minimum case occur, we shall put all k tuples in an x1 × x2 × · · · × xD subcube satisfying x1 x2 · · · xD = k (if the equality is not possible, we can change it to ≥ and make the objective that of minimizing x1 x2 · · · xD , which means that the subcube should be as small as possible). We choose the vector (x1 , x2 · · · , xD ) such that the xi s are as “close” as possible, which is also the condition that makes x1 + x2 + · · · + xD (see above paragraph) as small as possible. ∑D ∏ The total number of cells is 1 + d=1 ( total # of xj s is d xj ). (b) Present a formula to calculate the maximum number of cells that C may contain. The maximum circumstance occurs when k tuples are placed in a completely “irrelevant” or “random” way, where any two tuples, (t11 , t12, · · · , t1D ) and (t21, t22 , · · · , t2D ), cannot be “merged” into one unless all D dimensions are rolled-up to all, i.e. t1i = t2i , i = 1, 2, · · · , D. Obviously, this can generate the most number of cells: no matter how we choose those dimensions to be dropped, after we do so, there are still k distinct tuples, unless all D dimensions are discarded. D D−1 1 ) + C 0 = k(2D − 1) + 1 cells. This will result in k(C D + · · · + CD + CD D We assume that we can always do placement as proposed, disregarding the fact that dimensionality D and the cardinality ci of each dimension i may place some constraints. (The same assumption is kept throughout for this question). Suppose that there is an 8 × 8 2-dimensional cube. We can place at most 8 tuples in the “irrelevant” manner mentioned above. If we fail to do so (e.g. k = 20), cases will be much more complex and thus are beyond consideration here. The question does not mention how cardinalities of dimensions are set. It can be assumed that we can always increase the cardinalities so that k tuples can be placed in an “irrelevant” style. (c) Answer parts (a) and (b) above as if the count in each cube cell must be no less than a threshold, v. To answer this question, we have a core observation: if all base cells contain at least v tuples, then all aggregate cells will also satisfy the condition. 1. Minimum case: The distinct condition no longer holds here, since v tuples have to be in one identical base cell now. Thus, we can put all k tuples in one base cell, which results in 2D cells in all. 2. Maximum case: We will replace k with ⌊ kv ⌋ and follow the procedure in part (b), since we can get at most that many base cells in all. (d) Answer parts (a) and (b) above as if only closed cells are considered (with the minimum count threshold, v). From the analysis in part (c), we will not consider the threshold, v, as long as k can be replaced by a new value. 1. Minimum case: We still don’t have the distinct condition here. Considering the number of closed cells, 1 is the minimum if we put all k tuples together in one base cell. 2. Maximum case: Given a fixed tuple composition, say p tuples, {t1 , t2 , · · · , tp }, we can obviously have at most one closed cell. In this way we can get an upper bound of Ck1 + C 2k + · · · + Ckk = 2k − 1 closed cells. How can we reach this bound? Make a 2 × 2 × · · · × 2 k-dimensional cube, where k tuples are distributed according to the following coordinates: t1 = (1, 0, · · · , 0), t2 = (0, 1, · · · , 0), tk = (0, 0, · · · , 1). Taking (∗1 , ∗2 , · · · , ∗p , 0, · · · , 0) as an instance for t1 , t2 , · · · , tp will make them into one closed cuboid cell, because changing any * to 0 or 1 results in a smaller count, p − 1 or 1. This finishes our construction, because all 2k − 1 closed cells can be formed likewise. The above statements, however, require k ≤ D. We assume that this is the case. We also assume that cardinalities cannot be increased (as in part (b)) to satisfy the condition. 4. Suppose that a base cuboid has three dimensions, A, B, C, with the following number of cells: |A| = 1, 000, 000, |B| = 100, and |C| = 1000. Suppose that each dimension is evenly partitioned into 10 portions for chunking. (a) Assuming each dimension has only one level, draw the complete lattice of the cube. (b) If each cube cell stores one measure with 4 bytes, what is the total size of the computed cube if the cube is dense ? (c) State the order for computing the chunks in the cube that requires the least amount of space, and compute the total amount of main memory space required for computing the 2-D planes. Answer: (a) Assuming each dimension has only one level, draw the complete lattice of the cube. The complete lattice is shown in Figure 5.1. (b) If each cube cell stores one measure with 4 bytes, what is the total size of the computed cube if the cube is dense? The total size of the computed cube is as follows. • all: 1 • A: 1,000,000; B: 100; C: 1, 000; subtotal: 1,001,100 Figure 5.1: A complete lattice for the cube of Exercise 5.4. • AB : 100,000,000; BC : 100,000; AC : 1,000,000,000; subtotal: 1,100,100,000 • ABC :100,000,000,000 • Total: 101,101,101,101 cells × 4 bytes = 404,404,404,404 bytes (c) State the order for computing the chunks in the cube that requires the least amount of space, and compute the total amount of main memory space required for computing the 2-D planes. The order of computation that requires the least amount of space is B-C -A. as show in Figure 5.2. Figure 5.2: The order of computation in Exercise 5.4 that requires the least amount of space. The total amount of main memory space required for computing the 2-D planes is: Total space = (100 × 1,000) (for the whole BC plane) + (1,000,000 × 10) (for one column of the AB plane) + (100 × 100,000) (for one chunk of the AC plane) = 20,100,000 cells = 80,400,000 bytes. 5. Often, the aggregate count value of many cells in a large data cuboid is zero, resulting in a huge, yet sparse, multidimensional matrix. (a) Design an implementation method that can elegantly overcome this sparse matrix problem. Note that you need to explain your data structures in detail and discuss the space needed, as well as how to retrieve data from your structures. (b) Modify your design in (a) to handle incremental data updates. Give the reasoning behind your new design. Answer: (a) Design an implementation method that can elegantly overcome this sparse matrix problem. Note that you need to explain your data structures in detail and discuss the space needed, as well as how to retrieve data from your structures. A way to overcome the sparse matrix problem is to use multiway array aggregation. (Note: this answer is based on the paper by Zhao, Deshpande, and Naughton entitled “An array-based algorithm for simultaneous multidimensional aggregates” in Proc. 1997 ACM-SIGMOD Int. Conf. Management of Data, pages 159–170, Tucson, Arizona, May 1997 [ZDN97]). The first step consists of partitioning the array-based cube into chunks or subcubes that are small enough to fit into the memory available for cube computation. Each of these chunks is first compressed to remove cells that do not contain any valid data, and is then stored as an object on disk. For storage and retrieval purposes, the “chunkID + offset” can be used as the cell address. The second step involves computing the aggregates by visiting cube cells in an order that minimizes the number of times that each cell must be revisited, thereby reducing memory access and storage costs. By first sorting and computing the planes of the data cube according to their size in ascending order, a smaller plane can be kept in main memory while fetching and computing only one chunk at a time for a larger plane. (b) Modify your design in (a) to handle incremental data updates. Give the reasoning behind your new design. In order to handle incremental data updates, the data cube is first computed as described in (a). Subsequently, only the chunk that contains the cells with the new data is recomputed, without needing to recompute the entire cube. This is because, with incremental updates, only one chunk at a time can be affected. The recomputed value needs to be propagated to its corresponding higher-level cuboids. Thus, incremental data updates can be performed efficiently. 6. When computing a cube of high dimensionality, we encounter the inherent curse of dimensionality problem: there exists a huge number of subsets of combinations of dimensions. (a) Suppose that there are only two base cells, {(a1 , a2 , a3 , . . . , a100), (a1 , a2 , b3 , . . . , b100 )}, in a 100dimensional base cuboid. Compute the number of nonempty aggregate cells. Comment on the storage space and time required to compute these cells. (b) Suppose we are to compute an iceberg cube from the above. If the minimum support count in the iceberg condition is two, how many aggregate cells will there be in the iceberg cube? Show the cells. (c) Introducing iceberg cubes will lessen the burden of computing trivial aggregate cells in a data cube. However, even with iceberg cubes, we could still end up having to compute a large number of trivial uninteresting cells (i.e., with small counts). Suppose that a database has 20 tuples that map to (or cover) the two following base cells in a 100-dimensional base cuboid, each with a cell count of 10: {(a1 , a2 , a3 , . . . , a100 ) : 10, (a1 , a2 , b3 , . . . , b100 ) : 10}. i. Let the minimum support be 10. How many distinct aggregate cells will there be like the following: {(a1 , a2 , a3 , a4 , . . . , a99, ∗) : 10, . . . , (a1 , a2 , ∗ , a4 , . . . , a99 , a100) : 10, . . . , (a1 , a2 , a3 , ∗ , . . . , ∗ , ∗) : 10}? ii. If we ignore all the aggregate cells that can be obtained by replacing some constants with ∗’s while keeping the same measure value, how many distinct cells are left? What are the cells? Answer: (a) Suppose that there are only two base cells, {(a1 , a2 , a3 , . . . , a100 ), (a1 , a2 , b3 , . . . , b100 )}, in a 100dimensional base cuboid. Compute the number of nonempty aggregate cells. Comment on the storage space and time required to compute these cells. Each base cell generates 2100 −1 aggregate cells. (We subtract 1 because, for example, (a1 , a2 , a3 , . . . , a100 ) is not an aggregate cell.) Thus, the two base cells generate 2 ×(2100 −1) = 2101 −2 aggregate cells, however, four of these cells are counted twice. These four cells are: (a1 , a2 , ∗, . . . , ∗), (a1 , ∗, . . . , ∗), (∗, a2 , ∗, . . . , ∗), and (∗, ∗, . . . , ∗). Therefore, the total number of cells generated is 2101 − 6. (b) Suppose we are to compute an iceberg cube from the above. If the minimum support count in the iceberg condition is two, how many aggregate cells will there be in the iceberg cube? Show the cells. They are 4: {(a1 , a2 , ∗, . . . , ∗), (a1 , ∗, ∗, . . . , ∗), (∗, a2 , ∗, . . . , ∗), (∗, ∗, ∗, . . . , ∗)}. (c) Introducing iceberg cubes will lessen the burden of computing trivial aggregate cells in a data cube. However, even with iceberg cubes, we could still end up having to compute a large number of trivial uninteresting cells (i.e., with small counts). Suppose that a database has 20 tuples that map to (or cover) the two following base cells in a 100-dimensional base cuboid, each with a cell count of 10: {(a1 , a2 , a3 , . . . , a100 ) : 10, (a1 , a2 , b3 , . . . , b100 ) : 10}. i. Let the minimum support be 10. How many distinct aggregate cells will there be like the following: {(a1 , a2 , a3 , a4 , . . . , a99 , ∗) : 10, . . . , (a1 , a2 , ∗, a4 , . . . , a99 , a100) : 10, . . . , (a1 , a2 , a3 , ∗, . . . , ∗, ∗) : 10}? There will be 2101 − 6, as shown above. ii. If we ignore all the aggregate cells that can be obtained by replacing some constants by ∗’s while keeping the same measure value, how many distinct cells are left? What are the cells? There are only three distinct cells left: {(a1 , a2 , a3 , . . . , a100) : 10, (a1 , a2 , b3 , . . . , b100 ) : 10, (a1 , a2 , ∗, . . . , ∗) : 20}. 7. Propose an algorithm that computes closed iceberg cubes efficiently. Answer: We base our answer on the algorithm presented in the paper: “Quotient Cube: How to summarize the semantics of a data cube” by Lakshamanan, Pei, and Han. VLDB 2002. Let the cover of a cell be the set of base tuples that are aggregated in the cell. For example, if we have three base tuples, (a1 , b1 , c1 ), (a1 , b2 , c1 ), (a1 , b1 , c3 ), then the cover of (a1 , b1 , ∗) = {(a1 , b1 , c1 ), (a1 , b1 , c3 )}. Cells with the same cover can be grouped in the same class if they share the same measure. Each class will have an upper bound, which consists of the most specific cells in the class, and a lower bound, which consists of the most general cells in the class. The set of closed cells correspond to the upper bounds of all of the distinct classes that compose the cube. We can compute the classes by following a depth-first search strategy: First look for the upper bound of the cell (∗, ∗, ..., ∗). Let the cells making up this bound be u1 , u2 , ..., uk . We then specialize each ui (assign a value to a ∗ dimension) and recursively find its upper bounds. Finding the upper bounds would depend on the measure. For example, if the measure is count, we can find the upper bound by just instantiating the ∗ to a value v if all base cells share the same value in the dimension. For the above example, the upper bound of (∗, b1 , ∗) is (a1 , b1 , ∗). Incorporating iceberg conditions is not difficult. For example, if we have an antimonotonic condition such as count(∗) > k, we can stop the recursion when we reach an upper bound that does not satisfy the condition. 8. Suppose that we would like to compute an iceberg cube for the dimensions, A, B , C, D, where we wish to materialize all cells that satisfy a minimum support count of at least v, and where cardinality(A) 500. Use an iceberg cubing algorithm, such as BUC. Since avg f are > 500 is not antimonotonic, it should be converted into a top-k-avg, i.e., avg 10(f are) > 500. Use binning plus min sup to prune the computation of the cube. 11. (Implementation project) There are four typical data cube computation methods: MultiWay [ZDN97], BUC [BR99], H-cubing [HPDW01], and Star-cubing [XHLW03]. (a) Implement any one of these cube computation algorithms and describe your implementation, experimentation, and performance. Find another student who has implemented a different algorithm on the same platform (e.g., C++ on Linux) and compare your algorithm performance with his/hers. Input: i. An n-dimensional base cuboid table (for n < 20), which is essentially a relational table with n attributes ii. An iceberg condition: count (C) ≥ k where k is a positive integer as a parameter Output: i. The set of computed cuboids that satisfy the iceberg condition, in the order of your output generation ii. Summary of the set of cuboids in the form of “cuboid ID : the number of nonempty cells”, sorted in alphabetical order of cuboids, e.g., A:155, AB : 120, ABC : 22, ABCD : 4, ABCE : 6, ABD : 36, where the number after “:” represents the number of nonempty cells. (This is used to quickly check the correctness of your results.) (b) Based on your implementation, discuss the following: i. What challenging computation problems are encountered as the number of dimensions grows large? ii. How can iceberg cubing solve the problems of part (a) for some data sets (and characterize such data sets)? iii. Give one simple example to show that sometimes iceberg cubes cannot provide a good solution. (c) Instead of computing a data cube of high dimensionality, we may choose to materialize the cuboids that have only a small number of dimension combinations. For example, for a 30-dimensional data cube, we may only compute the 5-dimensional cuboids for every possible 5-dimensional combination. The resulting cuboids form a shell cube. Discuss how easy or hard it is to modify your cube computation algorithm to facilitate such computation. Answer: (a) There is no standard answer for an implementation project. This is to be evaluated on an individual basis. (b) i. What challenging computation problems are encountered as the number of dimensions grows large? The number of cuboids for a cube grows exponentially with the number of dimensions. If the number of dimension grows large, then huge amounts of memory and time are required to compute all of the cuboids. ii. How can iceberg cubing solve the problems of part (a) for some data sets (and characterize such data sets)? Iceberg cubes, by eliminating statistically insignificant aggregated cells, can substantially reduce the number of aggregate cells and therefore greatly reduce the computation. Benefits from iceberg cubing can be maximized if the data sets are sparse but not skewed. This is because in these data sets, there is a relatively low chance that cells will collapse into the same aggregated cell, except for cuboids consisting of a small number of dimensions. Thus, many cells may have values that are less than the threshold and therefore will be pruned. iii. Give one simple example to show that sometimes iceberg cubes cannot provide a good solution. Consider, for example, an OLAP database consisting of 100 dimensions. Let ai,j be the jth value of dimension i. Assume that there are 10 cells in the base cuboid, all of which aggregate to the cell (a1,1 , a2,1 , . . . , a99,1 , ∗). Let the support threshold be 10. Then, all 299 −1 aggregate cells of this cell satisfy the threshold. In this case, iceberg cubing cannot benefit from the pruning effect. Another example can be found in Question 6(c). (c) Instead of computing a data cube of high dimensionality, we may choose to materialize the cuboids having only a small number of dimension combinations. For example, for a 30-dimensional data cube, we may only compute the 5-dimensional cuboids for every possible 5-dimensional combination. The resulting cuboids form a shell cube. Discuss how easy or hard it is to modify your cube computation algorithm to facilitate such computation. It is easy to modify the algorithms if they adopt a top-down approach. Consider BUC as an example. We can modify the algorithm to generate a shell cube of a specific number of dimension combinations because it proceeds from the apex (all) cuboid, downward. The process can be stopped when it reaches the maximum number of dimensions. H-cubing and Star-Cubing can be modified in a similar manner. However, multiway array aggregation (MultiWay) is difficult to modify because it computes every cuboid at the same time. 12. The sampling cube was proposed for multidimensional analysis of sampling data (e.g., survey data). In many real applications, sampling data can be of high dimensionality, e.g., it is not unusual to have more than 50 dimensions in a survey data set. (a) How can we construct an efficient and scalable high-dimensional sampling cube in large sampling data sets? (b) Design an efficient incremental update algorithm for such a high-dimensional sampling cube, and (c) Discuss how to support quality drill-down although some low-level cells may contain empty or too few data for reliable analysis. Answer: (a) How can we construct an efficient and scalable high-dimensional sampling cube in large sampling data sets? To handle high-dimensional data, a sampling cube method called Sampling Cube Shell was developed. The algorithm is top-down. It starts at the apex cuboid and proceeds down the cuboid lattice towards the base cuboid. The search in this space is iterative and greedy: in each iteration, the best candidate cuboid is chosen and added to the shell. This process halts until some stopping condition is met. The condition could be a space constraint, e.g., the number of cuboids built cannot exceed some value. Or it could be an information constraint, e.g., the gain in building a new cuboid must exceed some minimum. Specifically speaking, initially, only the all or apex cuboid exists. By definition, it contains exactly one cell and the standard deviation of it is the standard deviation of all the samples put together. The child cuboids of the apex cuboid are then added into a candidate set. The best cuboid is computed. In the paper, the measure is the reduction in the amount of variance with respect to the cube value in its cells from one of the cuboid’s parents. Then this candidate cuboid is chosen and added to the shell. Its children in the cuboid lattice are added to the candidate set. This process iterates until a stopping criterion is met. Note that the final data structure is not strictly a tree since a node could have multiple parents. It is just a portion (i.e., shell) of the complete data cube lattice. (b) Design an efficient incremental update algorithm for such a high-dimensional sampling cube. In order to handle incremental data updates for such a high-dimensional sampling cube, the Sampling Cube Shell is first recomputed as described in (a). Then we simply compute new cuboids in the shell fragments and update the existing shell fragments. The ID table should be updated accordingly. The update is efficient since all the mean and confidence interval measures of the data cube are algebraic. Note that our cube is build top-down, so the cells in the high-level cuboids often contain quite many samples. (c) Discuss how to support quality drill-down although some low-level cells may contain empty or too few data for reliable analysis. The best way to solve this small sample size problem is to simply get more data. There are two possible methods to expand the query and get more data to boost the confidence. They both expand the original query in the data cube, just in different directions. The first one is Intra-Cuboid Query Expansion. In the intra-cuboid case, the expansion occurs by looking at nearby cells in the same cuboid as the queried cell. Dimensions which are uncorrelated or weakly correlated with the measure value (i.e., the value to be predicted) are the best candidates for expansion. Next we should select semantically similar values within those dimension(s) to minimize the risk of altering the final result. The second is Inter-Cuboid Query Expansion. Here the expansion occurs by looking to a more general cell. And the strategy is similar: correlated dimensions are not allowed in inter-cuboid expansions. Some references for the answer to this question: [1] Xiaolei Li, Jiawei Han, Zhijun Yin, Jae-Gil Lee, and Yizhou Sun, ”Sampling Cube: A Framework for Statistical OLAP over Sampling Data”, Proc. 2008 ACM SIGMOD Int. Conf. on Management of Data (SIGMOD’08), Vancouver, BC, Canada, June 2008. 13. The ranking cube was proposed for efficient computation of top-k (ranking) queries in relational databases. Recently, researchers have proposed another kind of queries, called skyline queries. A skyline query returns all the objects pi such that pi is not dominated by any other object pj , where dominance is defined as follows. Let the value of pi on dimension d be v(pi , d). We say pi is dominated by pj if and only if for each preference dimension d, v(pj , d) ≤ v (pi , d), and there is at least one d where the equality does not hold. (a) Design a ranking cube so that skyline queries can be processed efficiently. (b) Skyline queries are sometimes too strict to be desirable to some users. One may generalize the concept of skyline into generalized skyline as below: Given a d-dimensional database and a query q, the generalized skyline is the set of the following objects: (1) the skyline objects, and (2) the non-skyline objects that are ϵ-neighbors of a skyline object, where r is an ϵ-neighbor of an object p if the distance between p and r is no more than ϵ. Design a ranking cube to process generalized skyline queries efficiently. Answer: (a) Design a ranking cube so that skyline queries can be processed efficiently. In order to design a ranking cube so that skyline queries can be processed efficiently, one data partition P over the preference dimensions (e.g., price and mileage) need to be created. Using P as the template, one can summarize the data distribution over P for each cell by indicating which regions in the partition contain data belonging to the cell. For instance, P may partition data into n regions r1 , r2 , ..., rn . A cell (e.g., type = sedan ) corresponds to a subset of data, which may ′ . A data summarization remembers those m regions. only appear in m ≤ n regions r′1 , · · · , rm Comparing with a completely new data partition, the data summarization is much cheaper in both computational and storage cost. The data summarization is a bridge to join the boolean selection condition and preference search during online query processing. More specifically, the query algorithm progressively visits (in P ) a sequence of regions that are promising for user preference (e.g., rq1 , · · · , rjq), but skips those regions rqi which do not satisfy boolean selections rqi ∈ / {r1′ , · · · , r′m }). By doing this, the query processing pushes both boolean and preference pruning deep into the search. The prune procedure has two main tasks: domination pruning and boolean pruning. The domination pruning for skylines are straightforward: simply comparing the value in each dimension between the submitted entry e (i.e., data objects or regions mentioned above) and the previously discovered skylines. If e is dominated by any of them, e can be pruned. The boolean pruning is accomplished by signatures (the data summarization mentioned above), checking whether the entry e submitted to the prune procedure should be skipped or not. Specifically, every region n is associated with a value d(n) used for comparison, where d(n) = ∑j minx∈n ( i=1 N i′ (x)) is the lower bound value over the region covered by n, and Ni′(x) is the value of object x on preference dimension N i′ . Clearly, a data object t cannot be dominated by ∑j any data objects contained by region n if i=1 Ni′ (t) ≤ d(n). On the other hand, if a region n is dominated by some data object t, all child regions of n are dominated by t. By the way, every entry e comes from a heap with minimal d(e). The signature-based query processing is listed in the Figure 5.4. One can easily verify the correctness of the algorithm for skyline queries. The results are generated on Line 8, and all data objects e on Line 8 are valid skylines. This is true because: (1) e passes the boolean pruning, and thus e satisfies the boolean predicate; and (2) e passes the preference pruning, and thus e is not dominated by previous skylines. (b) Skyline queries are sometimes too strict to be desirable to some users. One may generalize the concept of skyline into generalized skyline as below: Given a d-dimensional database and a query q, the generalized skyline is the set of the following objects: (1) the skyline objects, and (2) the non-skyline objects that are ϵ-neighbors of a skyline object, where r is an ϵ-neighbor of an object p if the distance between p and r is no more than ϵ. Design a ranking cube to process generalized skyline queries efficiently. The cube which processes generalized skyline queries is similar to the one described in the question (a). We first adopt algorithm in question (a) to obtain the top-k skyline queries. To get those ϵ-neighbors, the domination pruning part for skylines in the algorithm should be modified for the purpose of pruning for ϵ-neighbors. That is, we run the algorithm again but compare the value in each dimension between the submitted entry e and the previously obtained top-k skyline queries instead. Some references for the answer to this question: [1] Dong Xin and Jiawei Han, “P-Cube: Answering Preference Queries in multiDimensional Space”, Proc. 2008 Int. Conf. on Data Engineering (ICDE’08), Figure 5.4: signature-based query processing of Exercise 5.13. Cancun, Mexico, April 2008. 14. The ranking cube was designed to support top-k (ranking) queries in relational database systems. However, ranking queries are also posed to data warehouses, where ranking is on multidimensional aggregates instead of on measures of base facts. For example, consider a product manager who is analyzing a sales database that stores the nationwide sales history, organized by location and time. In order to make investment decisions, the manager may pose the following queries: “What are the top-10 (state, year) cells having the largest total product sales? ” and he may further drill-down and ask, “What are the top-10 (city, month) cells? ” Suppose the system can perform such partial materialization to derive two types of materialized cuboids: a guiding cuboid and a supporting cuboid, where the former contains a number of guiding cells that provide concise, high-level data statistics to guide the ranking query processing, whereas the latter provides inverted indices for efficient online aggregation. (a) Derive an efficient method for computing such aggregate ranking cubes. (b) Extend your framework to handle more advanced measures. One such example could be as follows. Consider an organization donation database, where donors are grouped by “age”, “income”, and other attributes. Interesting questions include: “Which age and income groups have made the top-k average amount of donation (per-donor)? ” and “Which income group of donors has the largest standard deviation in the donation amount? ” Answer: (a) Derive an efficient method for computing such aggregate ranking cubes. The main idea is that high-level, compact data statistics can be used to guide the query processing so that promising candidates are given higher priority. In this case, higher-ranking states imply higher-ranking cities with high probability. And the combinations of higher-ranking years and higher-ranking states and cities imply the high probability of large total product sales. Specifically, the guiding cells within the guiding cuboids, as is described in the question, play the key role not only in guiding, but also in effective pruning. There exist an aggregate-bound for each guiding cell , which is derived from the materialized high-level statistics. By bounding principle, if a guiding cell’s aggregate-bound is no greater than the current top-k aggregate value, then none of the candidates generated by this. And suporting cuboids are generated corresponding to the guiding cuboids. For example, Figure 5.5 shows a sample data set R consisting of 8 base tuples and 3 attributes A, B, and C. For illustrative purposes, we create a tid column that shows the row number. The last column, Score, stores the raw score. The left side of Figure 5.6 depicts a guiding cuboid C gd (A; SU M ), which contains 3 cells; in this cuboid, only SU M has been computed. Similarly, the left side of Figure 5.7 shows the guiding cuboid C gd (B; SU M ). the right sides of Figure 5.6 and 5.7 illustrate two supporting cuboids, C sp(A) and C sp (B). For instance, cell a2 in the right side of Figure 5.6 has an inverted index of length 2 and the first element (t4, 16) indicates that a2 has a raw tuple id t4 and its raw score is 16. Figure 5.5: A sample database of Exercise 5.14. Figure 5.6: Guiding cuboid C gd (A; SU M ) and Supporting cuboid C sp (A)of Exercise 5.14. Figure 5.7: Guiding cuboid C gd (B; SU M ) and Supporting cuboid C sp (B)of Exercise 5.14. Now Consider a query asking for the top-1 SU M aggregate grouped-by AB. Initially, as illustrated in Figure 5.8, the two sorted lists are obtained from C gd (A; SU M ) and C gd (B; SU M ). The aggregate-bound of each guiding cell is initialized to be the materialized SU M and the guiding cells in each list are sorted descendingly according to the aggregate-bound. Next, we pull out the top guiding cell from each list and combine them to generate the first candidate cell, (a1 , b2 ). The intuition is straightforward as a1 and b2 have larger SU M than any other cell does. It is, however, not possible to terminate early until we verify its true aggregate value and make sure any unseen candidate cell has no greater aggregate. To verify the true aggregate, we turn to the inverted indices of a1 and b2 in C sp (A) and C sp(B), respectively. We retrieve their indices and intersect the two tid-lists, which results in {t2, t3}, and then compute the SU M of the raw scores Q (a1 , b2 ) = 10 + 50 = 60. over the intersecting tid-list, which results in Fagg ∑ Having known that SU M (a1 , b2 ) = 60, we can infer that j=2 SU M (a1 , bj ) = SU M (a1 ) − SU M (a1 , b2 ) = 123 − 60 = 63. This means that any unseen cell (a1 , bj )(j = 2) must satisfy SU M (a1, bj) ≤ 63. Thus, we update the aggregate-bound F agg (a1 ) from 123 to 63 (Figure 5.9). For the same reason, F agg (b2 ) can be updated from 157 to 97, implying that SU M (ai , b2 ) ≤ 97(i = 1) . Q ) Here, The aggregate-bound of a guiding cell g, F agg (g), is the maximum possible aggregate (F agg of any unseen candidate cell that could be combined by g . After the first candidate verification, as shown in Figure 5.9, the order of the guiding cells in the two sorted lists has changed due to the update. The top-1 cell from the two lists are now a3 and b1 , respectively. We generate the sec ond candidate (a3 , b1 ) in the same fashion. To verify it, we intersect the tid’s of a3 and b1 , which results in {t6, t7} and SU M (a3 , b1 ) = 35 + 40 = 75. Then, we update F agg (a3 ) to 120 − 75 = 45 and F agg (b1 ) to 154 − 75 = 79 and adjust the sorted lists, as shown in Figure 5.10. At the time, the maximum aggregate-bound in the sorted list for ai , F agg (a2 ) = 68, is no greater than the current top-1 aggregate value, 75. Although both F agg (b1 ) Q (ai , bj ) could are F agg (b2 ) are still greater than 75, it is impossible to find any ai such that Fagg be greater than 75. Therefore, we can terminate the query process and output (a3 , b1 ) : 75 as the final top-1. Figure 5.8: Initial sorted lists of Exercise 5.14. Figure 5.9: Sorted lists after the first candidate verification of Exercise 5.14. Similarly, the strategy described above can be easily extended to the top-k situation. And this query execution algorithm for the top-k cells QueryExec() is give in Figure 5.11 . (b) Extend your framework to handle more advanced measures. One such example could be as follows. Consider an organization donation database, where donors are grouped by “age”, “income”, and other attributes. Interesting questions include: “Which age and income groups have made the Figure 5.10: Sorted lists after the second candidate verification of Exercise 5.14. top-k average amount of donation (per-donor)? ” and “Which income group of donors has the largest standard deviation in the donation amount? ” To handle more general types of query measures, we extend QueryExec(). While the candidate generation and verification framework remains unchanged, their key difference lies in the computation of the aggregate-bound F agg (g) for any guiding cell g. By bounding principle, F agg (g ) should represent the maximum possible aggregate value of any candidate cb generated by g, i.e., Q Q . Therefore, the aggregate-bound F agg (g) ≥ Fagg (b c) must always hold for the query measure F agg for SU M cannot work for other query measures. We address the problem of aggregate-bound computation for different measures in two aspects: (1) the initialization F agg (g) for all guiding cells; and (2) how to update F agg (g). Figure 5.12 lists the guiding measures and the initial aggregate- bound for different query measures. To initialize the aggregate-bound of guiding cells for a particular query measure F agg , its corresponding guiding measures M should be already materialized. The initialization process is similar to QueryExec() in that N sorted lists are created, each containing all the guiding cells in the corresponding guiding cuboid. For each guiding cell, its materialized guiding measure values are retrieved, and its aggregate-bound is computed using Γ on the materialized measure values. Updating the aggregate-bound is equally important as the initialization because the aggregatebound is monotonically decreasing, providing an increasingly tighter bound to prune more guiding Q in the table can be cells. Starting from the measures in Figure 5.12, we can see that any Fagg derived from one or two of the four guiding measures, SU M , COU N T , M AX, and M IN . For Q (b c), where g SU M , as we have discussed, the updating procedure is F agg (g) ← F agg (g) − Fagg a guiding cell and b c is a candidate generated by g. This procedure applies to COU N T as well. For M AX and M I N , the updating procedure is as follows. We maintain the set of g’s raw scores, denoted as Sg , during the fetching process. After the intersection of the inverted indices of all guiding cells, we can also know the set of cb’s raw scores, denoted as Sbc (⊆ Sg ). Thus, the updated M AX(g) would be max(Sg − Sbc ), whereas the updated M IN (g) would be min(Sg − Sbc ). Finally, after all the updated guiding measure values are obtained, Γ can be applied to calculate the updated aggregate-bound F agg (g), which must be monotonically decreasing. Some references for the answer to this question: [1] Tianyi Wu, Dong Xin, and Jiawei Han, “ARCube: Supporting Ranking Aggregate Queries in Partially Materialized Data Cubes”, Proc. 2008 ACM SIGMOD Int. Conf. on Management of Data (SIGMOD’08), Vancouver, BC, Canada, June 2008. 15. The prediction cube is a good example of multidimensional data mining in cube space. (a) Propose an efficient algorithm that computes prediction cubes in a given multidimensional database; and (b) For what kind of classification models can your algorithm be applied. Explain. Answer: Figure 5.11: Query execution algorithm for SU M of Exercise 5.14. (a) Propose an efficient algorithm that computes prediction cubes in a given multidimensional database. A naı̈ve way to fully materialize a prediction cube is to exhaustively build models and evaluate them for each cell and for each granularity. This method is very expensive if the base data set is large. An ensemble method called Probability-Based Ensemble (PBE) was developed as a more feasible alternative. It requires model construction for only the finest-grained cells. OLAP-style bottom-up aggregation is then used to generate the values of the coarser-grained cells. Let the finest-grained subsets (i.e., finest-grained cells) be called the base subsets, denoted by bi (D), for i = 1, . . . , B, where B is the product of the sizes of the least general domains. Then every cube subset can be represented as the union of some base subsets of D, i.e., σS (D) = ∪i∈S bi (D), where S ⊆ {1, . . . , B} denotes a cube subset. The prediction of a predictive model can be seen as finding a class label that maximizes a scoring function. Formally, consider a predictive model h(X; σS (D)) trained on subset σS (D) using features X to predict the class label. The prediction of h(X; σS (D)) on input tuple x can be modeled as maximizing a scoring function Score(y|x; σS (D)); i.e., h(x|σS (D)) = argmaxy Score(y|x, σS D). The prediction of a predictive model can be seen as finding a class label that maximizes a scoring function. PBE was developed to approximately make the scoring function of any predictive model distributively decomposable. Figure 5.12: Aggregate measures and their corresponding guiding measures and aggregate-bound of Exercise 5.14. (b) For what kind of classification models can your algorithm be applied. Explain. If the scoring function used is distributively or algebraically decomposable, prediction cubes can also be computed with efficiency. Previous studies have shown that the naı̈ve Bayes classifier has an algebraically decomposable scoring function, and the kernel density-based classifier has a distributively decomposable scoring function. Therefore, either of these could be used to implement prediction cubes efficiently. The PBE method presents a novel approach to multidimensional data mining in cube space. 16. Multifeature cubes allow us to construct interesting data cubes based on rather sophisticated query conditions. Can you construct the following multifeature cube by translating the following user requests into queries using the form introduced in this textbook? (a) Construct smart shopper cube where a shopper is smart if at least 10% of the goods she buys in each shopping are on sale; and (b) Construct a datacube for best-deal products where best-deal products are those products whose price is the lowest for this product in the given month. Answer: There exist problems in this question. The “such that” phrase in the multifeature cube is not able to filter not smart shoppers, and is only able to find the cells satisfying some conditions. On the other hand, the “where” phrase is designed to be able to do the filtering. In order to build the cubes with smart shoppers, I think we first need to remove those not smart shoppers. But if we use “where” to filter shoppers, the motivation of using multifeature cube is not clear. In the example of the textbook, the multifeature cube does operations around the measure “price”, which is easier to deal with since it is not like what we need to do in the question 16 where a shopper is smart or not. In other words, the feature “is smart” is more correlated with “shopper” which cannot be aggregated easily, while “price” can be efficiently aggregated according to different dimensions like region or time (i.e. in cuboid region time, the “is smart” measure does not make sense). The “best-deal product” is similar to certain extent. 17. Discovery-driven cube exploration is a desirable way to mark interesting points among a large number of cells in a data cube. Individual users may have different views on whether a point should be considered interesting enough to be marked. Suppose one would like to mark those objects whose absolute value of Z score is over 2 in every row and column in a d-dimensional plane. (a) Derive an efficient computation method to identify such points during the data cube computation. (b) Suppose a partially materialized cube has (d−1)-dimensional and (d+ 1)-dimensional cuboids materialized but not the d-dimensional one. Derive an efficient method to mark those d-dimensional cells whose (d + 1)-dimensional children contain such marked points. Answer: (a) Derive an efficient computation method to identify such points during the data cube computation. The computation consists of two phases. The first step involves the computation of the aggregate ∑ ∑ 2 values defining the cube, including the count l, sum x and squared sum x (in order to compute the Z score). The second phase computes the Z score. Therefore, the computation of identifying such points is efficient. (b) Suppose a partially materialized cube has (d−1)-dimensional and (d+ 1)-dimensional cuboids materialized but not the d-dimensional one. Derive an efficient method to mark those d-dimensional cells whose (d + 1)-dimensional children contain such marked points. Not certain very much. Maybe I misunderstood the question. Since (d − 1)-dimensional cuboids are already materialized, for each column or row in the d∑ dimentional plane, in order x, ∑ to2 compute Z score for every cell, one can directly obtain the count l and squared sum x from the parent cell within the corresponding (d − 1)-dimensional cuboids, given the equation for Z score: Z = x−µ . δ 5.2 Supplementary Exercises 1. Iceberg conditions, such as “count(∗) ≥ min sup”, has been used to speed up the computation of iceberg cubes by pushing iceberg conditions deeply into the cube computation. Such iceberg conditions are antimonotonic constraints, i.e., if a cell cannot satisfy the constraint, its descendant cells can never satisfy the same constraint. However, in practice, iceberg conditions may not always be antimonotonic. For example, one may like to give the following conditions in computing a Sales Iceberg cube: (1) AV G(price) ≥ 800, and (2) COU N T (∗) ≥ 50. (a) State why constraint (1) cannot be pushed deeply into a typical iceberg cube computation process, (b) Design an efficient iceberg computation algorithm that will make good use of both iceberg conditions, and (c) Discuss what kind of non-antimonotonic iceberg conditions can still be pushed deeply into iceberg cube computation. Answer: (a) State why constraint (1) cannot be pushed deeply into a typical iceberg cube computation process. An anti-monotionic iceberg cube can be computed efficiently by exploring the Apriori property: if a given cell does not satisfy minimum support, then no descendant (i.e., more specialized or detailed version) of the cell will satisfy minimum support either. However, since the constraint involves the non-anti-monotonic measure average, it does not have the Apriori property. (b) Design an efficient iceberg computation algorithm that will make good use of both iceberg conditions. Although the measure average is non-anti-monotonic, we are able to find a weaker but antimonotonic auxiliary condition that may help us compute iceberg cubes efficiently. That is top-k average. A cell c is said to have n base cells if it covers n nonempty descendant base cells. The top-k average of c, denoted as avg k (c), is the average value of the top-k base cells of c (i.e., the first k cells when all the base cells in c are sorted in value-descending order) if k ≤ n; or −∞ if k > n. Then we have the Top-k Apriori : Let c be a cell which fails to satisfy avgk (c) ≥ v in cube B(AvgI ). If a cell c′ is a descendant of c, then c′ cannot satisfy avg k (c′ ) ≥ v in cube B(Sales I ceberg). Here v is the value in the constraint (800 in this quesition) and B(Sales I ceberg) is called the background cube which is the cube without the iceberg condition. Even we get the above top-k apriori property, to keep tracking of top k values for each cell in an m-dimensional space seems to be a nontrivial cost. Therefore, a binning technique is proposed which can be used to reduce the cost of storage and computation of top-k average. For example, suppose v ≥ 0, one can set up the range of five bins as follows: range(bin[1]) = [v, ∞), range(bin[2]) = [0.95v, v), range(bin[3]) = [0.85v, 0.95v), range(bin[4]) = [0.70v, 0.85v ), and range(bin[5]) = [0.50v, 0.70v). Notice since we have count and sum of all the cells, that for the remaining range [−∞, 0.50v) can be derived easily. The set of bins for a cell c can be used to judge wheter avgk (c) ≥ v is false as follows. Let m be the smallest number such that the sum of counts of the upper m bins is no less than k, i.e., ∑m countm = i=1 count(bini ) ≥ k. We approximate avgk (c) using: avg′k (c) = ( m−1 ∑ i=1 sum(bini ) + max(binm ) × nk )/k ∑m−1 where nk = k − i=1 count(bini ). Note that avg k (c) ≤ avg′k (c). Consequenty, if avg′k (c) < v, then do descendant of c can satisfy the constraint in Sales iceberg. Based on the above discussion, one can easily extend the BUC iceberg cube computation algorithm to compute iceberg cubes with average. (c) Discuss what kind of non-antimonotonic iceberg conditions can still be pushed deeply into iceberg cube computation. • • • • Compute iceberg cube whose AVG is no bigger than a value. Compute iceberg cubes with AVG constraint only. Compute iceberg cubes whose measure is SUM of positive and negative values. Compute iceberg cubes with measures like max, min, count, and p sum, where p sum means the sum of all nonnegative base cell values in a cube. • Compute iceberg cubes having conjunctions of multiple conditions with different measures. Some references for the answer to this question: [1] J. Han, J. Pei, G. Dong, K. Wang. Efficient Computation of Iceberg Cubes With Complex Measures. SIGMOD01