Mining multi-relational high utility itemsets from star schemas

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.