Mining Multi-Dimensional Constrained Gradients in Data Cubes
Find in a Library
Constrained gradient analysis (similar to the “cubegrade” problem posed by Imielinski, et al. ) is to extract pairs of similar cell characteristics associated with big changes in measure in a data cube. Cells are considered similar if they are related by roll-up, drill-down, or 1-dimensional mutation operation. Constrained gradient queries are expressive, capable of capturing trends in data and answering “what-if” questions.
To facilitate our discussion, we call one cell in a gradient pair probe cell and the other gradient cell. An efficient algorithm is developed, which pushes constraints deep into the computation process, finding all gradient-probe cell pairs in one pass. It explores bi-directional pruning between probe cells and gradient cells, utilizing transformed measures and dimensions. Moreover, it adopts a hyper-tree structure and an H-cubing method to compress data and maximize sharing of computation. Our performance study shows that this algorithm is efficient and scalable.
& Wang, K.
(2001). Mining Multi-Dimensional Constrained Gradients in Data Cubes. Proceedings of the Twenty-Seventh International Conference on Very Large Databases, 321-330.