Data Mining_ Concepts and Techniques - Jiawei Han [151]
5.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.
(b) For what kind of classification models can your algorithm be applied? Explain.
5.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 a smart shopper cube where a shopper is smart if at least 10% of the goods she buys in each shopping trip are on sale.
(b) Construct a data cube for best-deal products where best-deal products are those products for which the price is the lowest for this product in the given month.
5.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 of which the 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 − 1)-dimensional cells with d-dimensional children that contain such marked points.
5.7. Bibliographic Notes
Efficient computation of multidimensional aggregates in data cubes has been studied by many researchers. Gray, Chaudhuri, Bosworth, et al. [GCB+97] proposed cube-by as a relational aggregation operator generalizing group-by, crosstabs, and subtotals, and categorized data cube measures into three categories: distributive, algebraic, and holistic. Harinarayan, Rajaraman, and Ullman [HRU96] proposed a greedy algorithm for the partial materialization of cuboids in the computation of a data cube. Sarawagi and Stonebraker [SS94] developed a chunk-based computation technique for the efficient organization of large multidimensional arrays. Agarwal, Agrawal, Deshpande, et al. [AAD+96] proposed several guidelines for efficient computation of multidimensional aggregates for ROLAP servers.
The chunk-based MultiWay array aggregation method for data cube computation in MOLAP was proposed in Zhao, Deshpande, and Naughton [ZDN97]. Ross and Srivastava [RS97] developed a method for computing sparse data cubes. Iceberg queries are first described in Fang, Shivakumar, Garcia-Molina, et al. [FSGM+98]. BUC, a scalable method that computes iceberg cubes from the apex cuboid downwards, was introduced by Beyer and Ramakrishnan [BR99]. Han, Pei, Dong, and Wang [HPDW01] introduced an H-Cubing method for computing iceberg cubes with complex measures using an H-tree structure.
The Star-Cubing method for computing iceberg cubes with a dynamic star-tree structure was introduced by Xin, Han, Li, and Wah [XHLW03]. MM-Cubing, an efficient iceberg cube computation method that factorizes the lattice space was developed by Shao, Han, and Xin [SHX04]. The shell-fragment-based cubing approach for efficient high-dimensional OLAP was proposed by Li, Han, and Gonzalez [LHG04].
Aside from computing iceberg cubes, another way to reduce data cube computation is to materialize condensed, dwarf, or quotient cubes, which are variants of closed cubes. Wang, Feng, Lu, and Yu proposed computing a reduced data cube, called a condensed cube[WLFY02]. Sismanis, Deligiannakis, Roussopoulos, and Kotids proposed computing a compressed data cube, called a dwarf cube [SDRK02]. Lakeshmanan, Pei, and Han proposed a quotient cube structure to summarize a data cube's semantics [LPH02], which has been further extended to a qc-tree structure by Lakshmanan, Pei, and