A distributed frequent itemset mining algorithm using Spark for Big Data analytics
Cluster ComputingPublished 28 October 2015
Feng Zhang, Min Liu, Feng Gui, Weiming Shen, Abdallah Shami, Yunlong Ma
Citations85
SJR quartileQ1
SJR score1.04
SNIP1.59
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
An efficient distributed frequent itemset mining algorithm (DFIMA) which can significantly reduce the amount of candidate itemsets by applying a matrix-based pruning approach is proposed.
Abstract
Frequent itemset mining is an essential step in the process of association rule mining. Conventional approaches for mining frequent itemsets in big data era encounter significant challenges when computing power and memory space are limited. This paper proposes an efficient distributed frequent itemset mining algorithm (DFIMA) which can significantly reduce the amount of candidate itemsets by applying a matrix-based pruning approach. The proposed algorithm has been implemented using Spark to further improve the efficiency of iterative computation. Numeric experiment results using standard benchmark datasets by comparing the proposed algorithm with the existing algorithm, parallel FP-growth, show that DFIMA has better efficiency and scalability. In addition, a case study has been carried out to validate the feasibility of DFIMA.
Keywords
Computer Science
Communications of the ACMMapReduce
18,538 Citations2008Jay B. Dean, Sanjay Ghemawat
This presentation explains how the underlying runtime system automatically parallelizes the computation across large-scale clusters of machines, handles machine failures, and schedules inter-machine communication to make efficient use of the network and disks.
Fast algorithms for mining association rules
10,739 Citations1998Rakesh Agrawal, Ramakrishnan Srikant
Spark: cluster computing with working sets
4,236 Citations2010Matei Zaharia, Mosharaf Chowdhury +3 more
Spark can outperform Hadoop by 10x in iterative machine learning jobs, and can be used to interactively query a 39 GB dataset with sub-second response time.
Resilient distributed datasets: a fault-tolerant abstraction for in-memory cluster computing
3,577 Citations2012Matei Zaharia, Mosharaf Chowdhury +7 more
Resilient Distributed Datasets is presented, a distributed memory abstraction that lets programmers perform in-memory computations on large clusters in a fault-tolerant manner and is implemented in a system called Spark, which is evaluated through a variety of user applications and benchmarks.
IEEE Transactions on Knowledge and Data EngineeringParallel mining of association rules
1,069 Citations1996R. K. Agrawal, J.C. Shafer
This work considers the problem of mining association rules on a shared nothing multiprocessor and presents three algorithms that explore a spectrum of trade-offs between computation, communication, memory usage, synchronization, and the use of problem specific information.
IEEE Transactions on Knowledge and Data EngineeringTopic-sensitive pagerank: A context-sensitive ranking algorithm for web search
1,065 Citations2003Taher H. Haveliwala
It is shown that using linear combinations of these (precomputed) biased PageRank vectors to generate context-specific importance scores for pages at query time, can generate more accurate rankings than with a single, generic PageRank vector.
Lecture notes in computer scienceAn Apriori-Based Algorithm for Mining Frequent Substructures from Graph Data
1,029 Citations2000Akihiro Inokuchi, Takashi Washio +1 more
A novel approach named AGM to efficiently mine the association rules among the frequently appearing substructures in a given graph data set through the extended algorithm of the basket analysis is proposed.
CLOSET : An Efficient Algorithm for Mining Frequent Closed Itemsets
829 Citations2000Jian Pei
IEEE Transactions on Knowledge and Data EngineeringFast algorithms for frequent itemset mining using FP-trees
552 Citations2005Gösta Grahne, Jun Zhu
A novel FP-array technique is presented that greatly reduces the need to traverse FP-trees, thus obtaining significantly improved performance for FP-tree-based algorithms and works especially well for sparse data sets.
Pfp
439 Citations2008Haoyuan Li, Yi Wang +3 more
Through empirical study on a large dataset of 802,939 Web pages and 1,021,107 tags, it is demonstrated that PFP can achieve virtually linear speedup and to be promising for supporting query recommendation for search engines.
Shark
373 Citations2013Reynold Xin, Josh Rosen +4 more
Shark is a new data analysis system that marries query processing with complex analytics on large clusters and extends such an engine in several ways, including column-oriented in-memory storage and dynamic mid-query replanning, to effectively execute SQL.
Insecta mundiScalable Distributed Communication\nArchitectures to Support Advanced\nMetering Infrastructure in Smart Grid
254 Citations2012Jiazhen Zhou, Rose Qingyang Hu +1 more
ACM SIGKDD Explorations NewsletterAdvances in frequent itemset mining implementations
237 Citations2004Bart Goethals, Mohammed J. Zaki
Given the experimental, algorithmic nature of FIM (and most of data mining in general), it is crucial that other researchers be able to independently verify the claims made in a new paper, and the FIM community has a very poor track record in this regard.
Apriori-based frequent itemset mining algorithms on MapReduce
231 Citations2012Ming-Yen Lin, Pei‐Yu Lee +1 more
DPC features in dynamically combining candidates of various lengths and outperforms both the straight-forward algorithm SPC and the fixed passes combined counting algorithm FPC, and shows that all the three algorithms scale up linearly with respect to dataset sizes and cluster sizes.
Frequent Itemset Mining for Big Data
213 Citations2013Sandy Moens, Emin Aksehirli +1 more
Two new methods for mining large datasets: Dist-Eclat focuses on speed while BigFIM is optimized to run on really large datasets, and the scalability of these methods is shown.
A Parallel Apriori Algorithm for Frequent Itemsets Mining
119 Citations2006Yanbin Ye, Chia-Chu Chiang
This paper revised Bodon's implementation of the Apriori algorithm into a parallel one where input transactions are read by a parallel computer and the results appear to be faster than the ones by Borgelt and Goethals.
IEEE Transactions on Parallel and Distributed SystemsA Novel Algorithm for Mining Association Rules in Wireless Ad Hoc Sensor Networks
85 Citations2008Azzedine Boukerche, Samer Samarah
A novel representation structure that is able to compress the data gathered for the mining process and thus allows the fast and efficient mining of sensor behavioral patterns, and a distributed data extraction mechanism to prepare the data required for mining sensor Behavioral patterns are proposed.
Cluster ComputingScaling up MapReduce-based Big Data Processing on Multi-GPU systems
83 Citations2014Hai Jiang, Yi Chen +3 more
This paper proposes an upgrade version MGMR++ to eliminate GPU memory limitation and a pipelined version, PMGMR, to handle the Big Data challenge through both CPU memory and hard disks and achieves about 2.5-fold performance improvement.
Journal of Parallel and Distributed ComputingParallel approaches to machine learning—A comprehensive survey
78 Citations2012Sujatha R Upadhyaya
Map reduce is another important technique that has evolved during this period and as the literature has it, it has been proved to be an important aid in delivering performance of machine learning algorithms on GPUs.
Cluster ComputingMining association rules in big data with NGEP
55 Citations2015Yunliang Chen, Fangyuan Li +1 more
Experimental results indicate that NGEP can efficiently achieve more association rules with a higher accuracy rate than the FP-Growth and Apriori algorithms and the time of computing is also much less than the other two methods.
Cluster ComputingScheduling of big data applications on distributed cloud based on QoS parameters
53 Citations2014Rajinder Sandhu, Sandeep K. Sood
A global architecture is proposed for QoS based scheduling for big data application to distributed cloud datacenter at two levels which are coarse grained and fine grained, and results indicated better QoS achievement and 33.15 % cost gain of the proposed architecture over traditional Amazon methods.
ETree: Effective and Efficient Event Modeling for Real-Time Online Social Media Networks
51 Citations2011Hansu Gu, Xing Xie +3 more
ETree, an effective and efficient event modeling solution for social media network sites, is proposed and detailed evaluation using 3.5 million tweets over a 5-month period demonstrates that ETree can efficiently generate high-quality event structures and identify inherent causal relationships with high accuracy.
Lecture notes in computer scienceParallel FP-Growth on PC Cluster
51 Citations2003Iko Pramudiono, Masaru Kitsuregawa
The bottlenecks of the parallelization and method to balance the execution efficiently on shared-nothing environment of FP-growth are examined.
Efficient mining of frequent itemsets in social network data based on MapReduce framework
47 Citations2013Zahra Farzanyar, Nick Cercone
This paper proposes an efficient frequent itemset mining algorithm, called IMRApriori, based on MapReduce framework which deals with Hadoop cloud, a parallel store and computing platform, and demonstrates experimental results to corroborate the theoretical claims.
Mining frequent itemsets in distributed and dynamic databases
38 Citations2004Matthew Eric Otey, C. Wang +3 more
This work presents what it believes to be the first unified approach that overcomes traditional methods for frequent itemset mining and makes use of parallel and incremental techniques to generate frequent itemsets in the presence of data updates without examining the entire database.
Knowledge and Information SystemsPerformance study of distributed Apriori-like frequent itemsets mining
33 Citations2009Lamine M. Aouad, Nhien‐An Le‐Khac +1 more
A new distributed approach which takes into account inherent characteristics of this algorithm and achieves good scalability compared to a typical distributed Apriori founded algorithm is presented.
Lecture notes in computer scienceLoad Balancing Approach Parallel Algorithm for Frequent Pattern Mining
32 Citations2007Kun-Ming Yu, Jiayi Zhou +1 more
A parallel and distributed mining algorithm based on FP-tree structure, Load Balancing FP-Tree (LFP-tree).
Expert Systems with ApplicationsA load-balanced distributed parallel mining algorithm
32 Citations2009Kun-Ming Yu, Jiayi Zhou +4 more
The Distributed Parallel Apriori (DPA) algorithm is proposed as a solution to the problem of quickly and correctly finding the relationship among data, which takes the factor of itemset counts into consideration, thus generating a balanced workload among processors and reducing processor idle time.
An improved Apriori algorithm based on pruning optimization and transaction reduction
32 Citations2011Zhuang Chen, Shibang Cai +2 more
By using the improved Apriori algorithm, the number of frequent item sets is much less and the running time is significantly shortened as well as the performance is enhanced then finally the algorithm is improved.
IEEE Transactions on Parallel and Distributed SystemsParallel Frequent Item Set Mining with Selective Item Replication
30 Citations2011Eray Özkural, Bora Uçar +1 more
A transaction database distribution scheme that divides the frequent item set mining task in a top-down fashion and is used in the design of two new parallel frequentitem set mining algorithms that replicate the items that correspond to the separator.
Cluster ComputingImproved MPI collectives for MPI processes in shared address spaces
30 Citations2014Shigang Li, Torsten Hoefler +2 more
This paper investigates the design and optimization of MPI collectives for clusters of NUMA nodes, develops performance models for collective communication using shared memory, and demonstrates several algorithms for various collectives.
An efficient parallel FP-Growth algorithm
24 Citations2009Min Chen, Xuedong Gao +1 more
This work proposes a novel parallel FP-Growth algorithm, which is designed to run on the computer cluster, and finds all the conditional pattern bases of frequent items by the projection method without constructing an FP-tree.
Fusing Text and Frienships for Location Inference in Online Social Networks
22 Citations2012Hansu Gu, Haojie Hang +2 more
Knowledge and Information SystemsBatch incremental processing for FP-tree construction using FP-Growth algorithm
22 Citations2012Shashikumar G. Totad, R. B. Geeta +1 more
A batch incremental processing algorithm BIT_FPGrowth is proposed that restructures and merges two small consecutive duration FP-trees to obtain a FP-tree of the FP-Growth algorithm, which uses FP- tree as preprocessed data repository to get transactions, unlike other sequential incremental algorithms that read transactions from database.
Cluster ComputingParallel data intensive applications using MapReduce: a data mining case study in biomedical sciences
21 Citations2014Liangxiu Han, Hwee Yong Ong
This paper explores how MapReduce and Cloud computing can accelerate performance of data intensive applications through a real data mining use case in the Biomedical Sciences and builds an analytic model based on the MapRed reduce computations to evaluate the efficiency and performance of the prototype.
2012 IEEE/WIC/ACM International Conferences on Web Intelligence and Intelligent Agent TechnologyFusing Text and Frienships for Location Inference in Online Social Networks
18 Citations2012Hansu Gu, Haojie Hang +2 more
GeoFind is proposed, which accurately identifies users' geographic regions through effective fusion (re-ranking) of (1) text-based ranking using geo-sensitive textual features and (2) structure- based ranking using maximum likelihood estimation (MLE) of geotagged friends.
Cluster ComputingPEBIL: binary instrumentation for practical data-intensive program analysis
15 Citations2013Michael A. Laurenzano, Joshua Peraza +4 more
This work details two novel mechanisms in the PEBIL binary instrumentation platform that make it well-suited for analyzing data-intensive programs by providing support for fast lookup of instrumentation thread-local storage (ITLS) and support for the fast enabling and disabling ofstrumentation at runtime as a methodology for supporting sampling.
Journal of SoftwareResearch of the FP-Growth Algorithm Based on Cloud Environments
15 Citations2014Lijuan Zhou, Xiang Wang
A parallel linked list-based FPG algorithm based on MapReduce programming model, named as the PLFPG algorithm, which has higher efficiency and better flexibility and scalability is proposed.
RMIT Research Repository (RMIT University Library)Distributed association rule mining with minimum communication overhead
13 Citations2009Mohammed Kaosar, Zhuojia Xu +1 more
Performance study shows that the proposed association rule mining algorithm performs better than two other well known algorithms known as Fast Distributed Algorithm for Mining Association Rules (FDM) and Count Distribution in terms of communication overhead.
International Journal of Machine Learning and CyberneticsEfficient mining frequent itemsets algorithms
12 Citations2013Marghny H. Mohamed, Mohammed M. Darwieesh
This method is developed to avoid the costly candidate-generation-and-test processing completely and to avoid expensive, and repeated database scans, and a comprehensive performance study shows that the techniques are efficient and scalable comparing with other methods.
A parallel algorithm for approximate frequent itemset mining using MapReduce
8 Citations2014Fabio Fumarola, Donato Malerba
The key principle underlying the design of MrAdam is that one can make reasonable decisions in the absence of perfect answers, and it is shown that the proposed algorithm returns a good statistically bounded approximation of the exact results.
Efficiently Using Matrix in Mining Maximum Frequent Itemset
6 Citations2010Zhenyu Liu, Weixiang Xu +1 more
A new MFI checking method is presented based on the optimizing of the former called MaxMatrix and an additional constraint for association rules generating is discussed to save mining time.