Publications
Authors:
  • Mostafa Haghir Chehreghani , Morteza Haghir Chehreghani
Citation:
ECML-PKDD, Riva del Garda, Italy, September 19-23, 2016.
Abstract:
In the transactional setting of finding frequent embedded patterns from
a large collection of tree-structured data, the crucial step is to decide whether a
tree pattern is subtree homeomorphic to a database tree. Our extensive study on
the properties of real-world tree-structured datasets reveals that while many vertices
in a database tree may have the same label, no two vertices on the same
path are identically labeled. In this paper, we exploit this property and propose a
novel and efficient method for deciding whether a tree pattern is subtree homeomorphic
to a database tree. Our algorithm is based on a compact data-structure,
called EMET, that stores all information required for subtree homeomorphism.
We propose an efficient algorithm to generate EMETs of larger patterns using
EMETs of the smaller ones. Based on the proposed subtree homeomorphism
method, we introduce TTM, an effective algorithm for finding frequent tree patterns
from rooted ordered trees. We evaluate the efficiency of TTM on several
real-world and synthetic datasets and show that it outperforms well-known existing algorithms by an order of magnitude.
Year:
2016
Report number:
2016/064