Final published version
Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSN › Conference contribution/Paper › peer-review
Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSN › Conference contribution/Paper › peer-review
}
TY - GEN
T1 - Efficient Frequent Subgraph Mining in Transactional Databases.
AU - Welke, Pascal
N1 - DBLP's bibliographic metadata records provided through http://dblp.org/search/publ/api are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.
PY - 2020/10/9
Y1 - 2020/10/9
N2 - Frequent connected subgraph mining (FCSM) has been an active area of research over the last twenty years. This review shall focus on the practical and theoretical issues arising in the transactional setting, where we are given a finite list of small to medium sized graphs and must find all graphs that are subgraph isomorphic to some user-defined number of graphs in the list. In particular, we present the generic approach to FCSM and investigate sufficient conditions for its computational tractability and intractability. Interestingly, it turns out that both depend on the complexity of the Hamiltonian Path problem. This implies that FCSM is computationally tractable only for very restricted transaction graph classes. We subsequently review existing exact FCSM algorithms with a focus on applicability to arbitrary graph databases and present recent approximative FCSM algorithms that remain computationally tractable for all transactional databases.
AB - Frequent connected subgraph mining (FCSM) has been an active area of research over the last twenty years. This review shall focus on the practical and theoretical issues arising in the transactional setting, where we are given a finite list of small to medium sized graphs and must find all graphs that are subgraph isomorphic to some user-defined number of graphs in the list. In particular, we present the generic approach to FCSM and investigate sufficient conditions for its computational tractability and intractability. Interestingly, it turns out that both depend on the complexity of the Hamiltonian Path problem. This implies that FCSM is computationally tractable only for very restricted transaction graph classes. We subsequently review existing exact FCSM algorithms with a focus on applicability to arbitrary graph databases and present recent approximative FCSM algorithms that remain computationally tractable for all transactional databases.
U2 - 10.1109/DSAA49011.2020.00044
DO - 10.1109/DSAA49011.2020.00044
M3 - Conference contribution/Paper
SN - 9781728182070
SP - 307
EP - 314
BT - Efficient Frequent Subgraph Mining in Transactional Databases.
PB - IEEE
T2 - 2020 IEEE 7th International Conference on Data Science and Advanced Analytics (DSAA)
Y2 - 6 October 2020 through 9 October 2020
ER -