A Novel Approach for Scalability a Two Way Sequential Pattern Mining using UDDAG

Abstract

Traditional pattern growth-based approaches for sequential pattern mining derive length- k 1 patterns based on the projected databases of length-k patterns recursively 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 It often outperforms PrefixSpan by almost one order of magnitude in scalability tests UDDAG is also considerably faster than Spade and LapinSpam Except for extreme cases UDDAG uses comparable memory to that of PrefixSpan and less memory than Spade and LapinSpam Additionally the special feature of UDDAG enables its extension toward applications involving searching in large spaces