Search Space Partition-Based Sequential Pattern Mining

In this chapter, we give a formulation of the problem of mining for sequential patterns in a Boolean database. Next, we devise sequential and parallel algorithms, based on search space partitioning, that solve this problem. In Section 10.1, we describe the basic objects involved in the problem of mining for sequential patterns. In Section 10.2, following and extending ideas proposed in [Z98], we identify the search space with the powerset (2A)P, where A is the set of attributes involved and P is the length of the largest sequential pattern that can be discovered. In the next section (Section 10.3), we define a family of equivalence relations over (2A)P that is used in Section 10.4 to derive a partitioning procedure. The procedure is based on recursive bisection and consists of progressively splitting (2A)P into finer and finer equivalence classes. Section 10.5 is dedicated to the development of algorithms for sequential pattern enumeration. First, three complementary join operators, stable with respect to the class partitioning, are defined and analyzed. Next, these operators are used within two search space partition-based algorithms for frequent sequential pattern enumeration: a sequential algorithm (Section 10.5.3) and a parallel one (Section 10.5.4). The latter requires both initial and dynamic load balancing. These issues are discussed in Section 10.5, where load balancing algorithms are given.