Efficiently mining homomorphic patterns from large data trees

Xiaoying Wu, Dimitri Theodoratos, Zhiyong Peng

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

4 Scopus citations

Abstract

Finding interesting tree patterns hidden in large datasets is a central topic in data mining with many practical applications. Unfortunately, previous contributions have focused almost exclusively on mining induced patterns from a set of small trees. The problem of mining homomorphic patterns from a large data tree has been neglected. This is mainly due to the challenging unbounded redundancy that homomorphic tree patterns can display. However, mining homomorphic patterns allows for discovering large patterns which cannot be extracted when mining induced or embedded patterns. Large patterns better characterize big trees which are important for many modern applications in particular with the explosion of big data. In this paper, we address the problem of mining frequent homomorphic tree patterns from a single large tree. We propose a novel approach that extracts non-redundant maximal homomorphic patterns. Our approach employs an incremental frequency computation method that avoids the costly enumeration of all pattern matchings required by previous approaches. Matching information of already computed patterns is materialized as bitmaps a technique that not only minimizes the memory consumption but also the CPU time. We conduct detailed experiments to test the performance and scalability of our approach. The experimental evaluation shows that our approach mines larger patterns and extracts maximal homomorphic patterns from real datasets outperforming stateof- the-art embedded tree mining algorithms applied to a large data tree.

Original languageEnglish (US)
Title of host publicationDatabase Systems for Advanced Applications - 21st International Conference, DASFAA 2016, Proceedings
EditorsShamkant B. Navathe, Weili Wu, Shashi Shekhar, Xiaoyong Du, Hui Xiong, X. Sean Wang
PublisherSpringer Verlag
Pages180-196
Number of pages17
ISBN (Print)9783319320243
DOIs
StatePublished - 2016
Event21st International Conference on Database Systems for Advanced Applications, DASFAA 2016 - Dallas, United States
Duration: Apr 16 2016Apr 19 2016

Publication series

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

Other

Other21st International Conference on Database Systems for Advanced Applications, DASFAA 2016
CountryUnited States
CityDallas
Period4/16/164/19/16

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Efficiently mining homomorphic patterns from large data trees'. Together they form a unique fingerprint.

Cite this