Towards efficiently mining closed high utility itemsets from incremental databases

Thu-Lan Dam

doi:10.1016/j.knosys.2018.11.019

Return

Towards efficiently mining closed high utility itemsets from incremental databases

2019-02-01

DOI：10.1016/j.knosys.2018.11.019

Original

Save

View PDF

Abstract

En 中文

The set of closed high-utility itemsets (CHUls) concisely represents the exact utility of all itemsets. Yet, it can be several orders of magnitude smaller than the set of all high-utility itemsets. Existing CHUI mining algorithms assume that databases are static, making them very expensive in the case of incremental data, since the whole dataset has to be processed for each batch of new transactions. To address this challenge, this paper presents the first approach, called IncCHUI, that mines CHUls efficiently from incremental databases. In order to achieve this, we propose an incremental utility-list structure, which is built and updated with only one database scan. Further, we apply effective pruning strategies to fast construct incremental utility-lists and eliminate candidates that are not updated. Finally, we suggest an efficient hash-based approach to update or insert new closed sets that are found. Our extensive experimental evaluation on both real-life and synthetic databases shows the efficiency, as well as the feasibility of our approach. It significantly outperforms previously proposed methods that are mainly run in batch mode in terms of speed, and it is scalable with respect to the number of transactions. (C) 2018 Elsevier B.V. All rights reserved.

Keywords:

High-utility itemset mining

Closed itemset mining

Incremental mining

Incremental utility list

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.