MINING MAXIMAL PERIODIC PATTERNS IN FEWER LEVELS OF RECURSION

To reduce the number of levels of recursion for mining maximal periodic patterns a novel data structure, UpDown Directed Acyclic Graph (UDDAG) is invented. UDDAG allows bidirectional pattern growth along both ends of detected patterns which result in fewer levels of recursion than the traditional. To mine k+1 length patterns it uses log2k +1 levels of recursion at best instead of k levels. With UDDAG, at level i recursion, we grow the length of patterns by 2i-1 at most. Thus, a length-k pattern can be detected in log2k+1 levels of recursion at minimum. Traditionally periodic patterns of length k+1 are mined based on the projected database of length k patterns. At each level of recursion they unidirectional grow the length of detected patterns by one along the suffix of detected patterns i.e. the new patterns are obtained by adding one item to the previous level pattern. The UDDAG approach grows patterns from both ends (prefixes and suffixes) of detected patterns, which results in faster pattern growth because of less levels of database projection compared to traditional approaches. This special feature of UDDAG enables its extension toward applications involving searching in large spaces.