Performance study of distributed Apriori-like frequent itemsets mining
Knowledge and Information SystemsPublished 15 April 2009Open access
Lamine M. Aouad, Nhien‐An Le‐Khac, Tahar Kechadi
Citations33
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
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.
Abstract
In this article, we focus on distributed Apriori-based frequent itemsets\nmining. We present a new distributed approach which takes into account inherent\ncharacteristics of this algorithm. We study the distribution aspect of this\nalgorithm and give a comparison of the proposed approach with a classical\nApriori-like distributed algorithm, using both analytical and experimental\nstudies. We find that under a wide range of conditions and datasets, the\nperformance of a distributed Apriori-like algorithm is not related to global\nstrategies of pruning since the performance of the local Apriori generation is\nusually characterized by relatively high success rates of candidate sets\nfrequency at low levels which switch to very low rates at some stage, and often\ndrops to zero. This means that the intermediate communication steps and remote\nsupport counts computation and collection in classical distributed schemes are\ncomputationally inefficient locally, and then constrains the global\nperformance. Our performance evaluation is done on a large cluster of\nworkstations using the Condor system and its workflow manager DAGMan. The\nresults show that the presented approach greatly enhances the performance and\nachieves good scalability compared to a typical distributed Apriori founded\nalgorithm.\n
Keywords
Computer Science
Fast algorithms for mining association rules
10,739 Citations1998Rakesh Agrawal, Ramakrishnan Srikant
ACM SIGMOD RecordMining frequent patterns without candidate generation
6,360 Citations2000Jiawei Han, Jian Pei +1 more
Mining frequent patterns without candidate generation
3,195 Citations2000Jiawei Han, Jian Pei +1 more
This study proposes a novel frequent pattern tree (FP-tree) structure, which is an extended prefix-tree structure for storing compressed, crucial information about frequent patterns, and develops an efficient FP-tree-based mining method, FP-growth, for mining the complete set of frequent patterns by pattern fragment growth.
Dynamic itemset counting and implication rules for market basket data
1,954 Citations1997Sergey Brin, Rajeev Motwani +2 more
A new algorithm for finding large itemsets which uses fewer passes over the data than classic algorithms, and yet uses fewer candidate itemsets than methods based on sampling and a new way of generating “implication rules” which are normalized based on both the antecedent and the consequent.
Concurrency and Computation Practice and ExperienceDistributed computing in practice: the Condor experience
1,896 Citations2005Douglas Thain, Todd Tannenbaum +1 more
The history and philosophy of the Condor project is provided and how it has interacted with other projects and evolved along with the field of distributed computing is described.
Future Generation Computer SystemsMining generalized association rules
1,617 Citations1997Ramakrishnan Srikant, Rakesh Agrawal
A new interest-measure for rules which uses the information in the taxonomy is presented, and given a user-specified “minimum-interest-level”, this measure prunes a large number of redundant rules.
An Efficient Algorithm for Mining Association Rules in Large Databases
1,598 Citations1995Ashoka Savasere, Edward Omiecinski +1 more
This paper presents an efficient algorithm for mining association rules that is fundamentally different from known algorithms and not only reduces the I/O overhead significantly but also has lower CPU overhead for most cases.
An effective hash-based algorithm for mining association rules
1,412 Citations1995Jong Soo Park, Ming-Syan Chen⋆ +1 more
The number of candidate 2-itemsets generated by the proposed algorithm is, in orders of magnitude, smaller than that by previous methods, thus resolving the performance bottleneck, and allows us to effectively trim the transaction database size at a much earlier stage of the iterations, thereby reducing the computational cost for later iterations significantly.
Sampling Large Databases for Association Rules
1,079 Citations1996Hannu Toivonen
New algorithms that reduce the database activity considerably by picking a Random sample, to find using this sample all association rules that probably hold in the whole database, and then to verify the results with the rest of the database.
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.
ACM SIGMOD RecordDynamic itemset counting and implication rules for market basket data
611 Citations1997Sergey Brin, Rajeev Motwani +2 more
ACM SIGMOD RecordAn effective hash-based algorithm for mining association rules
487 Citations1995Jong Soo Park, Ming-Syan Chen⋆ +1 more
IEEE ConcurrencyParallel and distributed association mining: a survey
476 Citations1999Mohammed J. Zaki
The author surveys the state of the art in parallel and distributed association-rule-mining algorithms and uncovers the field's challenges and open research problems.
A fast distributed algorithm for mining association rules
439 Citations2002David W. Cheung, Jiawei Han +3 more
An interesting distributed association rule mining algorithm, FDM (fast distributed mining of association rules), which generates a small number of candidate sets and substantially reduces the number of messages to be passed at mining association rules is proposed.
Concurrency and Computation Practice and ExperienceA Java commodity grid kit
354 Citations2001Gregor von Laszewski, Ian Foster +2 more
Developing advanced applications for the emerging national‐scale ‘Computational Grid’ infrastructures is still a difficult task because these services may not be compatible with the commodity distributed‐computing technologies and frameworks used previously.
IEEE Transactions on Knowledge and Data EngineeringEfficient mining of association rules in distributed databases
345 Citations1996David W. Cheung, Vincent Ng +2 more
An efficient algorithm called DMA (Distributed Mining of Association rules), which generates a small number of candidate sets and requires only O(n) messages for support-count exchange for each candidate set, in distributed databases.
GridAnt: a client-controllable grid workflow system
204 Citations2004Kaizar Amin, Gregor von Laszewski +4 more
This paper discusses the design principles, functionality, and application of the proposed GridAnt workflow manager, an extensible client-side workflow management system, called GridAnt, developed.
Concurrency and Computation Practice and ExperienceASKALON: a tool set for cluster and Grid computing
187 Citations2005Thomas Fahringer, Alexandru Jugravu +4 more
The overall architecture of the ASKALON tool set is described and the basic functionality of the four constituent tools are outlined, enabling tool interoperability and demonstrating the usefulness and effectiveness of ASKalON by applying the tools to real‐world applications.
Grid'5000: a large scale, reconfigurable, controlable and monitorable Grid platform
154 Citations2005Franck Cappello, Frédéric Desprez +11 more
Macrocycle 2 has been shown to serve as an effective bis-metal-coordinating ligand and exhibits attractive optical properties such as a sharp Soret-like band at 566 nm and low-energy fluorescence at 1058 nm.
Knowledge and Information SystemsParallel Data Mining for Association Rules on Shared-Memory Systems
141 Citations2001Srinivasan Parthasarathy, Mohammed J. Zaki +2 more
A new parallel algorithm for data mining of association rules on shared-memory multiprocessors is presented, the degree of parallelism, synchronization, and data locality issues are studied, and proposed optimizations for fast frequency computation are presented.
IEEE Transactions on Systems Man and Cybernetics Part B (Cybernetics)Distributed Data Mining on Grids: Services, Tools, and Applications
140 Citations2004Mario Cannataro, Antonio Congiusta +3 more
The paper discusses how to design and implement data mining applications by using the KNOWLEDGE GRID tools starting from searching grid resources, composing software and data components, and executing the resulting data mining process on a grid.
Parallel data mining for association rules on shared-memory multi-processors
130 Citations1996Mohammed J. Zaki, Mitsunori Ogihara +2 more
This paper presents parallel algorithms for data mining of association rules, and studies the degree of parallelism, synchronization, and data locality issues on the SGI Power Challenge shared-memory multi-processor.
IEEE Distributed Systems OnlineODAM: an optimized distributed association rule mining algorithm
101 Citations2004Mafruz Zaman Ashrafi, David Taniar +1 more
This work has developed a distributed algorithm, called optimized distributed association mining, for geographically distributed data sets, called ODAM, which generates support counts of candidate itemsets quicker than the other DARM algorithms and reduces the size of average transactions, data set, and message exchanges.
IEEE Transactions on Systems Man and Cybernetics Part B (Cybernetics)Association Rule Mining in Peer-to-Peer Systems
93 Citations2004Ran Wolff, Assaf Schuster
Communications of the ACMViewpoint: From TeraGrid to knowledge grid
92 Citations2001Fran Berman
The first decade of the new millennium is the " Data Decade", where data growth is outpacing computational growth, and many of the most important advances in science and engineering will result from the tight coupling of computation and online analysis and synthesis of massive data collections.
Discovery net
80 Citations2002Vasa Ćurčin, Moustafa Ghanem +5 more
This paper shows how this architecture will behave during a typical KDD process design and deployment, how it enables the execution of complex and distributed data mining tasks with high performance and how it provides a community of e- scientists with means to collaborate, retrieve and reuse both KDD algorithms, discovery processes and knowledge in a visual analytical environment.
Knowledge and Information SystemsA high-performance distributed algorithm for mining association rules
72 Citations2004Assaf Schuster, Ran Wolff +1 more
A new distributed association rule mining (D-ARM) algorithm that demonstrates superlinear speed-up with the number of computing nodes and is the first D-ARM algorithm to perform a single scan over the database.
Lecture notes in computer scienceParallel and Distributed Data Mining: An Introduction
63 Citations2000Mohammed J. Zaki
This chapter presents a survey on large-scale parallel and distributed data mining algorithms and systems, serving as an introduction to the rest of this volume.
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.
Fast distributed algorithm for mining association rules
42 Citations1996David W. Cheung, Jiawei Han +3 more
SIAM Journal on ComputingAverage-Case Performance of the Apriori Algorithm
40 Citations2004Paul W. Purdom, Dirk Van Gucht +1 more
It is found that under a wide range of conditions the performance of the Apriori Algorithm is almost as bad as is permitted under sophisticated worst-case analyses.
Association rule mining in peer-to-peer systems
35 Citations2004Ran Wolff, Assaf Schuster
This work presents an algorithm by which every node in the system can reach the exact solution, as if it were given the combined database, and is entirely asynchronous, imposes very little communication overhead, transparently tolerates network topology changes and node failures, and quickly adjusts to changes in the data as they occur.
ACM Transactions on Database SystemsTight upper bounds on the number of candidate patterns
30 Citations2005Floris Geerts, Bart Goethals +1 more
Knowledge and Information SystemsA scalable algorithm for mining maximal frequent sequences using a sample
30 Citations2007Congnan Luo, Soon M. Chung
A high-performance distributed algorithm for mining association rules
28 Citations2004Assaf Schuster, Ran Wolff +1 more
A Peer to Peer Computing Framework: Design and Performance Evaluation of YML
28 Citations2005Olivier Delannoy, S. Petiton
The YML Framework is presented which provides supporting tools to design and execute portable parallel applications over large scale peer to peer and grid middlewares and defines a new parallel programming language called YvetteML which is composed of a graph language and a component model.
Data Mining and Knowledge DiscoveryCommunication-Efficient Distributed Mining of Association Rules
26 Citations2004Assaf Schuster, Ran Wolff
This paper presents a set of new algorithms that solve the Distributed Association Rule Mining problem using far less communication and are also extremely robust.
ADMIRE FRAMEWORK: DISTRIBUTED DATA MINING ON DATA GRID PLATFORMS
24 Citations2006Nhien‐An Le‐Khac, Tahar Kechadi +1 more
International Conference on Software and Data Technologies (ICSOFT 2006), Setubal, Portugal, 11-14 September 2006.
Knowledge and Information SystemsEfficient mining of maximal frequent itemsets from databases on a cluster of workstations
21 Citations2007Soon M. Chung, Congnan Luo
Both DMM and PMM demonstrate very good performance and scalability even when there are large maximal frequent itemsets in databases, and their performance was evaluated for various cases.
Parallel and distributed computing and networksGrid knowledge discovery processes and an architecture for their composition.
19 Citations2004Guenter Kickinger, Jürgen Hofer +2 more
EPO+Fe administration is associated and perhaps stimulates the appearance of grade 1 ROP, and lower birth weight and gestational age, more neonatal morbidity and a more aggressive treatment is associated.
Journal of Algorithms & Computational TechnologyGrid-Based Approaches for Distributed Data Mining Applications
18 Citations2009Lamine M. Aouad, Nhien‐An Le‐Khac +1 more
This paper presents grid-based approaches for two basic data mining applications, and a performance evaluation on an experimental grid environment that provides interesting monitoring capabilities and configuration tools and proposes a new distributed clustering approach and a distributed frequent itemsets generation well-adapted for grid environments.
Knowledge Map: Toward a New Approach Supporting the Knowledge Management in Distributed Data Mining
18 Citations2007Nhien-An Le-Khac, Lamine M. Aouad +1 more
This knowledge map is used to facilitate not only the visualization, evaluation of mining results but also the coordinating of local mining process and existing knowledge to increase the accuracy of final model.
Data mining "to go"
10 Citations2001Hillol Kargupta, Anupam Joshi
Distributed mining of maximal frequent itemsets from databases on a cluster of workstations
3 Citations2004Soon M. Chung, Congnan Luo
The proposed Distributed Max-Miner demonstrates better performance than other sequential and parallel algorithms, and its performance is quite scalable, even when there are large maximal frequent itemsets in databases.