Open Access
ARTICLE
GTK: A Hybrid-Search Algorithm of Top-Rank-k Frequent Patterns Based on Greedy Strategy
Yuhang Long1, Wensheng Tang1, *, Bo Yang1, *, Xinyu Wang2, Hua Ma1, Hang Shi1, Xueyu Cheng3
1 Hunan Provincial Key Laboratory of Intelligent Computing and Language Information Processing, Hunan Normal University, Changsha, 410081, China.
2 College of Information Science and Engineering, Hunan University, Changsha, 410082, China.
3 Clayton State University, Morrow, GA 30260, USA.
*Corresponding Authors: Wensheng Tang. Email: ; Bo Yang. Email: .
Computers, Materials & Continua 2020, 63(3), 1445-1469. https://doi.org/10.32604/cmc.2020.09944
Received 30 January 2020; Accepted 26 February 2020; Issue published 30 April 2020
Abstract
Currently, the top-rank-
k has been widely applied to mine frequent patterns
with a rank not exceeding
k. In the existing algorithms, although a level-wise-search
could fully mine the target patterns, it usually leads to the delay of high rank patterns
generation, resulting in the slow growth of the support threshold and the mining
efficiency. Aiming at this problem, a greedy-strategy-based top-rank-
k frequent patterns
hybrid mining algorithm (GTK) is proposed in this paper. In this algorithm, top-rank-
k
patterns are stored in a static doubly linked list called RSL, and the patterns are divided
into short patterns and long patterns. The short patterns generated by a rank-first-search
always joins the two patterns of the highest rank in RSL that have not yet been joined. On
the basis of the short patterns satisfying specific conditions, the long patterns are
extracted through level-wise-search. To reduce redundancy, GTK improves the
generation method of subsume index and designs the new pruning strategies of
candidates. This algorithm also takes the use of reasonable pruning strategies to reduce
the amount of computation to improve the computational speed. Real datasets and
synthetic datasets are adopted in experiments to evaluate the proposed algorithm. The
experimental results show the obvious advantages in both time efficiency and space
efficiency of GTK.
Keywords
Cite This Article
Y. Long, W. Tang, B. Yang, X. Wang, H. Ma
et al., "Gtk: a hybrid-search algorithm of top-rank-
k frequent patterns based on greedy strategy,"
Computers, Materials & Continua, vol. 63, no.3, pp. 1445–1469, 2020.