SPADE: An efficient algorithm for mining frequent sequences
SPADE: An efficient algorithm for mining frequent sequences
复制标题
DOI：
10.1023/a:1007652502315
复制
发表时间：
2001-01-01
期刊：
影响因子：
7.5
通讯作者：
Zaki, MJ
中科院分区：
文献类型：
--
作者：
Zaki, MJ
本文提出了一种快速发现序列模式的新算法SPADE。现有的解决方案对这个问题进行重复的数据库扫描，并使用复杂的散列结构，具有较差的局部性。SPADE利用组合特性将原始问题分解为更小的子问题，这些子问题可以使用高效的格搜索技术和简单的连接操作在主存中独立求解。所有序列都是在三次数据库扫描中发现的。实验结果表明，SPADE算法的性能比以前最好的算法提高了一倍，并且在一些预处理数据的情况下提高了一个数量级。它还具有相对于输入序列的数量和一些其他数据库参数的线性可伸缩性。最后讨论了序列挖掘的结果如何应用于真实的应用领域。
In this paper we present SPADE, a new algorithm for fast discovery of Sequential Patterns. The existing solutions to this problem make repeated database scans, and use complex hash structures which have poor locality. SPADE utilizes combinatorial properties to decompose the original problem into smaller sub-problems, that can be independently solved in main-memory using efficient lattice search techniques, and using simple join operations. All sequences are discovered in only three database scans. Experiments show that SPADE outperforms the best previous algorithm by a factor of two, and by an order of magnitude with some pre-processed data. It also has linear scalability with respect to the number of input-sequences, and a number of other database parameters. Finally, we discuss how the results of sequence mining can be applied in a real application domain.