Mining <Emphasis Type="Italic">top-k</Emphasis> frequent patterns in the presence of the memory constraint |
| |
Authors: | Kun-Ta Chuang Jiun-Long Huang Ming-Syan Chen |
| |
Affiliation: | (1) Department of Electrical Engineering, National Taiwan University, Taipei, Taiwan, ROC;(2) Department of Computer Science, National Chiao Tung University, Hsinchu, Taiwan, ROC |
| |
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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|