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.