12.5 并行序列模式挖掘

早期的并行序列模式挖掘算法大多被用于解决算法效率低下的问题。因此，许多并行算法是由其串行版本改进得到。例如，Zaki [28] 扩展了由他自己提出的 SPADE 算法，提出了在内存共享框架下的并行算法 pSPADE。pSPADE 的并行性主要来源于对垂直格式数据库的划分，这种划分既可以横向也可以纵向，最终实现了并行。采用了相似策略的算法还有 Par-ASP [29] 和 Par-CSP [30] 等。

近年来，随着数据量的不断增大、数据类型的不断变化，以及新型并行计算框架（如 HadoopMapReduce 和 Spark）的不断涌现，并行序列模式挖掘算法开始面向更大的数据及更加复杂的应用。Berberich 等人[31]提出了基于 MapReduce 的并行序列模式挖掘算法，从大规模的文本语料中挖掘 n元语法模式。Miliaraki 等人[32]考虑了更为复杂的带有间隔约束的序列模式挖掘问题，提出了基于MapReduce 的大规模带间隔约束的并行序列模式算法 MS-FSM。该算法提出了一系列对序列集合的改写方法，使得在 MapReduce 的任务划分更加平衡，从而取得更好的并行效率。Beedkar 等人[33]又继续对 MS-FSM 算法进行扩展，解决更为复杂的带有层次结构的间隔约束序列模式挖掘问题。所提出的LASH算法在大规模文本数据集上的实验结果显示，当数据具有或者不具有层次结构时，LASH 算法的表现均优于 MS-FSM 算法。我们最近的工作将序列模式挖掘技术与基于线段树的索引技术相结合，实际用于我国证券市场“老鼠仓”发现应用中，实现了基于 MapReduce 和 Spark 的高可扩展趋同行为发现并行算法，将同等规模任务的运行时间从“天”级缩短到分钟级。