Parallel sequence mining on shared-memory machines

We present pSPADE, a parallel algorithm for fast discovery of frequent sequ ences in large databases. pSPADE decomposes the original search space into smaller suffix-based classes. Each class can be solved in main-memory using efficient search techniques and simple join operations. Furthermore, each class can be solved independently on each processor requiring no synchroniz ation. However, dynamic interclass and intraclass load balancing must be ex ploited to ensure that each processor gets an equal amount of work. Experim ents on a 12 processor SGI Origin 2000 shared memory system show good speed up and excellent scaleup results. (C) 2001 Academic Press.