.png){kind=icon}
Return
An UpDown Directed Acyclic Graph Approach for Sequential Pattern Mining
.png){kind=icon}
PRE
AI
DOI：10.1109/TKDE.2009.135.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 left perpendicular log(2)k + 1 right perpendicular 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.
Keywords:
Data mining algorithm
directed acyclic graph
performance analysis
sequential pattern
transaction database
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
10.4
Papers:
6.9K
Citations:
3.2W
Organization
No organization information available
Cited Papers
.png){kind=icon}
ShareSaveShareSaveShareSave
ShareSave
View more