Mining top-k frequent patterns in the presence of the memory constraint

Kun Ta Chuang*, Jiun-Long Huang, Ming Syan Chen

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

50 Scopus citations

Abstract

We explore in this paper a practicably interesting mining task to retrieve top-k (closed) itemsets in the presence of the memory constraint. Specifically, as opposed to most previous works that concentrate on improving the mining efficiency or on reducing the memory size by best effort, we first attempt to specify the available upper memory size that can be utilized by mining frequent itemsets. To comply with the upper bound of the memory consumption, two efficient algorithms, called MTK and MTK_Close, are devised for mining frequent itemsets and closed itemsets, respectively, without specifying the subtle minimum support. Instead, users only need to give a more human-understandable parameter, namely the desired number of frequent (closed) itemsets k. In practice, it is quite challenging to constrain the memory consumption while also efficiently retrieving top-k itemsets. To effectively achieve this, MTK and MTK_Close are devised as level-wise search algorithms, where the number of candidates being generated-and-tested in each database scan will be limited. A novel search approach, called δ-stair search, is utilized in MTK and MTK_Close to effectively assign the available memory for testing candidate itemsets with various itemset-lengths, which leads to a small number of required database scans. As demonstrated in the empirical study on real data and synthetic data, instead of only providing the flexibility of striking a compromise between the execution efficiency and the memory consumption, MTK and MTK_Close can both achieve high efficiency and have a constrained memory bound, showing the prominent advantage to be practical algorithms of mining frequent patterns.

Original languageEnglish
Pages (from-to)1321-1344
Number of pages24
JournalVLDB Journal
Volume17
Issue number5
DOIs
StatePublished - 1 Aug 2008

Fingerprint Dive into the research topics of 'Mining top-k frequent patterns in the presence of the memory constraint'. Together they form a unique fingerprint.

Cite this