Mining Frequent Sequential Patterns under a Similarity Constraint

Many practical applications are related to frequent sequential pattern mining, ranging from Web Usage Mining to Bioinformatics. To ensure an appropriate extraction cost for useful mining tasks, a key issue is to push the user-defined constraints deep inside the mining algorithms. In this paper, we study the search for frequent sequential patterns that are also similar to an user-defined reference pattern. While the effective processing of the frequency constraints is well-understood, our contribution concerns the identification of a relaxation of the similarity constraint into a convertible anti-monotone constraint. Both constraints are then used to prune the search space during a levelwise search. Preliminary experimental validations have confirmed the algorithm efficiency.