A Universal Formulation of Sequential Patterns
Mahesh V. Joshi, George Karypis, Vipin Kumar · 1999
This paper proposes a universal formulation of sequential patterns, which unies and generalizes most of the previously proposed formulations such as the generalized patterns proposed by Srikant and Agrawal and episode discovery approach taken by Manilla et al. There are two novel concepts in our proposed formulation. First is the directed acyclic graph representation of the structural and timing constraints of sequential patterns. Second, our approach supplies several dierent ways in which support of a pattern can be dened, each of which can be suitable in specic applications, depending on the user's perception. We show that by choosing specic combinations of structural constraints, timing constraints, and support counting methods, our formulation can be made identical to most of the existing formulations. The algorithm used to discover these universal sequential patterns is based on a modication of the GSP algorithm proposed by Srikant and Agrawal. Some of these modications are made to take care of the newly introduced timing constraints and pattern restrictions, whereas some modications are made for performance reasons. In the end, we present an application, which illustrates the deciencies of current approaches that can be overcome by the proposed universal formulation. 1