Unit 4

Data Cube Technology

 Efficient Method for Data Cube
Computation
• Data cube computation is an essential task in data warehouse implementation.
The precomputation of all or part of a data cube can greatly reduce the
response time and enhance the performance of on-line analytical processing.
• However, such computation is challenging because it may require
substantial computational time and storage space.
• Grouping of data in a multidimensional matrix is called data cubes. In Dataware
housing, we generally deal with various multidimensional data models as the
data will be represented by multiple dimensions and multiple attributes.
• This multidimensional data is represented in the data cube as the cube
represents a high-dimensional space.
The Data cube pictorially shows how different attributes of data are
arranged in the data model.

The example above is a 3D cube having attributes like

branch(A,B,C,D),itemtype(home,entertainment,computer,phone,securi
ty), year(1997,1998,1999) .
 Data cube classification:

The data cube can be classified into two categories:

• Multidimensional data cube: It basically helps in storing large
amounts of data by making use of a multi-dimensional array. It
increases its efficiency by keeping an index of each dimension. Thus,
dimensional is able to retrieve data fast.
• Relational data cube: It basically helps in storing large amounts of
data by making use of relational tables. Each relational table displays
the dimensions of the data cube. It is slower compared to a
Multidimensional Data Cube.
 Efficient Methods for Data Cube
Computation
Cube Materialization
• The figure shows a 3-D data cube for the dimensions A, B, and C for
some aggregate measure, M. A data cube is a lattice of cuboids.
 Efficient Methods for Data Cube
Computation
Cube Materialization
• Each cuboid represents a group-by. ABC is the base cuboid,
containing all three of the dimensions. The base cuboid is the least
generalized of all of the cuboids in the data cube.
• The most generalized cuboid is the apex cuboid, commonly
represented as all. It contains one value.
• To drill down in the data cube, we move from the apex cuboid,
downward in the lattice. To roll up, we move from the base cuboid,
upward.
 Efficient Methods for Data Cube
Computation
Cube Materialization
• In order to ensure fast on-line analytical processing, it is
sometimes desirable to precompute cubes. The different kinds of
cubes that can be precomputed are given below.
• Full Cube
• Iceberg Cube
• Close Cube
• Shell Cube
 Efficient Methods for Data Cube
Computation
Full Cube
• Full cube is the data cube in which all cells or cuboids for the data
cube are precomputed.
• This, however, is exponential to the number of dimensions. That
is, a data cube of n dimensions contains 2n cuboids. There are even
more cuboids if we consider concept hierarchies for each
dimension.
• Thus, precomputation of the full cube can require huge and
often excessive amounts of memory.
 Example of full cube

Dimensions: Time, Product, Location

Cuboids in Full Cube:
(Time, Product, Location) → base cuboid
(Time, Product)
(Time, Location)
(Product, Location)
(Time)
(Product)
(Location)
(∅) → apex→ apex cuboid (grand total)
 Full cube …

• When to use
• When storage is not a problem
• When queries require many different grouping combinations
• Advantages
• Fastest query performance
• Every possible aggregation is precomputed
• Disadvantages
• Extremely high storage cost
• High processing cost during cube construction
 Efficient Methods for Data Cube
Computation
Iceberg Cube
• Instead of computing the full cube, we can compute only a subset of the
data cube’s cuboids.
• In many situations, it is useful to materialize only those cells in a cuboid
(group-by) whose measure value is above some minimum threshold.
• For example, in a data cube for sales, we may wish to materialize only those
cells for which count>10, or only those cells representing sales>$100.
Such partially materialized cubes are known as iceberg cubes.
• An Iceberg Cube materializes only those cuboids whose aggregate values satisfy
a minimum threshold (e.g., SUM > 10,000 or COUNT > 50).
• This avoids storing small, insignificant aggregation results.
 Example of iceberg cube

Threshold rule:
SUM(Sales) ≥ 10,000
Cuboids materialized:

Combination SUM(Sales) Stored?

A-Kathmandu 15,000 ✔
✖ (Below threshold
B-Pokhara 2,000
— not materialized)
 Iceberg cube …

• When to use
• When the user is interested only in significant patterns
• When saving storage space is important
• Advantages
• Reduces storage dramatically
• Faster cube computation
• Good for mining frequent/important patterns
• Disadvantages
• Small or rare patterns are lost
• Querying ignored patterns becomes slower
 Efficient Methods for Data Cube
Computation
Closed Cube
• A Closed Cube materializes only closed cuboids, which are cuboids whose
aggregate value cannot be found in any of their parent cuboids.
• Meaning:
→ A cuboid is “closed” if no larger (more general) cuboid has the same
aggregate value.
→ Redundant cuboids are removed.
 Example of closed cube

Dimensions: Product, Region, Month

Measure: Sales
Product Region Month Sales
Mobile Bagmati Jan 100
Mobile Bagmati Feb 50
Laptop Bagmati Jan 150
Laptop Lumbini Jan 80
1: Base Cuboid (Lowest level – all base cells)

Product Region Month Sales

Mobile Bagmati Jan 100
Mobile Bagmati Feb 50
Laptop Bagmati Jan 150
Laptop Lumbini Jan 80

Base cells always stored, no redundancy removed at this level.

2: Intermediate Aggregate Cells (1 dimension rolled up)
A) Product + Region (Month rolled up → ALL)
Product Region Sales
Mobile Bagmati 100 + 50 = 150
Laptop Bagmati 150
Laptop Lumbini 80

B) Region only (Product rolled up → ALL)

Region Sales
Bagmati 150 + 150 = 300
Lumbini 80

C) Product only (Region rolled up → ALL)

Product Sales
Mobile 150
Laptop 150 + 80 = 230
3: Identify Redundant Cells
• Rule: A cell is redundant if its aggregate value is exactly the same as
in a more general cuboid.
• Check Product+Region vs Product-only
• Mobile–Bagmati = 150
• Mobile (all regions) = 150
• Observation: Mobile–Bagmati = 150 Same value → redundant → Remove
• Check Product+Region vs Region-only
• Laptop–Bagmati = 150
• Bagmati (all products) = 300 → Not same → Keep
• Laptop–Lumbini = 80
• Lumbini (all products) = 80 → Same value → redundant → Remove
 Closed cube…

• When to use
• When removing redundancy is important
• When you want compact but lossless information
• Advantages
• No redundant cuboids
• Storage savings without losing important information
• More complete than Iceberg Cube
• Disadvantages
• Computationally complex
• Understanding closed sets requires additional logic
 Efficient Methods for Data Cube
Computation
Shell Cube
• Another strategy for partial materialization is to precompute only the cuboids involving a small number
of dimensions, such as 3 to 5. These cuboids form a shell cube.
• Queries on additional combinations of the dimensions will have to be computed on the fly.

• For example, we could compute all cuboids with 3 dimensions or less in an n-dimensional data cube,

resulting in a Shell cube of size 3.

• A Shell Cube materializes:

• The Base cuboid (full dimensions)

• The Apex cuboid (empty group-by)

• A few selected intermediate-level cuboids based on usage patterns
• It is a middle-ground approach between full cube and partial cube.
 Example of shell cube
Dimensions: Time, Product, Location
Shell cube might store:
• (Time, Product, Location) → base cuboid
• (Time, Product)
• (Product, Location)
• (∅) → apex cuboid
Other cuboids like (Time, Location) or (Time) may not be stored.
 Shell cube ….

• When to use
• When you want a balance between:
• Storage cost
• Query performance
• When some cuboids are queried more frequently
• Advantages
• Storage-efficient
• Allows reasonably fast querying
• Practical in real-world systems
• Disadvantages
• Less flexible than a full cube
• Queries requiring non-materialized cuboids will be slower
 General Strategies for Efficient Cube
Computation
• The following are general optimization techniques for the efficient
computation of data cubes.
Optimization Technique 1: Sorting, hashing, and grouping
• Sorting, hashing, and grouping operations should be applied to the
dimension attributes in order to reorder and cluster related tuples.
• In cube computation, aggregation is performed on the tuples (or
cells) that share the same set of dimension values.
• For example, to compute total sales by branch, day, and item, it is more
efficient to sort tuples or cells by branch, and then by day, and then
group them according to the item name.
 General Strategies for Efficient Cube
Computation
• Optimization Technique 2: Simultaneous aggregation and
caching intermediate results
• In cube computation, it is efficient to compute higher-level
aggregates from previously computed lower-level aggregates,
rather than from the base fact table.
• Moreover, simultaneous aggregation from cached intermediate
computation results may lead to the reduction of expensive disk
I/O operations.
• For example, to compute sales by branch, we can use the
intermediate results derived from the computation of a lower-
level cuboid, such as sales by branch and month.
 General Strategies for Efficient Cube
Computation
• Optimization Technique 3: Aggregation from the smallest
child, when there exist multiple child cuboids.
• When there exist multiple child cuboids, it is usually more
efficient to compute the desired parent (i.e., more generalized)
cuboid from the smallest, previously computed child cuboid.
• For example, to compute a sales cuboid, Cbranch, when there exist
two previously computed cuboids, C{branch,year} and C{branch,item}, it is
obviously more efficient to compute Cbranch from the former than
from the latter if there are many more distinct items than distinct
years.
 General Strategies for Efficient Cube
Computation
• Optimization Technique 4: The Apriori pruning method can
be explored to compute iceberg cubes efficiently
• The Apriori property, in the context of data cubes, states as
follows: If a given cell does not satisfy minimum threshold, then no
descendant of the cell will satisfy minimum threshold. This
property can be used to substantially reduce the computation of
iceberg cubes.
 Attribute Oriented Induction for Data
Characterization
• The attribute-oriented induction (AOI) approach to concept
description is alternative of the data cube approach.
• Generally, the data cube approach performs off-line
aggregation before an OLAP or data mining query is submitted
for processing.
• On the other hand, the attribute-oriented induction approach is
basically a query-oriented and performs on-line data analysis.
 Attribute Oriented Induction for Data
Characterization
• The general idea of attribute-oriented induction is to first collect
the task-relevant data using a database query and then perform
generalization based on the examination of the number of
distinct values of each attribute in the relevant set of data.
• The generalization is performed by either attribute removal or
attribute generalization. The following examples illustrate the
process of attribute-oriented induction.
 Attribute Oriented Induction for Data
Characterization
Example: Suppose that a user would like to describe the general
characteristics of graduate students in the Big University database,
given the attributes Name, Gender, Major, BirthPlace, BirthDate,
Residence, Phone#, and GPA. A data mining query for this
characterization can be expressed in the data mining query language,
DMQL, as follows:
Use BigUniversityDB
mine characteristics as “GraduateStudents”
in relevance to Name, Gender, Major, BirthPlace, BirthDate,
Residence, Phone#, GPA
From Student
where Status in “Graduate”
 Attribute Oriented Induction for Data
Characterization
• The data mining query presented above is transformed into the
following relational query for the collection of the task-relevant
set of data:
Use BigUniversityDB
Select Name, Gender, Major, BirthPlace, BirthDate, Residence, Phone#, GPA
From student
Where status in {“[Link].”, “M.A.”, “M.B.A.”, “Ph.D.”}
• The result of above query is called the (task-relevant) initial
working relation. Now that the data are ready for attribute-
oriented induction.
 Attribute Oriented Induction for Data
Characterization
• Attribute removal is based on the following rule
1. If there is a large set of distinct values for an attribute of the initial
working relation, but there is no generalization operator on the
attribute (e.g., there is no concept hierarchy defined for the
attribute) then remove the attribute

Attribute Values
Employee Name 5000 distinct names
Age 18–65

If Employee Name has no concept hierarchy (like grouping into departments), it should be
removed, because it is too detailed to generalize.
 Attribute Oriented Induction for Data
Characterization
• Attribute removal is based on the following rule
2. If there is a large set of distinct values for an attribute of the
initial working relation, but its higher-level concepts are expressed in
terms of other attributes, then the attribute should be removed from the
working relation.

Attributes Values
City Kathmandu, Pokhara…
State Bagmati, Gandaki…
If State already captures the higher-level grouping of City, and you are generalizing at the State
level, City may be removed to simplify analysis.
 Attribute Oriented Induction for Data
Characterization
• Attribute generalization is based on the City State Country
following rule: Kathmandu Bagmati Nepal
• If there is a large set of distinct Lalitpur Bagmati Nepal
values for an attribute in the initial Pokhara Gandaki Nepal
working relation, and there exists a •Attribute: City (many distinct values)
set of generalization operators on •Concept hierarchy exists: City → State →
the attribute, then a generalization Country
operator should be selected and •Generalization operator: Map City to State
applied to the attribute. •Resulting generalization reduces distinct
values and simplifies analysis

State Country
Bagmati Nepal
Gandaki Nepal
Mining Class Comparisons: Discriminating
between Different Classes
• In many applications, users may not be interested in having a single
class (or concept) described or characterized, but rather would prefer
to mine a description that compares or distinguishes one class (or
concept) from other comparable classes (or concepts).
• Class discrimination or comparison mines descriptions that
distinguish a target class from its contrasting classes.
• The target and contrasting classes must be comparable in the sense that
they share similar dimensions and attributes. For example, the three
classes, person, address, and item, are not comparable. However, the
sales in the last three years are comparable classes, and so are
computer science students versus physics students.
 class comparison

• Class comparison is used in data mining to identify differences and patterns between a target class

(e.g., a group of interest) and one or more contrasting classes (e.g., other groups for comparison).

1. Data Collection:

The set of relevant data in the database is collected by query processing and is partitioned

respectively into a target class and one or a set of contrasting class(es). Relevant data is selected

from the database using query processing.

The data is partitioned into classes:

• Target class: The main group of interest (e.g., customers who defaulted on a loan).
• Contrasting class(es): Groups used for comparison (e.g., customers who did not default).
Example:
• Dataset: Customer loan records
• Target class: Defaulted loans
• Contrasting class: Non-defaulted loans
 class comparison
2. Dimension Relevance Analysis:
• If there are many dimensions, then dimension relevance analysis should
be performed on these classes to select only the highly relevant dimensions
for further analysis.
• If there are many attributes (dimensions) in the data, not all are useful for
comparison.
• Dimension relevance analysis identifies the most important/relevant attributes
for distinguishing between classes.
• Irrelevant dimensions are excluded to reduce noise and simplify the analysis.
Example:
• Attributes: Age, Occupation, City, Salary, Account Balance
• Relevant dimensions for loan default comparison: Age, Salary, Account Balance
• Irrelevant dimensions: Name, Phone number
 class comparison

3. Synchronous Generalization:
• Generalization is performed on the target class and contrasting class(es) to the
level controlled by a user- or expert-specified dimension threshold.
• Both the target class and the contrasting class(es) are generalized
simultaneously.
• Generalization is controlled by a dimension threshold specified by the user or
an expert, which defines the level of abstraction.
• This ensures both classes are comparable at the same level of detail.
Example:
• City → State → Country
• Age → Age Group (e.g., 20–30, 31–40)
• Both defaulted and non-defaulted classes are generalized to these levels for
 class comparison
4. Presentation of the Derived Comparison:
• The resulting class comparison description can be visualized in
the form of tables, graphs, and rules.
• This presentation usually includes a “contrasting” measure such as
count% (percentage count).
• The user can adjust the comparison description by applying
drill-down, roll-up, and other OLAP operations to the target and
contrasting classes, as desired.
Non-defaulted
Age Group Defaulted Count Defaulted % Non-defaulted %
Count
20–30 50 25% 150 30%
31–40 100 50% 200 40%
41–50 50 25% 150 30%

Here, you can see contrasting patterns between the classes.