Conference proceeding
Experimental Clarification of Some Issues in Subgraph Isomorphism Algorithms
Intelligent Information and Database Systems 10th Asian Conference, ACIIDS 2018, Dong Hoi City, Vietnam, March 19-21, 2018, Proceedings, Part II, Vol.10752, pp.71-80
Lecture Notes in Artificial Intelligence
ACIIDS: Asian Conference on Intelligent Information and Database Systems, 10th (Dong Hoi City, Vietnam, 19/03/2018 - 21/03/2018)
01/01/2018
Metrics
14 Record Views
UN Sustainable Development Goals (SDGs)
This output has contributed to the advancement of the following goals:
Source: InCites
Abstract
Graph data is ubiquitous in many domains such as social network, bioinformatics, biochemical and image analysis. Finding subgraph isomorphism is a fundamental task in most graph databases and applications. Despite its NP-completeness, many algorithms have been proposed to tackle this problem in practical scenarios. Recently proposed algorithms consistently claimed themselves faster than previous ones, while the fairness of their evaluation is questionable due to query-set selections and algorithm implementations. Although there are some existing works comparing the performance of state-of-the-art subgraph isomorphism algorithms under the same query-sets and implementation settings, we observed there are still some important issues left unclear. For example, it remains unclear how those algorithms behave when dealing with unlabelled graphs. It is debatable that the number of embeddings of a larger query is smaller than that of a smaller query, which further challenges the remark that the time cost should decrease for a good algorithm when increasing the size of the queries. In this paper, we conducted a comprehensive evaluation of three of most recent subgraph algorithms. Through the analysis of the experiment results, we clarify those issues.
Details
- Title
- Experimental Clarification of Some Issues in Subgraph Isomorphism Algorithms
- Creators
- Xuguang Ren - Institute for Integrated and Intelligent Systems (Nathan, QLD, Australia)Junhu Wang - Institute for Integrated and Intelligent Systems (Nathan, QLD, Australia)Nigel Franciscus - Institute for Integrated and Intelligent Systems (Nathan, QLD, Australia)Bela Stantic - Institute for Integrated and Intelligent Systems (Nathan, QLD, Australia)
- Contributors
- N T Nguyen (Editor)D H Hoang (Editor)T P Hong (Editor)H Pham (Editor)B Trawinski (Editor)
- Publication Details
- Intelligent Information and Database Systems 10th Asian Conference, ACIIDS 2018, Dong Hoi City, Vietnam, March 19-21, 2018, Proceedings, Part II, Vol.10752, pp.71-80
- Conference
- ACIIDS: Asian Conference on Intelligent Information and Database Systems, 10th (Dong Hoi City, Vietnam, 19/03/2018 - 21/03/2018)
- Series
- Lecture Notes in Artificial Intelligence
- Publisher
- Springer Nature
- Number of pages
- 10
- Identifiers
- 991013099201102368
- Copyright
- © 2018 Springer International Publishing AG, part of Springer Nature.
- Academic Unit
- Faculty of Science and Engineering
- Language
- English
- Resource Type
- Conference proceeding