Affiliations: [a] School of Computer Science and Technology, North China University of Technology, Beijing 100144, China | [b] Beijing Key Laboratory on Integration and Analysis of Large-scale Stream Data, Beijing 100144, China
Correspondence:
[*]
Corresponding author: Wei Song, School of Computer Science and Technology, North China University of Technology, Beijing 100144, China. Tel.: +86 10 88802798; Fax: +86 10 88802798; E-mail: [email protected].
Abstract: Mining high utility itemsets is an interesting research problem in data mining and knowledge discovery. Most high utility itemset discovery algorithms seek patterns in a single table, but few are dedicated to processing data stored using a multi-dimensional model. In this paper, the problem of mining high utility itemsets in multi-relational databases is investigated, and two algorithms, RHUI-Mine and RHUI-Growth, are proposed for star schema-based data warehouses. In the RHUI-Mine algorithm, the search space is traversed in a level-wise manner, and an item index and transaction index are proposed to represent item and transaction information, respectively. The RHUI-Growth algorithm traverses the search space recursively using a pattern growth approach, and a dimensional tree and relational tree are used to compress the original data. Neither algorithm materializes the join operation between tables, thus making use of the star schema properties. Experiments show that both RHUI-Mine and RHUI-Growth are effective approaches for mining high utility itemsets in multi-relational data.
Keywords: Multi-relational high utility itemsets, star schema, item index, transaction index, dimensional tree, relational tree
