 3/18/2013
 2
Agenda
 Data Cube Computation: Preliminary Concepts
 Data Cube Computation Methods
 Processing Advanced Queries by Exploring Data Cube Technology
 Multidimensional Data Analysis in Cube Space
 Summary
Data Cube: A Lattice of Cuboids
Data Cube: A Lattice of Cuboids
Cube Materialization: Full Cube vs. Iceberg Cube
 Full cube vs. iceberg cube
 compute cube sales iceberg as
 select month, city, customer group, count(*)
 from salesInfo
 cube by month, city, customer group
 iceberg condition: having count(*) >= min support
 Computing only the cuboid cells whose measure satisfies the iceberg condition
 Only a small portion of cells may be “above the water’’ in a sparse cube
 Avoid explosive growth: A cube with 100 dimensions
 2 base cells: (a1, a2, …., a100), (b1, b2, …, b100)
 How many aggregate cells if “having count >= 1”?
 What about “having count >= 2”?
Iceberg Cube, Closed Cube & Cube Shell
 Is iceberg cube good enough?
 2 base cells: {(a1, a2, a3 . . . , a100):10, (a1, a2, b3, . . . , b100):10}
 How many cells will the iceberg cube have if having count(*) >= 10? Hint: A huge but tricky number!
 Close cube:
 Closed cell c: if there exists no cell d, s.t. d is a descendant of c, and d has the same measure value as c.
 Closed cube: a cube consisting of only closed cells
 What is the closed cube of the above base cuboid? Hint: only 3 cells
 Cube Shell
 Precompute only the cuboids involving a small # of dimensions, e.g., 3
 More dimension combinations will need to be computed on the fly
 For (A1, A2, … A10), how many combinations to compute?
Roadmap for Efficient Computation
 General cube computation heuristics (Agarwal et al.’96)
 Computing full/iceberg cubes: 3 methodologies
 BottomUp: MultiWay array aggregation (Zhao, Deshpande & Naughton, SIGMOD’97)
 Topdown:
 BUC (Beyer & Ramarkrishnan, SIGMOD’99)
 Hcubing technique (Han, Pei, Dong & Wang: SIGMOD’01)
 Integrating TopDown and BottomUp:
 Starcubing algorithm (Xin, Han, Li & Wah: VLDB’03)
 Highdimensional OLAP: A Minimal Cubing Approach (Li, et al. VLDB’04)
 Computing alternative kinds of cubes:
 Partial cube, closed cube, approximate cube, etc.
General Heuristics (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
 Smallestchild: computing a cuboid from the smallest, previously computed cuboid
 Cacheresults: caching results of a cuboid from which other cuboids are computed to reduce disk I/Os
 Amortizescans: computing as many as possible cuboids at the same time to amortize disk reads
 Sharesorts: sharing sorting costs cross multiple cuboids when sortbased method is used
 Sharepartitions: sharing the partitioning cost across multiple cuboids when hashbased algorithms are used
Data Cube Computation Methods
 MultiWay Array Aggregation
 BUC
 StarCubing
 HighDimensional OLAP
MultiWay Array Aggregation
 Arraybased “bottomup” algorithm
 Using multidimensional chunks
 No direct tuple comparisons
 Simultaneous aggregation on multiple dimensions
 Intermediate aggregate values are reused for computing ancestor cuboids
 Cannot do Apriori pruning: No iceberg optimization
Multiway Array Aggregation for Cube Computation (MOLAP)
 Partition arrays into chunks (a small subcube which fits in memory).
 Compressed sparse array addressing: (chunk_id, offset)
 Compute aggregates in “multiway” by visiting cube cells in the order which minimizes the # of times to visit each cell, and reduces memory access and storage cost.
Multiway Array Aggregation for Cube Computation (3D to 2D)
 The best order is the one that minimizes the memory requirement and reduced I/Os
Multiway Array Aggregation for Cube Computation (2D to 1D)
MultiWay Array Aggregation for Cube Computation (Method Summary)
 Method: the planes should be sorted and computed according to their size in ascending order
 Idea: keep the smallest plane in the main memory, fetch and compute only one chunk at a time for the largest plane
 Limitation of the method: computing well only for a small number of dimensions
 If there are a large number of dimensions, “topdown” computation and iceberg cube computation methods can be explored
BottomUp Computation (BUC)

BUC: Partitioning
 Usually, entire data set can’t fit in main memory
 Sort distinct values
 partition into blocks that fit
 Continue processing
 Optimizations
 Partitioning
 External Sorting, Hashing, Counting Sort
 Ordering dimensions to encourage pruning
 Cardinality, Skew, Correlation
 Collapsing duplicates
 Can’t do holistic aggregates anymore!
StarCubing: An Integrating Method
 D. Xin, J. Han, X. Li, B. W. Wah, StarCubing: Computing Iceberg Cubes by TopDown and BottomUp Integration, VLDB'03
 Explore shared dimensions
 E.g., dimension A is the shared dimension of ACD and AD
 ABD/AB means cuboid ABD has shared dimensions AB
 Allows for shared computations
 e.g., cuboid AB is computed simultaneously as ABD
 Aggregate in a topdown manner but with the bottomup sublayer underneath which will allow Apriori pruning
 Shared dimensions grow in bottomup fashion
Iceberg Pruning in Shared Dimensions
 Antimonotonic property of shared dimensions
 If the measure is antimonotonic , and if the aggregate value on a shared dimension does not satisfy the iceberg condition , then all the cells extended from this shared dimension cannot satisfy the condition either
 Intuition: if we can compute the shared dimensions before the actual cuboid, we can use them to do Apriori pruning
 Problem: how to prune while still aggregate simultaneously on multiple dimensions?
Cell Trees
 Use a tree structure similar to Htree to represent cuboids
 Collapses common prefixes to save memory
 Keep count at node
 Traverse the tree to retrieve a particular tuple
Star Attributes and Star Nodes

Intuition: If a singledimensional aggregate on an attribute value
p
does not satisfy the iceberg condition, it is useless to distinguish them during the iceberg computation
 E.g., b2, b3, b4, c1, c2, c4, d1, d2, d3
 Solution: Replace such attributes by a *. Such attributes are star attributes, and the corresponding nodes in the cell tree are star nodes
Example: Star Reduction

Star Tree

StarCubing Algorithm—DFS on Lattice Tree
MultiWay Aggregation
StarCubing Algorithm—DFS on StarTree
MultiWay StarTree Aggregation
 Start depthfirst search at the root of the base star tree
 At each new node in the DFS, create corresponding star tree that are descendents of the current tree according to the integrated traversal ordering
 E.g., in the base tree, when DFS reaches a1, the ACD/A tree is created
 When DFS reaches b*, the ABD/AD tree is created
 The counts in the base tree are carried over to the new trees
MultiWay Aggregation (2)
 When DFS reaches a leaf node (e., d*), start backtracking
 On every backtracking branch, the count in the corresponding trees are output, the tree is destroyed, and the node in the base tree is destroyed
 Example
 When traversing from d* back to c*, the a1b*c*/a1b*c* tree is output and destroyed
 When traversing from c* back to b*, the a1b*D/a1b* tree is output and destroyed
 When at b*, jump to b1 and repeat similar process
The Curse of Dimensionality
 None of the previous cubing method can handle high dimensionality!
 A database of 600k tuples. Each dimension has cardinality of 100 and zipf of 2.
Motivation of HighD OLAP
 X. Li, J. Han, and H. Gonzalez, HighDimensional OLAP: A Minimal Cubing Approach, VLDB'04
 Challenge to current cubing methods:
 The “curse of dimensionality’’ problem
 Iceberg cube and compressed cubes: only delay the inevitable explosion
 Full materialization: still significant overhead in accessing results on disk
 HighD OLAP is needed in applications
 Science and engineering analysis
 Biodata analysis: thousands of genes
 Statistical surveys: hundreds of variables
Fast HighD OLAP with Minimal Cubing
 Observation: OLAP occurs only on a small subset of dimensions at a time
 SemiOnline Computational Model
 Partition the set of dimensions into shell fragments
 Compute data cubes for each shell fragment while retaining inverted indices or valuelist indices
 Given the precomputed fragment cubes , dynamically compute cube cells of the highdimensional data cube online
Properties of Proposed Method
 Partitions the data vertically
 Reduces highdimensional cube into a set of lower dimensional cubes
 Online reconstruction of original highdimensional space
 Lossless reduction
 Offers tradeoffs between the amount of preprocessing and the speed of online computation
Example Computation
 Let the cube aggregation function be count
 Divide the 5 dimensions into 2 shell fragments:
(A, B, C) and (D, E)
1D Inverted Indices
 Build traditional invert index or RID list
Shell Fragment Cubes: Ideas
 Generalize the 1D inverted indices to multidimensional ones in the data cube sense
 Compute all cuboids for data cubes ABC and DE while retaining the inverted indices
 For example, shell fragment cube ABC contains 7 cuboids:
 A, B, C
 AB, AC, BC
 ABC
 This completes the offline computation stage
Shell Fragment Cubes: Size and Design

Given a database of T tuples, D dimensions, and F shell fragment size, the fragment cubes’ space requirement is:
\[ O\left ( T\left \lceil \frac{D}{F} \right \rceil(2^{F}1) \right ) \]  For F < 5, the growth is sublinear
 Shell fragments do not have to be disjoint
 Fragment groupings can be arbitrary to allow for maximum online performance

Known common combinations (e.g.,
) should be grouped together.  Shell fragment sizes can be adjusted for optimal balance between offline and online computation
ID_Measure Table
 If measures other than count are present, store in ID_measure table separate from the shell fragments
The FragShells Algorithm
 Partition set of dimension (A1,…,An) into a set of k fragments (P1,…,Pk).

Scan base table once and do the following

insert
into ID_measure table. 
for each attribute value ai of each dimension Ai

build inverted index entry

build inverted index entry

insert

For each fragment partition Pi
 build local fragment cube Si by intersecting tidlists in bottom up fashion.
FragShells (cont')
Online Query Computation: Query
 A query has the general form <a1,a2,...an: M>
 Each ai has 3 possible values
 Instantiated value
 Aggregate * function
 Inquire ? function
 For example, <3 ? ? * 1: count> returns a 2D data cube.
Online Query Computation: Method
 Given the fragment cubes, process a query as follows
 Divide the query into fragment, same as the shell
 Fetch the corresponding TID list for each fragment from the fragment cube
 Intersect the TID lists from each fragment to construct instantiated base table
 Compute the data cube using the base table with any cubing algorithm
Online Query Computation: Sketch
Experiment: Size vs. Dimensionality (50 and 100 cardinality)
 (50C): 106 tuples, 0 skew, 50 cardinality, fragment size 3.
 (100C): 106 tuples, 2 skew, 100 cardinality, fragment size 2.
Experiments on Real World Data
 UCI Forest CoverType data set
 54 dimensions, 581K tuples
 Shell fragments of size 2 took 33 seconds and 325MB to compute
 3D subquery with 1 instantiate D: 85ms~1.4 sec.
 Longitudinal Study of Vocational Rehab. Data
 24 dimensions, 8818 tuples
 Shell fragments of size 3 took 0.9 seconds and 60MB to compute
 5D query with 0 instantiated D: 227ms~2.6 sec.
Processing Advanced Queries by Exploring Data Cube Technology
 Sampling Cube
 X. Li, J. Han, Z. Yin, J.G. Lee, Y. Sun, “Sampling Cube: A Framework for Statistical OLAP over Sampling Data”, SIGMOD’08
 Ranking Cube
 D. Xin, J. Han, H. Cheng, and X. Li. Answering topk queries with multidimensional selections: The ranking cube approach. VLDB’06
 Other advanced cubes for processing data and queries
 Stream cube, spatial cube, multimedia cube, text cube, RFID cube, etc. — to be studied in volume 2
Statistical Surveys and OLAP

Statistical survey: A popular tool to collect information about a
population
based on a
sample
 Ex.: TV ratings, US Census, election polls
 A common tool in politics, health, market research, science, and many more
 An efficient way of collecting information (Data collection is expensive)
 Many statistical tools available, to determine validity
 Confidence intervals
 Hypothesis tests
 OLAP (multidimensional analysis) on survey data
 highly desirable but can it be done well?
Surveys: Sample vs. Whole Population
Data is only a sample of population
Problems for Drilling in Multidim. Space
 Data is only a sample of population but samples could be small when drilling to certain multidimensional space
OLAP on Survey (i.e., Sampling) Data
 Semantics of query is unchanged
 Input data has changed
Challenges for OLAP on Sampling Data
 Computing confidence intervals in OLAP context
 No data?
 Not exactly. No data in subspaces in cube
 Sparse data
 Causes include sampling bias and query selection bias
 Curse of dimensionality
 Survey data can be high dimensional
 Over 600 dimensions in real world example
 Impossible to fully materialize
Example 1: Confidence Interval
 What is the average income of 19yearold highschool students?
 Return not only query result but also confidence interval
Confidence Interval

Confidence interval at x':

x is a sample of data set;x' is the mean of sample
tc is the critical tvalue, calculated by a lookup
is the estimated standard error of the mean 
Example
:
$50,000 ± $3,000 with 95% confidence
 Treat points in cube cell as samples
 Compute confidence interval as traditional sample set

Return answer in the form of confidence interval
 Indicates quality of query answer
 User selects desired confidence interval
Efficient Computing Confidence Interval Measures
 Efficient computation in all cells in data cube
 Both mean and confidence interval are algebraic
 Why confidence interval measure is algebraic?
\[ \bar{x}\pm t_{c}\hat{\sigma}_{\bar{x}} \]
x' is algebraic
\[ \hat{\sigma}_{\bar{x}}=\frac{s}{\sqrt{l}} \]
where both s and l (count) are algebraic
 Thus one can calculate cells efficiently at more general cuboids without having to start at the base cuboid each time
Example 2: Query Expansion
 What is the average income of 19yearold college students?
Boosting Confidence by Query Expansion
 From the example: The queried cell “19yearold college students” contains only 2 samples
 Confidence interval is large (i.e., low confidence). why?
 Small sample size
 High standard deviation with samples
 Small sample sizes can occur at relatively low dimensional selections
 Collect more data?― expensive!
 Use data in other cells? Maybe, but have to be careful
IntraCuboid Expansion: Choice 1
 Expand query to include 18 and 20 year olds?
IntraCuboid Expansion: Choice 2
 Expand query to include highschool and graduate students?
Query Expansion
IntraCuboid Expansion
 Combine other cells’ data into own to “boost” confidence
 If share semantic and cube similarity
 Use only if necessary
 Bigger sample size will decrease confidence interval
 Cell segment similarity
 Some dimensions are clear: Age
 Some are fuzzy: Occupation
 May need domain knowledge
 Cell value similarity
 How to determine if two cells’ samples come from the same population?
 Twosample ttest (confidencebased)
InterCuboid Expansion
 If a query dimension is
 Not correlated with cube value
 But is causing small sample size by drilling down too much
 Remove dimension (i.e., generalize to *) and move to a more general cuboid
 Can use twosample ttest to determine similarity between two cells across cuboids
 Can also use a different method to be shown later
Query Expansion Experiments
 Real world sample data: 600 dimensions and 750,000 tuples
 0.05% to simulate “sample” (allows error checking)
Ranking Cubes – Efficient Computation of Ranking queries
 Data cube helps not only OLAP but also ranked search
 (topk) ranking query: only returns the best k results according to a userspecified preference, consisting of (1) a selection condition and (2) a ranking function
 Ex.: Search for apartments with expected price 1000 and expected square feet 800
 Select top 1 from Apartment
 where City = “LA” and Num_Bedroom = 2
 order by [price – 1000]^2 + [sq feet  800]^2 asc
 Efficiency question: Can we only search what we need?
 Build a ranking cube on both selection dimensions and ranking dimensions
Ranking Cube: Partition Data on Both Selection and Ranking Dimensions
Materialize RankingCube
Search with RankingCube: Simultaneously Push Selection and Ranking
Processing Ranking Query: Execution Trace
Ranking Cube: Methodology and Extension
 Ranking cube methodology
 Push selection and ranking simultaneously
 It works for many sophisticated ranking functions
 How to support highdimensional data?
 Materialize only those atomic cuboids that contain single selection dimensions
 Uses the idea similar to highdimensional OLAP
 Achieves low space overhead and high performance in answering ranking queries with a high number of selection dimensions
Data Mining in Cube Space
 Data cube greatly increases the analysis bandwidth
 Four ways to interact OLAPstyled analysis and data mining
 Using cube space to define data space for mining
 Using OLAP queries to generate features and targets for mining, e.g., multifeature cube
 Using datamining models as building blocks in a multistep mining process, e.g., prediction cube
 Using datacube computation techniques to speed up repeated model construction
 Cubespace data mining may require building a model for each candidate data space
 Sharing computation across modelconstruction for different candidates may lead to efficient mining
Prediction Cubes
 Prediction cube: A cube structure that stores prediction models in multidimensional data space and supports prediction in OLAP manner
 Prediction models are used as building blocks to define the interestingness of subsets of data, i.e., to answer which subsets of data indicate better prediction
How to Determine the Prediction Power of an Attribute?
 Ex. A customer table D:
 Two dimensions Z: Time (Month, Year ) and Location (State, Country)
 Two features X: Gender and Salary
 One classlabel attribute Y: Valued Customer
 Q: “Are there times and locations in which the value of a customer depended greatly on the customers gender (i.e., Gender: predictiveness attribute V)?”
 Idea:
 Compute the difference between the model built on that using X to predict Y and that built on using X – V to predict Y
 If the difference is large, V must play an important role at predicting Y
Efficient Computation of Prediction Cubes
 Naïve method: Fully materialize the prediction cube, i.e., exhaustively build models and evaluate them for each cell and for each granularity
 Better approach: Explore score function decomposition that reduces prediction cube computation to data cube computation
Complex Aggregation at Multiple Granularities: MultiFeature Cubes
 Multifeature cubes (Ross, et al. 1998): Compute complex queries involving multiple dependent aggregates at multiple granularities

Ex. Grouping by all subsets of {item, region, month}, find the maximum price in 2010 for each group, and the total sales among all maximum price tuples
select item, region, month, max(price), sum(R.sales)
from purchases
where year = 2010
cube by item, region, month: R
such that R. price = max(price)  Continuing the last example, among the max price tuples, find the min and max shelf live, and find the fraction of the total sales due to tuple that have min shelf life within the set of all max price tuples
DiscoveryDriven Exploration of Data Cubes
 Hypothesisdriven
 exploration by user, huge search space
 Discoverydriven (Sarawagi, et al.’98)
 Effective navigation of large OLAP data cubes
 precompute measures indicating exceptions, guide user in the data analysis, at all levels of aggregation
 Exception: significantly different from the value anticipated, based on a statistical model
 Visual cues such as background color are used to reflect the degree of exception of each cell
Kinds of Exceptions and their Computation
 Parameters
 SelfExp: surprise of cell relative to other cells at same level of aggregation
 InExp: surprise beneath the cell
 PathExp: surprise beneath cell for each drilldown path
 Computation of exception indicator (modeling fitting and computing SelfExp, InExp, and PathExp values) can be overlapped with cube construction
 Exception themselves can be stored, indexed and retrieved like precomputed aggregates
Examples: DiscoveryDriven Data Cubes
HCubing: Using HTree Structure
