Efficient Sequential Pattern Mining Based on Pattern Growth

Abstract

The goal of this paper is to make efficient sequential pattern mining by increasing the pattern growth. Traditional pattern-growth based approaches for sequential pattern mining allows unidirectional pattern-growth. Here only the suffix of the detected pattern is increased. But UDDAG allows bidirectional pattern-growth along both end of the detected patterns. It makes fewer levels of recursion and faster pattern growth in the detected patterns. Sequential pattern mining derive length-(k + 1) patterns based on the projected databases of length-k patterns recursively, used by traditional pattern growth-based approaches. At each level of recursion, they unidirectionally grow the length of detected patterns by one along the suffix of detected patterns, which needs k levels of recursion to find a length-k pattern. In this paper, a novel data structure, UpDown Directed Acyclic Graph (UDDAG), is invented for efficient sequential pattern mining. UDDAG allows bidirectional pattern growth along both ends of detected patterns. Thus, a length-k pattern can be detected in log2[k+ 1] levels of recursion at best, which results in fewer levels of recursion and faster pattern growth. When minSup is large such that the average pattern length is close to 1, UDDAG and PrefixSpan have similar performance because the problem degrades into frequent item counting problem. However, UDDAG scales up much better. UDDAG is also considerably faster than Spade and LapinSpam. UDDAG uses comparable memory to that of PrefixSpan and less memory than Spade and LapinSpam