数据挖掘理论与技术4.pptVIP

Data Mining: Concepts and Techniques 知识挖掘理论和技术Knowledge Mining Theory and Technology— Chapter 4 — 魏玮 计算机科学与软件学院 河北工业大学 weiwei@scse.hebut.edu.cn Chapter 4: Data Cube Computation and Data Generalization 4.1 Efficient Computation of Data Cubes 4.2 Exploration and Discovery in Multidimensional Databases 4.3 Attribute-Oriented Induction ─ An Alternative Data Generalization Method 4.1 Efficient Computation of Data Cubes Preliminary cube computation tricks (Agarwal et al.’96) Computing full/iceberg cubes: 3 methodologies Top-Down: Multi-Way array aggregation (Zhao, Deshpande Naughton, SIGMOD’97) Bottom-Up: 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. Fig 4.1 Fig 4.2 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 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 4.1.2 Multi-Way Array Aggregation Array-based “bottom-up” algorithm Using multi-dimensional chunks No direct tuple comparisons Simultaneous aggregation on multiple dimensions Intermediate aggregate values are re-used for computing ancestor cuboids Cannot do