Power-law relationship and self-similarity in the itemset support distribution: Analysis and applications

Kun Ta Chuang, Jiun Long Huang, Ming Syan Chen

研究成果: Article同行評審

12 引文 斯高帕斯(Scopus)

摘要

In this paper, we identify and explore that the power-law relationship and the self-similar phenomenon appear in the itemset support distribution. The itemset support distribution refers to the distribution of the count of itemsets versus their supports. Exploring the characteristics of these natural phenomena is useful to many applications such as providing the direction of tuning the performance of the frequent-itemset mining. However, due to the explosive number of itemsets, it is prohibitively expensive to retrieve lots of itemsets before we identify the characteristics of the itemset support distribution in targeted data. As such, we also propose a valid and cost-effective algorithm, called algorithm PPL, to extract characteristics of the itemset support distribution. Furthermore, to fully explore the advantages of our discovery, we also propose novel mechanisms with the help of PPL to solve two important problems: (1) determining a subtle parameter for mining approximate frequent itemsets over data streams; and (2) determining the sufficient sample size for mining frequent patterns. As validated in our experimental results, PPL can efficiently and precisely identify the characteristics of the itemset support distribution in various real data. In addition, empirical studies also demonstrate that our mechanisms for those two challenging problems are in orders of magnitude better than previous works, showing the prominent advantage of PPL to be an important pre-processing means for mining applications.

原文English
頁(從 - 到)1121-1141
頁數21
期刊VLDB Journal
17
發行號5
DOIs
出版狀態Published - 2008 八月 1

All Science Journal Classification (ASJC) codes

  • 資訊系統
  • 硬體和架構

指紋

深入研究「Power-law relationship and self-similarity in the itemset support distribution: Analysis and applications」主題。共同形成了獨特的指紋。

引用此