DC Field | Value | Language |
---|---|---|
dc.contributor.author | Kim, Hyunjoon | - |
dc.contributor.author | Choi, Yunyoung | - |
dc.contributor.author | Park, Kunsoo | - |
dc.contributor.author | Lin, Xuemin | - |
dc.contributor.author | Hong, Seok-Hee | - |
dc.contributor.author | Han, Wook-Shin | - |
dc.date.accessioned | 2023-04-07T01:40:25Z | - |
dc.date.available | 2023-04-07T01:40:25Z | - |
dc.date.created | 2022-07-04 | - |
dc.date.issued | 2022-06 | - |
dc.identifier.issn | 1066-8888 | - |
dc.identifier.uri | https://oasis.postech.ac.kr/handle/2014.oak/117131 | - |
dc.description.abstract | © 2022, The Author(s), under exclusive licence to Springer-Verlag GmbH Germany, part of Springer Nature.Subgraph query processing (also known as subgraph search) and subgraph matching are fundamental graph problems in many application domains. A lot of efforts have been made to develop practical solutions for these problems. Despite the efforts, existing algorithms showed limited running time and scalability in dealing with large and/or many graphs. In this paper, we propose a new subgraph search algorithm using equivalences of vertices in order to reduce search space: (1) static equivalence of vertices in a query graph that leads to an efficient matching order of the vertices and (2) dynamic equivalence of candidate vertices in a data graph, which enables us to capture and remove redundancies in search space. These techniques for subgraph search also lead to an improved algorithm for subgraph matching. Experiments show that our approach outperforms state-of-the-art subgraph search and subgraph matching algorithms by up to several orders of magnitude with respect to query processing time. | - |
dc.language | English | - |
dc.publisher | Springer Science and Business Media Deutschland GmbH | - |
dc.relation.isPartOf | VLDB Journal | - |
dc.title | Fast subgraph query processing and subgraph matching via static and dynamic equivalences | - |
dc.type | Article | - |
dc.identifier.doi | 10.1007/s00778-022-00749-x | - |
dc.type.rims | ART | - |
dc.identifier.bibliographicCitation | VLDB Journal, v.32, pp.343 - 368 | - |
dc.identifier.wosid | 000807272000001 | - |
dc.citation.endPage | 368 | - |
dc.citation.startPage | 343 | - |
dc.citation.title | VLDB Journal | - |
dc.citation.volume | 32 | - |
dc.contributor.affiliatedAuthor | Han, Wook-Shin | - |
dc.identifier.scopusid | 2-s2.0-85131573928 | - |
dc.description.journalClass | 1 | - |
dc.description.journalClass | 1 | - |
dc.description.isOpenAccess | N | - |
dc.type.docType | Article; Early Access | - |
dc.subject.keywordPlus | ISOMORPHISM | - |
dc.subject.keywordPlus | EFFICIENT | - |
dc.subject.keywordPlus | ALGORITHM | - |
dc.subject.keywordPlus | OPTIMIZATION | - |
dc.subject.keywordPlus | INDEX | - |
dc.subject.keywordAuthor | Vertex equivalence | - |
dc.subject.keywordAuthor | Neighbor-safety | - |
dc.subject.keywordAuthor | Subgraph matching | - |
dc.subject.keywordAuthor | Subgraph query processing | - |
dc.subject.keywordAuthor | Subgraph search | - |
dc.relation.journalWebOfScienceCategory | Computer Science, Hardware & Architecture | - |
dc.relation.journalWebOfScienceCategory | Computer Science, Information Systems | - |
dc.description.journalRegisteredClass | scie | - |
dc.description.journalRegisteredClass | scopus | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
library@postech.ac.kr Tel: 054-279-2548
Copyrights © by 2017 Pohang University of Science ad Technology All right reserved.