数据泛化 data cub computation and data generalization数据泛化 data cube computation and data generalization数据泛化 data cube computation and data generalization数据泛化 data cube computation and data generalization.ppt

Data Mining: Concepts and Techniques Data Mining:  Concepts and Techniques — Chapter 4 — Chapter 4: Data Cube Computation and Data Generalization Efficient Computation of Data Cubes Exploration and Discovery in Multidimensional Databases Attribute-Oriented Induction ─ An Alternative Data Generalization Method Efficient Computation of Data Cubes Computing full/iceberg cubes: 3 methodologies bottom-up: Multi-Way array aggregation (Zhao, Deshpande Naughton, SIGMOD’97) top-down: Bottom-up computation: BUC (Beyer Ramarkrishnan, SIGMOD’99) H-cubing technique (Han, Pei, Dong Wang: SIGMOD’01) Integrating Top-Down and Bottom-Up: Star-cubing algorithm (Xin, Han, Li Wah: VLDB’03) High-dimensional OLAP: A Minimal Cubing Approach (Li, et al. VLDB’04) Computing alternative kinds of cubes: Partial cube, closed cube, approximate cube, etc. Preliminary Tricks (Agarwal et al. VLDB’96) Sorting, hashing, and grouping operations are applied to the dimension attributes in order to reorder and cluster related tuples Aggregates may be computed from previously computed aggregates, rather than from the base fact table Smallest-child: computing a cuboid from the smallest, previously computed cuboid Cache-results: caching results of a cuboid from which other cuboids are computed to reduce disk I/Os Preliminary Tricks (Agarwal et al. VLDB’96) Amortize-scans: computing as many as possible cuboids at the same time to amortize disk reads Share-sorts: sharing sorting costs cross multiple cuboids when sort-based method is used Share-partitions: sharing the partitioning cost across multiple cuboids when hash-based algorithms are used Multi-Way Array Aggregation Array-based “bottom-up” algorithm Simultaneous aggregation on multiple dimensions Intermediate aggregate values are re-used for computing ancestor cuboids Cannot do Apriori pruning: No iceberg optimization Multi-way Array Aggregation for Cube Computation (MOLAP) Partition arrays into chunks Compressed sparse array addressing: (ch