Mining Algorithms for Sequential Patterns in Parallel: Hash Based Approach

Mining Algorithms for Sequential Patterns in Parallel: Hash Based Approach
复制标题

DOI：
10.1007/3-540-64383-4_24
复制
发表时间：
1998-04
期刊：
--
影响因子：
--
通讯作者：
T. Shintani;M. Kitsuregawa
T. Shintani;M. Kitsuregawa
中科院分区：
其他
文献类型：
--
作者：
T. Shintani;M. Kitsuregawa

文献摘要

被引文献

相似文献

在本文中，我们研究了在一个大型的客户交易数据库中挖掘序列模式的问题。由于发现顺序模式必须处理大量的客户交易数据，并需要多次通过数据库，预计并行算法有助于显着提高性能。本文研究了无共享环境下序列模式挖掘的并行算法。提出了三种并行算法：非划分序列模式挖掘（NPSPM）、简单划分序列模式挖掘（SPSPM）和哈希划分序列模式挖掘（HPSPM）。在NPSPM中，候选序列只是在所有节点之间复制，这可能会导致大型数据库的内存溢出。剩下的两个算法将候选序列划分到节点上，随着节点数量的增加，这可以有效地利用整个系统的内存。如果简单地划分，客户交易数据必须广播到所有节点。HPSPM利用哈希函数在节点间划分候选序列，消除了客户交易数据广播，减少了比较工作量。我们描述了这些算法的实现在一个没有共享的并行计算机IBM SP2和它的性能评估结果。在三种算法中，HPSPM算法的性能最好。
In this paper, we study the problem of mining sequential patterns in a large database of customer transactions. Since finding sequential patterns has to handle a large amount of customer transaction data and requires multiple passes over the database, it is expected that parallel algorithms help to improve the performance significantly. We consider the parallel algorithms for mining sequential patterns on a shared-nothing environment. Three parallel algorithms (Non Partitioned Sequential Pattern Mining(NPSPM), Simply Partitioned Sequential Pattern Mining(SPSPM) and Hash Partitioned Sequential Pattern Mining(HPSPM)) are proposed. In NPSPM, the candidate sequences are just copied among all the nodes, which can lead to memory overflow for large databases. The remaining two algorithms partition the candidate sequences over the nodes, which can efficiently exploit the total system's memory as the number of nodes in increased. If it is partitioned simply, customer transaction data has to be broadcasted to all nodes. HPSPM partitions the candidate sequences among the nodes using hash function, which eliminates the customer transaction data broadcasting and reduces the comparison workload. We describe the implementation of these algorithms on a shared-nothing parallel computer IBM SP2 and its performance evaluation results. Among three algorithms HPSPM attains best performance.