Title: An efficient and optimised frequent pattern mining using novel multipath-graph structure

Authors: Suhasini A. Itkar; Uday V. Kulkarni

Addresses: Department of Computer Engineering, PES Modern College of Engineering, Pune, Maharashtra, India ' Department of Computer Science and Engineering, SGGS Institute of Engineering and Technology, Nanded, Maharashtra, India

Abstract: The frequent pattern mining is one of the most focused areas in the data mining domain. The frequent pattern growth (FP-growth) algorithm introduced compact prefix-based data structure, frequent pattern tree (FP-Tree), to store frequent itemsets in compressed format. The FP-growth attempts to overcome drawback of candidate generation approach of multiple database scan. This work aims to propose a novel optimised data structure multipath-Graph (MP-Graph) for improving memory utilisation and efficiency of mining algorithms. The MP-Graph is a compact graph structure to store frequent patterns in memory. It generates graph nodes equal to number of frequent 1-itemsets of transaction database. Further, it stores multiple occurrences of prefix subpaths along the edges of the graph in the form of transaction bitmap instead of storing frequency of individual item node. The proposed structure helps to mine frequent patterns without constructing conditional FP-Trees. The performance of the MP-Graph mining algorithm is compared with FP-growth, CT-PRO and IFP-growth. The experimental results show order of magnitude improvement in memory consumption to store frequent patterns, nodes generated and time complexity.

Keywords: data mining; frequent pattern mining; MP-Graph; association rules mining; frequent pattern tree; multipath graph; transaction bitmap.

DOI: 10.1504/IJDMMM.2017.082551

International Journal of Data Mining, Modelling and Management, 2017 Vol.9 No.1, pp.79 - 97

Accepted: 20 Aug 2015
Published online: 01 Mar 2017 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article