Mining constrained gradients in large databases

Guozhu Dong, Jiawei Han, Joyce M.W. Lam, Jian Pei, Ke Wang, Wei Zou

Research output: Contribution to journalArticlepeer-review

Abstract

Many data analysis tasks can be viewed as search or mining in a multidimensional space (MDS). In such MDSs, dimensions capture potentially important factors for given applications, and cells represent combinations of values for the factors. To systematically analyze data in MDS, an interesting notion, called "cubegrade" was recently introduced by lmielinski et al. which focuses on the notable changes in measures in MDS by comparing a cell (which we refer to as probe cell) with its gradient cells, namely, its ancestors, descendants, and siblings. We call such queries gradient analysis queries (GQs). Since an MDS can contain billions of cells, it is important to answer GQs efficiently. In this study, we focus on developing efficient methods for mining GQs constrained by certain (weakly) antimonotone constraints. Instead of conducting an independent gradient-cell search once per probe cell, which is inefficient due to much repeated work, we propose an efficient algorithm, LiveSet-Driven. This algorithm finds all good gradient-probe cell pairs in one search pass. It utilizes measure-value analysis and dimension-match analysis in a set-oriented manner, to achieve bidirectional pruning between the sets of hopeful probe cells and of hopeful gradient cells. Moreover, it adopts a hypertree structure and an H-cubing method to compress data and to maximize sharing of computation. Our performance study shows that this algorithm is efficient and scalable. In addition to data cubes, we extend our study to another important scenario: mining constrained gradients in transactional databases where each item is associated with some measures such as price. Such transactional databases can be viewed as sparse MDSs where items represent dimensions, although they have significantly different characteristics than data cubes. We outline efficient mining methods for this problem in this paper.

Original languageEnglish (US)
Pages (from-to)922-938
Number of pages17
JournalIEEE Transactions on Knowledge and Data Engineering
Volume16
Issue number8
DOIs
StatePublished - Aug 2004

Keywords

  • Antimonotonicity
  • Complex measures
  • Constraint-based pruning
  • Data cube
  • Data mining
  • Dimension-based pruning
  • Gradient analysis
  • Iceberg query

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Mining constrained gradients in large databases'. Together they form a unique fingerprint.

Cite this