document: Mining sequential patterns from probabilistic databases We consider sequential pattern mining in situations where there is uncertainty about which source an event is associated with . We model this in the probabilistic database framework and consider the problem of enumerating all sequences whose expected support is sufficiently large . Unlike frequent itemset mining in probabilistic databases ( C. Aggarwal et al. . KDD ' 09 ; Chui et al. , PAKDD ' 07 ; Chui and Kao , PAKDD ' 08 ) , we use dynamic programming ( DP ) to compute the probability that a source supports a sequence , and show that this suffices to compute the expected support of a sequential pattern . Next , we embed this DP algorithm into candidate generate-and-test approaches , and explore the pattern lattice both in a breadth-first ( similar to GSP ) and a depth-first ( similar to SPAM ) manner . We propose optimizations for efficiently computing the frequent 1-sequences , for re-using previously-computed results through incremental support computation , and for elmiminating candidate sequences without computing their support via probabilistic pruning . Preliminary experiments show that our optimizations are effective in improving the CPU cost .
doc_bio_tags: O O O O B 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 B 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 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