document: Towards bounding sequential patterns 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 .
doc_bio_tags: O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O