The effective skyline quantify-utility patterns mining algorithm with pruning strategies

Jimmy Ming-Tai Wu ; Ranran Li ; Pi-Chung Hsu ; Mu-En Wu 4

Computer Science and Information Systems, Tome 20 (2023) no. 3.

Résumé

Frequent itemset mining and high-utility itemset mining have been widely applied to the extraction of useful information from databases. However, with the proliferation of the Internet of Things, smart devices are generating vast amounts of data daily, and studies focusing on individual dimensions are increasingly unable to support decision-making. Hence, the concept of a skyline query considering frequency and utility (which returns a set of points that are not dominated by other points) was introduced. However, in most cases, firms are concerned about not only the frequency of purchases but also quantities. The skyline quantity-utility pattern (SQUP) considers both the quantity and utility of items. This paper proposes two algorithms, FSKYQUP-Miner and FSKYQUP, to efficiently mine SQUPs. The algorithms are based on the utility-quantity list structure and include an effective pruning strategy which calculates the minimum utility of SQUPs after one scan of the database and prunes undesired items in advance, which greatly reduces the number of concatenation operations. Furthermore, this paper proposes an array structure superior to utilmax for storing the maximum utility of quantities, which further improves the efficiency of pruning. Extensive comparison experiments on different datasets show that the proposed algorithms find all SQUPs accurately and efficiently.

Détail

Keywords: Internet of Things, skyline quantity-utility patterns (SQUPs), utility-quantity list, minimum utility of SQUPs (MUSQ), quantity maximum utility of the array (QMUA)