Jong Soo, Ming-syan Chen, Philip S. Yu · 1995
In this paper, we develop an algorithm, called PDM, to conduct parallel data mining for association rules. Consider a transaction as a collection of items, and a large itemset is a set of items such that the number of transactions containing it exceeds a pre-specified threshold. PDM is so designed that the global set of large itemsets can be identified efficiently and the amount of inter-node data exchange required is minimized. Specifically, with a given database partition, each processing node will collect (count) information on each itemset from its local database efficiently via a hashing method. The information discovered by each node is next shared with other nodes via some communication schemes. Then, PDM employs a technique, called clue-andpoll, to address the uncertainty due to the partial knowledge collected at each node by judiciously selecting a small fraction of the itemsets for the exchange of count information among nodes, thus reducing the communication cost. The global...
Cited by 0
Moez Ben HajHmida, Antonio Congiusta · IGI Global eBooks · 2012
Knowledge discovery has become a necessary task in scientific, life sciences, and business fields, both for the growing amount of data being collected and for the complexity of the analysis that need to be performed on it. Classic data mining techniques, developed for centralized sites, often reveal themselves inadequate, due to some unique characteristics of today’s data sources. In such cases, sequential approaches to data mining cannot provide for scalability, in terms of the data dimensionality, size, and runtime performance. Moreover, the increasing trend towards decentralized business organizations, distribution of users, software, and hardware systems magnifies the need for more advanced and flexible approaches and solutions. Life science is one of the application areas that best resemble such scenario. This chapter presents the state of the art about the major data mining techniques, systems and approaches. A detailed taxonomy is drawn by analyzing and comparing parallel, distributed and Grid-based data mining methods, with a particular focus on the exploitation of large and remotely dispersed datasets and/or high-performance computers.
Cited by 8
Ivan Kholod, Mikhail Kuprianov, Ilya Petukhov · Lecture notes in computer science · 2016
Cited by 3
Eui-Hong Han, George Karypis, Vipin Kumar · IEEE Transactions on Knowledge and Data Engineering · 2000
The authors propose two new parallel formulations of the Apriori algorithm (R. Agrawal and R. Srikant, 1994) that is used for computing association rules. These new formulations, IDD and HD, address the shortcomings of two previously proposed parallel formulations CD and DD. Unlike the CD algorithm, the IDD algorithm partitions the candidate set intelligently among processors to efficiently parallelize the step of building the hash tree. The IDD algorithm also eliminates the redundant work inherent in DD, and requires substantially smaller communication overhead than DD. But IDD suffers from the added cost due to communication of transactions among processors. HD is a hybrid algorithm that combines the advantages of CD and DD. Experimental results on a 128-processor Cray T3E show that HD scales just as well as the CD algorithm with respect to the number of transactions, and scales as well as IDD with respect to increasing candidate set size.
Cited by 174
Theodoros Toliopoulos, Anastasios Gounaris, Kostas Tsichlas et al. · Research Explorer (The University of Manchester) · 2018
In this work, we focus on distance-based outliers in a metric space, where the status of an entity as to whether it is an outlier is based on the number of other entities in its neighborhood. In the recent years, several solutions have tackled the problem of distance-based outliers in data streams, where outliers must be mined continuously as new elements become available. An interesting research problem is to combine the streaming environment with massively parallel systems to provide scalable stream-based algorithms. However, none of the previously proposed techniques refer to a massively parallel setting. Our proposal fills this gap and studies transferring state-of-the-art techniques in Apache Flink, a modern platform for intensive streaming analytics. We thoroughly present the technical challenges encountered and the alternatives that may be applied. We show speed-ups up to 117 (resp. 2076) times over a naive parallel (resp. non-parallel) solution in Flink, by using just an ordinary 4-core machine and a real-world dataset. Our results demonstrate that oulier mining can be achieved in an efficient and scalable manner. The resulting techniques have been made publicly available in open-source.
Cited by 12Open access
Srinivasan Parthasarathy, Mohammed J. Zaki, Wei Li · 1997
A lot of data mining tasks, such as Associations, Sequences, and Classification, use complex pointer-based data structures that typically suffer from sub-optimal locality. In the multiprocessor case shared access to these data structures may also result in false-sharing. Most of the optimization techniques for enhancing locality and reducing false sharing have been proposed in the context of numeric applications involving array-based data structures, and are not applicable for dynamic data structures due to dynamic memory allocation from the heap with arbitrary addresses. Within the context of data mining it is commonly observed that the building phase of these large recursive data structures, such as hash trees and decision trees, is random and independent from the access phase which is usually ordered and typically dominates the computation time. In such cases locality and false sharing sensitive memory placement of these structures can enhance performance significantly. We evaluate ...
Cited by 2
Allen D. Malony, Kevin Huck · 2009
Parallel applications running on high-end computer systems manifest a complex combination of performance phenomena, such as communication patterns, work distributions, and computational inefficiencies. Current performance tools compute results that help to describe performance behavior, as well as to understand performance problems and how they came about. Unfortunately, parallel performance tool research has been limited in its contributions to large-scale performance data management and analysis, automated performance investigation, and knowledge-based performance problem reasoning.
This dissertation discusses the design of a performance analysis methodology and framework which integrates scalable data management, dimension reduction, clustering, classification and correlation analysis of individual trials of large dimensions, and comparative analysis between multiple application executions. Analysis process workflows can be captured, automating what would otherwise be time-consuming and possibly error prone tasks. More importantly, process automation provides an extensible interface to the analysis process. The methods also integrate context metadata and a rule-based system in order to capture expert performance analysis knowledge about known anomalous behavior patterns. Applying this knowledge to performance analysis results and associated metadata provides a mechanism for diagnosing the causes of performance problems, rather than just summarizing results. Our prototype implementation of our data mining framework, PerfExplorer, and our data management framework, PerfDMF, are applied in large-scale performance studies to demonstrate each thesis contribution. The dissertation concludes with a discussion of future research directions.
Cited by 1
Julien Collet, Tanguy Sassolas, Yves Lhuillier et al. · HAL (Le Centre pour la Communication Scientifique Directe) · 2015
International audience
Cited by 0
Albert Y. Zomaya, Tarek El‐Ghazawi, Ophir Frieder · IEEE Concurrency · 1999
Cited by 14
Yang, Chunsheng, Létourneau, Sylvain · NPARC · 2005
In many practical applications, data mining results must be quickly delivered. To achieve the required efficiency, without sacrificing the quality of the results, practitioners are now looking at ways to parallelize the most computationally expensive steps of the data mining process. Realizing that a complete rewriting of existing sequential programs into parallel ones is often too tedious and expensive, we propose a framework which re-uses existing sequential programs to perform parallel data mining on a computer cluster. The proposed framework relies on the JavaParty system and can be used to parallelize both Java and non-Java programs. This paper details the framework, illustrates the implementation, and presents early experimental results showing the benefits of the approach.
Cited by 0Open access
Sandipan Sarkar, Sandipan Sarkar · University of Minnesota Digital Conservancy (University of Minnesota) · 1997
Cited by 0Open access
Massimo Coppola, Marco Vanneschi · IGI Global eBooks · 2011
We consider the application of parallel programming environments to develop portable and efficient high performance data mining (DM) tools. We first assess the need of parallel and distributed DM applications, by pointing out the problems of scalability of some mining techniques and the need to mine large, eventually geographically distributed databases. We discuss the main issues of exploiting parallel and distributed computation for DM algorithms. A high-level programming language enhances the software engineering aspects of parallel DM, and it simplifies the problems of integration with existing sequential and parallel data management systems, thus leading to programming-efficient and high-performance implementations of applications. We describe a programming environment we have implemented that is based on the parallel skeleton model, and we examine the addition of object-like interfaces toward external libraries and system software layers. This kind of abstractions will be included in the forthcoming programming environment ASSIST. In the main part of the chapter, as a proof-of-concept we describe three well-known DM algorithms, Apriori, C4.5, and DBSCAN. For each problem, we explain the sequential algorithm and a structured parallel version, which is discussed and compared to parallel solutions found in the literature. We also discuss the potential gain in performance and expressiveness from the addition of external objects on the basis of the experiments we performed so far. We evaluate the approach with respect to performance results, design, and implementation considerations.Request access from your librarian to read this chapter's full text.
Cited by 1
Masayuki Yoshikawa, Hidekazu Terai · 2006
The job-shop scheduling problem is concerned with allocating limited resources to operations over time. Although the job shop scheduling has an important role in various fields, it is one of the most difficult problems in combinational optimization. In this paper, we propose a new scheduling technique that combines Ant Colony Optimization (ACO) with GT method in order to realize effective scheduling. ACO approach has been applied recently to several combinational optimization problems, e.g., TSP and scheduling problem. However, no studies have ever seen the approach of applying hybrid ACO to job-shop problems. Experimental results using benchmark data show improvement comparison with a conventional scheduling technique.
Cited by 2
Manh‐Hung Nguyen, Dau Hai Phong · Research and Development on Information and Communication Technology · 2017
Mining high utility itemsets in transaction database is an important task in data mining and widely applied in many areas. Recently, many algorithms have been proposed, but most algorithms for identifying high utility itemsets need to generate candidate sets by overestimating their utility and then calculating their exact utility value. Therefore, the number of candidate itemsets is much larger than the actual number of high utility itemsets. In this paper, we introduce the Retail Transaction-Weighted Utility (RTWU) structure and propose two algorithms: EAHUIMiner algorithm and PEAHUI-Miner parallel algorithm. They have been experimented and compared to the two most efficient algorithms: EFIM and FHM. Results show that our algorithm is better with sparse datasets. DOI: 10.32913/rd-ict.vol3.no14.519
Cited by 0
Peter Christen, Markus Hegland, Ole M. Nielsen⋆ et al. · 2001
This paper presents our approach to data mining that allows the coupling of parallel applications with a scripting language resulting in an efficient and flexible toolbox. Parallel algorithms which are scalable both in data size and number of processors are a key issue to be able to solve the ever increasing problems in data mining. On the other hand, data mining applications should be flexible to allow interactive data exploration. By using a toolbox written in a scripting language we are able to steer parallel applications in a flexible way, thus fulfilling the needs of a data miner for fast interactive data analysis. The chosen approach is discussed and first results are presented.
Cited by 0
Fadi Thabtah, Suhel Hammoud, Hussein Abdel-Jaber · Parallel Processing Letters · 2015
Associative classification (AC) is a research topic that integrates association rules with classification in data mining to build classifiers. After dissemination of the Classification-based Association Rule algorithm (CBA), the majority of its successors have been developed to improve either CBA's prediction accuracy or the search for frequent ruleitems in the rule discovery step. Both of these steps require high demands in processing time and memory especially in cases of large training data sets or a low minimum support threshold value. In this paper, we overcome the problem of mining large training data sets by proposing a new learning method that repeatedly transforms data between line and item spaces to quickly discover frequent ruleitems, generate rules, subsequently rank and prune rules. This new learning method has been implemented in a parallel Map-Reduce (MR) algorithm called MRMCAR which can be considered the first parallel AC algorithm in the literature. The new learning method can be utilised in the different steps within any AC or association rule mining algorithms which scales well if contrasted with current horizontal or vertical methods. Two versions of the learning method (Weka, Hadoop) have been implemented and a number of experiments against different data sets have been conducted. The ground bases of the comparisons are classification accuracy and time required by the algorithm for data initialization, frequent ruleitems discovery, rule generation and rule pruning. The results reveal that MRMCAR is superior to both current AC mining algorithms and rule based classification algorithms in improving the classification performance with respect to accuracy.
Cited by 19
Jinlin Wang, Xi Chen, Kefa Zhou et al. · 2008
Sequential pattern has important applications in many areas and a large number of data and patterns need efficient and scalable parallel algorithm. In light of the widespread problem in current sequential pattern data mining algorithm and on the basis of researching the data mining algorithm of serial sequential pattern, a data mining algorithm of parallel sequential pattern is presented in this paper. Through theoretical analysis and experimental verification, the parallel data mining algorithm can well improve the efficiency of data mining in massive data circumstances.
Cited by 2
Wenwu Lian, Xiaoshu Zhu, Jie Zhang et al. · International Journal of Grid and Distributed Computing · 2015
With the rapid development of computer science and technology, more and more data is stored in the computer storage media , data mining (DM) emerged as an interdisciplinary subject , it is based on a method previously used researcher science and algorithms . Cloud computing is an emerging shared infrastructure approach that open standards and service-based, Internet-centric , providing safe , fast and convenient data storage and network computing services. The cloud computing applications to data mining, you can tap the growing number of mass data solutions. This paper presents a cloud computing environment suitable for partitioning the data set allocation method and data sets; introduces improved Apriori algorithm based on its calculation of two parallel processes running on the platform in the cloud, the results of the simulation.
Cited by 2Open access
Shaojie Qiao, Tianrui Li, Jing Peng et al. · International Journal of Computational Intelligence Systems · 2010
The trajectory pattern mining problem has recently attracted much attention due to the rapid development of location-acquisition technologies, and parallel computing essentially provides an alternative method for handling this problem. This study precisely addresses the problem of parallel mining of trajectory sequential patterns based on the newly proposed concepts with regard to trajectory pattern mining. We propose an efficient and effective parallel sequential patterns mining (plute) algorithm that includes three essential techniques: prefix projection, data parallel formulation, and task parallel formulation. Firstly, the prefix projection technique is used to decompose the search space as well as greatly reduce the candidate trajectory sequences. Secondly, the data parallel formulation decomposes the computations associated with counting the support of trajectory patterns. Thirdly, the task parallel formulation employs the MapReduce programming model to assign the computations across a set of machines in a scalable and easy-to-use fashion. Based on the properties of parallel trajectory sequences, item pruning and sequence pruning strategies are applied to further prune the candidate sequences. Extensive experiments are conducted to evaluate the performance of plute in terms of parallel computing time and communication cost among processors. Experimental results show that plute outperforms the previously proposed parallel mining strategy (PartSpan) in mining massive trajectory data.
Cited by 35Open access
Schelter, Sebastian · DepositOnce · 2016
This thesis lays the ground work for enabling scalable data mining in massively parallel dataflow systems, using large datasets. Such datasets have become ubiquitous. We illustrate common fallacies with respect to scalable data mining: It is in no way sufficient to naively implement textbook algorithms on parallel systems; bottlenecks on all layers of the stack prevent the scalability of such naive implementations. We argue that scalability in data mining is a multi-leveled problem and must therefore be approached on the interplay of algorithms, systems, and applications. We therefore discuss a selection of scalability problems on these different levels. We investigate algorithm-specific scalability aspects of collaborative filtering algorithms for computing recommendations, a popular data mining use case with many industry deployments. We show how to efficiently execute the two most common approaches, namely neighborhood methods and latent factor models on MapReduce, and describe a specialized architecture for scaling collaborative filtering to extremely large datasets which we implemented at Twitter. We turn to system-specific scalability aspects, where we improve system performance during the distributed execution of a special class of iterative algorithms by drastically reducing the overhead required for guaranteeing fault tolerance. Therefore we propose a novel optimistic approach to fault-tolerance which exploits the robust convergence properties of a large class of fixpoint algorithms and does not incur measurable overhead in failure-free cases. Finally, we present work on an application-specific scalability aspect of scalable data mining. A common problem when deploying machine learning applications in real-world scenarios is that the prediction quality of ML models heavily depends on hyperparameters that have to be chosen in advance. We propose an algorithmic framework for an important subproblem occuring during hyperparameter search at scale: efficiently generating samples from block-partitioned matrices in a shared-nothing environment. For every selected problem, we show how to execute the resulting computation automatically in a parallel and scalable manner, and evaluate our proposed solution on large datasets with billions of datapoints.
Cited by 0Open access