Data placement in massively distributed environments for fast parallel mining of frequent itemsets

Frequent itemset mining presents one of the fundamental building blocks in data mining. However, despite the crucial recent advances that have been made in data mining literature, few of both standard and improved solutions scale. This is particularly the case when (1) the quantity of data tends to be very large and/or (2) the minimum support is very low. In this paper, we address the problem of parallel frequent itemset mining (PFIM) in very large databases and study the impact and effectiveness of using specific data placement strategies in a massively distributed environment. By offering a clever data placement and an optimal organization of the extraction algorithms, we show that the arrangement of both the data and the different processes can make the global job either completely inoperative or very effective. In this setting, we propose two different highly scalable, PFIM algorithms, namely P2S (parallel-2-steps) and PATD (parallel absolute top-down). P2S algorithm allows discovering itemsets from large databases in two simple, yet efficient parallel jobs, while PATD renders the mining process of very large databases more simple and compact. Its mining process is made up of only one parallel job, which dramatically reduces the running time, the communication cost and the energy power consumption overhead in a distributed computational platform. Our different proposed approaches have been extensively evaluated on massive real-world data sets. The experimental results confirm the effectiveness and scalability of our proposals by the important scale-up obtained with very low minimum supports compared to other alternatives.     

一种快速的频繁子图挖掘算法

提出了一种基于关联矩阵的频繁子图挖掘算法。该算法通过对关联矩阵的标准化,有效地降低了子图同构判断的代价。在此基础上,算法利用深度优先的思想,通过逐步扩展频繁边找出所有频繁子图。实验结果表明,该算法比其他同类算法具有更快的速度和更好的稳定性。     

Efficient prime-based method for interactive mining of frequent patterns

Over the past decade, an increasing number of efficient algorithms have been proposed to mine frequent patterns by satisfying the minimum support threshold. Generally, determining an appropriate value for minimum support threshold is extremely difficult. This is because the appropriate value depends on the type of application and expectation of the user. Moreover, in some real-time applications such as web mining and e-business, finding new correlations between patterns by changing the minimum support threshold is needed. Since rerunning mining algorithms from scratch is very costly and time-consuming, researchers have introduced interactive mining of frequent patterns. Recently, a few efficient interactive mining algorithms have been proposed, which are able to capture the content of transaction database to eliminate possibility of the database rescanning. In this paper, we propose a new method based on prime number and its characteristics mainly for interactive mining of frequent patterns. Our method isolates the mining model from the mining process such that once the mining model is constructed; it can be frequently used by mining process with various minimum support thresholds. During the mining process, the mining algorithm reduces the number of candidate patterns and comparisons by using a new candidate set called candidate head set and several efficient pruning techniques. The experimental results verify the efficiency of our method for interactive mining of frequent patterns.     

一种分布式环境中的二分式多层网格skyline算法

skyline计算在数据挖掘、多标准决策和数据库可视化等领域有着非常重要的作用,这些年已经得到了广泛的关注,以往对于skyline查询的研究大多集中在处理集中的数据集上,即集中式skyline查询,已经得到了很多的研究成果。然而,实际情况是：相关数据几乎分散在几个不同的服务器上,因此在分布式环境中的skyline查询计算需要从各个服务器收集大量的数据;现有的在分布式环境中的skyline查询方法有两个主要问题：一是skyline查询的处理时间较慢;二是在网络中服务器之间传输了很多不必要的重叠数据。提出了一种二分式多层网格法（DMLG）,可以有效地处理在分布式环境中的skyline查询。该方法利用网格的方法,借鉴二分法,最大限度地减少了不必要的重叠数据传输,基于不同的数据集的实验表明,这种方法优于现有的方法。     

基于复合粒度计算的频繁模式挖掘研究

针对经典频繁模式挖掘算法存在的不足,提出了一种基于复合粒度计算的频繁模式挖掘算法。该算法借助复合粒度计算方法双向搜索频繁模式,即首先通过二进制的按位取反运算获得复合粒度内涵的像,然后构建复合粒度计算发现频繁模式;虽然该算法需要产生候选项,但它只需扫描一次数据库,减少了I/O开销;算法通过线性数组存储复合信息粒度减少内存使用。理论分析和实验比较表明,其效率优于经典的频繁模式挖掘算法,且内存利用率比较高。     

一种新的多层频繁模式挖掘算法

在多层频繁模式挖掘时,结合映射和并发技术,改进经典的FP-growth算法,提出了多层映射频繁模式增长算法(ML-MFP_Growth).首先对事务数据库中的项目编码预处理,随后对编码数据库的每一列进行映射,构造各层映射频繁模式树(MFP-Tree),最后并发挖掘各层MFP-Tree,得到所有频繁模式.实验表明,ML_MFP_Growth算法比传统多层频繁模式挖掘算法性能有所提高.     

A novel approach for mining maximal frequent patterns

Mining maximal frequent patterns (MFPs) is an approach that limits the number of frequent patterns (FPs) to help intelligent systems operate efficiently. Many approaches have been proposed for mining MFPs, but the complexity of the problem is enormous. Therefore, the run time and memory usage are still large. Recently, the N-list structure has been proposed and verified to be very effective for mining FPs, frequent closed patterns, and top-rank-k FPs. Therefore, this paper uses the N-list structure for mining MFPs. A pruning technique is also proposed to prune branches to reduce the search space. This technique is applied to an algorithm called INLA-MFP (improved N-list-based algorithm for mining maximal frequent patterns) for mining MFPs. Experiments were conducted to evaluate the effectiveness of the proposed algorithm. The experimental results show that INLA-MFP outperforms two state-of-the-art algorithms for mining MFPs.     

互关联后继树在时间序列特征模式挖掘中的应用

在文献[1]中提出的基于互关联后继树（IRST）的时间序列特征模式挖掘方法的基础上,加入了时间窗口的概念,以弥补IRST这种原本应用于文本检索中的索引模型在时间序列应用中的不足.对IRST以及挖掘算法做出了改进,弥补了其只能挖掘出紧密衔接特征模式的缺陷.实验结果表明,该方法可以挖掘出更多更具应用价值的特征模式.     

A secure file sharing service for distributed computing environments

Distributed cryptographic file systems enable file sharing among their users and need the adoption of a key management scheme for the distribution of the cryptographic keys to authorized users according to their specific degree of trust. In this paper we describe the architecture of a basic secure file sharing facility relying on a multi-party threshold-based key-sharing scheme that can be overlaid on top of the existing stackable networked file systems, and discuss its application to the implementation of distributed cryptographic file systems. It provides flexible access control policies supporting multiple combination of roles and trust profiles. A proof of concept prototype implementation within the Linux operating system framework demonstrated its effectiveness in terms of performance and security robustness.     

基于元学习的分布式挖掘频繁闭合模式算法研究*

利用元学习技术提出了一种分布式挖掘频繁闭合模式算法;为适应不同的分布式环境,还给出了该算法的一个变种;最后通过实验讨论了不同分布式下选取算法的策略。算法具有挖掘效率高、通信量少、可靠性高的特点,适合分布式挖掘。     

一种快速的自适应频繁模式挖掘方法

提出一种自适应的频繁模式挖掘算法：AD-Mine算法．该算法采用超结构,根据计算机可用内存自动确定一次性产生超结构的大小,能够自动适应各类不同特性的数据,进行高效率的频繁模式挖掘工作．同时提出了一种能够有效地减少扫描记录数的新颖的数据库划分方法。     

一种高效的频繁模式挖掘算法

在分析研究具有代表性的关联知识挖掘算法的基础上,提出了挖掘频繁模式的一个新的数据库存储结构AFP-树,并在此结构上设计了一个频繁模式挖掘算法。理论研究已经阐明了AFP-树的有效性和相关算法的高效性。     

A new algorithm for fast mining frequent itemsets using N-lists

Mining frequent itemsets has emerged as a fundamental problem in data mining and plays an essential role in many important data mining tasks.In this paper,we propose a novel vertical data representation called N-list,which originates from an FP-tree-like coding prefix tree called PPC-tree that stores crucial information about frequent itemsets.Based on the N-list data structure,we develop an efficient mining algorithm,PrePost,for mining all frequent itemsets.Efficiency of PrePost is achieved by the following three reasons.First,N-list is compact since transactions with common prefixes share the same nodes of the PPC-tree.Second,the counting of itemsets’ supports is transformed into the intersection of N-lists and the complexity of intersecting two N-lists can be reduced to O(m + n) by an efficient strategy,where m and n are the cardinalities of the two N-lists respectively.Third,PrePost can directly find frequent itemsets without generating candidate itemsets in some cases by making use of the single path property of N-list.We have experimentally evaluated PrePost against four state-of-the-art algorithms for mining frequent itemsets on a variety of real and synthetic datasets.The experimental results show that the PrePost algorithm is the fastest in most cases.Even though the algorithm consumes more memory when the datasets are sparse,it is still the fastest one.     

Parallel and distributed methods for incremental frequent itemset mining

Traditional methods for data mining typically make the assumption that the data is centralized, memory-resident, and static. This assumption is no longer tenable. Such methods waste computational and input/output (I/O) resources when data is dynamic, and they impose excessive communication overhead when data is distributed. Efficient implementation of incremental data mining methods is, thus, becoming crucial for ensuring system scalability and facilitating knowledge discovery when data is dynamic and distributed. In this paper, we address this issue in the context of the important task of frequent itemset mining. We first present an efficient algorithm which dynamically maintains the required information even in the presence of data updates without examining the entire dataset. We then show how to parallelize this incremental algorithm. We also propose a distributed asynchronous algorithm, which imposes minimal communication overhead for mining distributed dynamic datasets. Our distributed approach is capable of generating local models (in which each site has a summary of its own database) as well as the global model of frequent itemsets (in which all sites have a summary of the entire database). This ability permits our approach not only to generate frequent itemsets, but also to generate high-contrast frequent itemsets, which allows one to examine how the data is skewed over different sites.     

Privacy-preserving algorithms for distributed mining of frequent itemsets

Standard algorithms for association rule mining are based on identification of frequent itemsets. In this paper, we study how to maintain privacy in distributed mining of frequent itemsets. That is, we study how two (or more) parties can find frequent itemsets in a distributed database without revealing each party’s portion of the data to the other. The existing solution for vertically partitioned data leaks a significant amount of information, while the existing solution for horizontally partitioned data only works for three parties or more. In this paper, we design algorithms for both vertically and horizontally partitioned data, with cryptographically strong privacy. We give two algorithms for vertically partitioned data; one of them reveals only the support count and the other reveals nothing. Both of them have computational overheads linear in the number of transactions. Our algorithm for horizontally partitioned data works for two parties and above and is more efficient than the existing solution.     

A heterogeneous computing system for data mining workflows in multi-agent environments

Abstract: The computing-intensive data mining (DM) process calls for the support of a heterogeneous computing system, which consists of multiple computers with different configurations connected by a high-speed large-area network for increased computational power and resources. The DM process can be described as a multi-phase pipeline process, and in each phase there could be many optional methods. This makes the workflow for DM very complex and it can be modeled only by a directed acyclic graph (DAG). A heterogeneous computing system needs an effective and efficient scheduling framework, which orchestrates all the computing hardware to perform multiple competitive DM workflows. Motivated by the need for a practical solution of the scheduling problem for the DM workflow, this paper proposes a dynamic DAG scheduling algorithm according to the characteristics of an execution time estimation model for DM jobs. Based on an approximate estimation of job execution time, this algorithm first maps DM jobs to machines in a decentralized and diligent (defined in this paper) manner. Then the performance of this initial mapping can be improved through job migrations when necessary. The scheduling heuristic used considers the factors of both the minimal completion time criterion and the critical path in a DAG. We implement this system in an established multi-agent system environment, in which the reuse of existing DM algorithms is achieved by encapsulating them into agents. The system evaluation and its usage in oil well logging analysis are also discussed.     

Computing the minimum-support for mining frequent patterns

Frequent pattern mining is based on the assumption that users can specify the minimum-support for mining their databases. It has been recognized that setting the minimum-support is a difficult task to users. This can hinder the widespread applications of these algorithms. In this paper we propose a computational strategy for identifying frequent itemsets, consisting of polynomial approximation and fuzzy estimation. More specifically, our algorithms (polynomial approximation and fuzzy estimation) automatically generate actual minimum-supports (appropriate to a database to be mined) according to users’ mining requirements. We experimentally examine the algorithms using different datasets, and demonstrate that our fuzzy estimation algorithm fittingly approximates actual minimum-supports from the commonly-used requirements. This work is partially supported by Australian ARC grants for discovery projects (DP0449535, DP0559536 and DP0667060), a China NSF Major Research Program (60496327), a China NSF grant (60463003), an Overseas Outstanding Talent Research Program of the Chinese Academy of Sciences (06S3011S01), and an Overseas-Returning High-level Talent Research Program of China Human-Resource Ministry. A preliminary and shortened version of this paper has been published in the Proceedings of the 8th Pacific Rim International Conference on Artificial Intelligence (PRICAI ’04).