Skip to main content

Towards bounding sequential patterns

Publication ,  Conference
Raïssi, C; Pei, J
Published in: Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
January 1, 2011

Given a sequence database, can we have a non-trivial upper bound on the number of sequential patterns? The problem of bounding sequential patterns is very challenging in theory due to the combinatorial complexity of sequences, even given some inspiring results on bounding itemsets in frequent itemset mining. Moreover, the problem is highly meaningful in practice, since the upper bound can be used in many applications such as space allocation in building sequence data warehouses. In this paper, we tackle the problem of bounding sequential patterns by presenting, for the first time in the field of sequential pattern mining, strong combinatorial results on computing the number of possible sequential patterns that can be generated at a given length k. We introduce, as a case study, two novel techniques to estimate the number of candidate sequences. An extensive empirical study on both real data and synthetic data verifies the effectiveness of our methods. Copyright 2011 ACM.

Duke Scholars

Published In

Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

DOI

Publication Date

January 1, 2011

Start / End Page

1379 / 1387
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Raïssi, C., & Pei, J. (2011). Towards bounding sequential patterns. In Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (pp. 1379–1387). https://doi.org/10.1145/2020408.2020612
Raïssi, C., and J. Pei. “Towards bounding sequential patterns.” In Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 1379–87, 2011. https://doi.org/10.1145/2020408.2020612.
Raïssi C, Pei J. Towards bounding sequential patterns. In: Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2011. p. 1379–87.
Raïssi, C., and J. Pei. “Towards bounding sequential patterns.” Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2011, pp. 1379–87. Scopus, doi:10.1145/2020408.2020612.
Raïssi C, Pei J. Towards bounding sequential patterns. Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2011. p. 1379–1387.

Published In

Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

DOI

Publication Date

January 1, 2011

Start / End Page

1379 / 1387