Discovering frequent weak XML patterns

Abstract

<P>PROBLEMS TO DISCOVER FREQUENT PATTERNS FROM A LARGE XML REPOSITORY HAVE ATTRACTED INCREASING RESEARCH ATTENTIONS IN RECENT YEARS. SUCH PROBLEMS BELONG TO THE CATEGORY OF UNORDERED AND INDUCED SUBTREE MINING PROBLEM FOR WHICH NO EFFICIENT AND COMPLETE ALGORITHM HAS BEEN PROPOSED SO FAR. IN THIS THESIS, WE INTRODUCE THE NOTION OF MAPPING EQUIVALENT CLASS FOR REPRESENTING TREES THAT HAVE THE SAME NODE LABEL SET. BASED ON THESE MAPPING EQUIVALENT CLASSES A NOVEL DIVIDE-AND-CONQUER ALGORITHM, WTIMINER, IS PROPOSED FOR DISCOVERY OF FREQUENT UNORDERED AND EMBEDDED SUBTREES WITHOUT LOSS. THE ALGORITHM SUCCESSFULLY DOWNGRADES THE COMPLEXITY OF PATTERN MATCHING AND COUNTING PROBLEM THAT A REGULAR TREE MINING ALGORITHM FACES. EXPERIMENTAL RESULTS DEMONSTRATE THE HIGH EFFICIENCY AND SCALABILITY OF WTIMINER IN TERMS OF BOTH TIME AND SPACE.</P>