• 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

• 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.

• X. Li, J. Han, and H. Gonzalez, High-Dimensional 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
• High-D OLAP is needed in applications
• Science and engineering analysis
• Bio-data analysis: thousands of genes
• Statistical surveys: hundreds of variables

• Observation: OLAP occurs only on a small subset of dimensions at a time
• Semi-Online Computational Model
• Partition the set of dimensions into shell fragments
• Compute data cubes for each shell fragment while retaining inverted indices or value-list indices
• Given the pre-computed fragment cubes , dynamically compute cube cells of the high-dimensional data cube online

• Partitions the data vertically
• Reduces high-dimensional cube into a set of lower dimensional cubes
• Online re-construction of original high-dimensional space
• Lossless reduction
• Offers tradeoffs between the amount of pre-processing and the speed of online computation

• Generalize the 1-D inverted indices to multi-dimensional 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

• 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 sub-linear
• 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 

• If measures other than count are present, store in ID_measure table separate from the shell fragments  

• 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
• For each fragment partition Pi
  • build local fragment cube Si by intersecting tid-lists in bottom- up fashion.

• 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 2-D data cube.

• 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

• UCI Forest CoverType data set
• 54 dimensions, 581K tuples
• Shell fragments of size 2 took 33 seconds and 325MB to compute
• 3-D 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
• 5-D query with 0 instantiated D: 227ms~2.6 sec.

• 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 top-k queries with multi-dimensional 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 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?

• 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

• Confidence interval at x':
  
  
  
  \[ \bar{x}\pm t_{c}\hat{\sigma}_{\bar{x}} \]
  
• x is a sample of data set;x' is the mean of sample
  tc is the critical t-value, calculated by a look-up  
  
  
  
  \[ \hat{\sigma}_{\bar{x}}=\frac{s}{\sqrt{l}} \]
  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 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

• From the example: The queried cell “19-year-old 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

Intra-Cuboid 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?
• Two-sample t-test (confidence-based)

• 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 two-sample t-test to determine similarity between two cells across cuboids
• Can also use a different method to be shown later

• 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
• (top-k) ranking query: only returns the best k results according to a user-specified 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: Methodology and Extension

• Ranking cube methodology
• Push selection and ranking simultaneously
• It works for many sophisticated ranking functions
• How to support high-dimensional data?
• Materialize only those atomic cuboids that contain single selection dimensions
• Uses the idea similar to high-dimensional 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 OLAP-styled 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., multi-feature cube
• Using data-mining models as building blocks in a multi-step mining process, e.g., prediction cube
• Using data-cube computation techniques to speed up repeated model construction
• Cube-space data mining may require building a model for each candidate data space
• Sharing computation across model-construction 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 class-label 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

• 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

• Multi-feature 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

• Hypothesis-driven
• exploration by user, huge search space
• Discovery-driven (Sarawagi, et al.’98)
• Effective navigation of large OLAP data cubes
• pre-compute 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

• 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 drill-down 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