Maintenance algorithm for high average-utility itemsets with transaction deletion

Jerry Chun Wei Lin*, Yina Shao, Philippe Fournier-Viger, Youcef Djenouri, Xiangmin Guo

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review


High-utility itemset mining (HUIM) is an extension of traditional association-rule mining that can find profitable itemsets for decision-making. It faces, however, a limitation since the utility of an itemset increases along with the size of it. High-average utility itemset mining (HAUIM) provides a fair measure to find the average-utility of an itemset, which is more reasonable to design the sales strategies for making the efficient decision. Traditional algorithms of HAUIM mostly focus on mining high average-utility itemsets (HAUIs) from the static database. When the database size is changed, for example, transaction insertion/deletion, the discovered information is required to be updated, thus the updated database is necessary to be re-scanned for identifying the set of HAUIs in the batch manner. In this paper, we present an updating algorithm called FUP-HAUIMD to maintain the discovered HAUIs with transaction deletion. When some transactions in the database are deleted, the designed FUP-HAUIMD algorithm can easily update the discovered HAUIs without scanning the database all the time. The designed FUP-HAUIMD algorithm divides the itemsets into four cases based on the modified fast updated (MFUP) concept. The average-utility (AU)-list structure is further utilized to keep the necessary ramification for later mining progress. Experiments are then conducted to compare the designed FUP-HAUIMD algorithm with the state-of-the-art baseline algorithm running on the batch mode, and the developed approach shows better performance in terms of runtime, number of examined patterns, and scalability.

Original languageEnglish
JournalApplied Intelligence
Issue number10
Pages (from-to)3691-3706
Publication statusPublished - 2018



  • Dynamic database
  • High average-utility mining
  • MFUP
  • Transaction deletion

Cite this

Lin, J. C. W., Shao, Y., Fournier-Viger, P., Djenouri, Y., & Guo, X. (2018). Maintenance algorithm for high average-utility itemsets with transaction deletion. Applied Intelligence, 48(10), 3691-3706.