数据挖掘课件 第四讲.ppt

Data Mining: Concepts and Techniques Data Mining:  Concepts and Techniques — Chapter 4 — Jiawei Han Department of Computer Science University of Illinois at Urbana-Champaign /~hanj ?2006 Jiawei Han and Micheline Kamber, All rights reserved 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 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. 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 Multi-Way Array Aggregation Array-based “bottom-up” algorithm Using multi-dimensional chunks No direct tuple comparisons Simultaneous aggregation on multiple dimensions Intermediate aggregate val