Leveraging homomorphisms and bitmaps to enable the mining of embedded patterns from large data trees

Xiaoying Wu, Dimitri Theodoratos

Research output: Chapter in Book/Report/Conference proceedingConference contribution

8 Scopus citations

Abstract

Finding interesting tree patterns hidden in large datasets is an important research area that has many practical applications. Along the years, research has evolved from mining induced patterns to mining embedded patterns. Embedded patterns allow for discovering useful relationships which cannot be captured by induced patterns. Unfortunately, previous contributions have focused almost exclusively on mining patterns from a set of small trees. The problem of mining embedded patterns from large data trees has been neglected. This is mainly due to the complexity of this task related to the problem of unordered tree embedding test being NP-Complete. However, mining embedded patterns from large trees is important for many modern applications that arise naturally and in particular with the explosion of big data. In this paper, we address the problem of mining unordered frequent embedded tree patterns from large trees. We propose a novel approach that exploits efficient homomorphic pattern matching algorithms to compute pattern support incrementally and avoids the costly enumeration of all pattern matchings required by previous approaches. A further originality of our approach is that matching information of already computed patterns is materialized as bitmaps. This technique not only minimizes the memory consumption but also reduces CPU costs by translating pattern evaluation to bitwise operations. An extensive experimental evaluation shows that our approach not only mines embedded patterns from real datasets up to several orders of magnitude faster than state-of-theart tree mining algorithms applied to large data trees but also scales well empowering the extraction of patterns from large datasets where previous approaches fail.

Original languageEnglish (US)
Title of host publicationDatabase Systems for Advanced Applications - 20th International Conference, DASFAA 2015, Proceedings Hanoi, Vietnam, April 20-23, 2015 Proceedings, Part I
EditorsCyrus Shahabi, Muhammad Aamir Cheema, Matthias Renz, Xiaofang Zhou
PublisherSpringer Verlag
Pages3-20
Number of pages18
ISBN (Print)9783319181196
DOIs
StatePublished - 2015
Event20th International Conference on Database Systems for Advanced Applications, DASFAA 2015 - Hanoi, Viet Nam
Duration: Apr 20 2015Apr 23 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9049
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other20th International Conference on Database Systems for Advanced Applications, DASFAA 2015
Country/TerritoryViet Nam
CityHanoi
Period4/20/154/23/15

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Keywords

  • Bitmap view
  • Holistic twig-join algorithm
  • Tree pattern mining

Fingerprint

Dive into the research topics of 'Leveraging homomorphisms and bitmaps to enable the mining of embedded patterns from large data trees'. Together they form a unique fingerprint.

Cite this