Skip to main content

2001 | OriginalPaper | Buchkapitel

Search Space Partition-Based Sequential Pattern Mining

verfasst von : Jean-Marc Adamo

Erschienen in: Data Mining for Association Rules and Sequential Patterns

Verlag: Springer New York

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

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.

Metadaten
Titel
Search Space Partition-Based Sequential Pattern Mining
verfasst von
Jean-Marc Adamo
Copyright-Jahr
2001
Verlag
Springer New York
DOI
https://doi.org/10.1007/978-1-4613-0085-4_10