Efficient Graph Isomorphism Query Processing using Degree Sequences and Color-Label Distributions
- Title
- Efficient Graph Isomorphism Query Processing using Degree Sequences and Color-Label Distributions
- Authors
- Gu, Geonmo; Nam, Yehyun; Park, Kunsoo; Galil, Zvi; Italiano, Giuseppe F.; Han, Wook-Shin
- Date Issued
- 2022-05-09
- Publisher
- IEEE Computer Society
- Abstract
- © 2022 IEEE.Given a set of data graphs and a query graph, graph isomorphism query processing is the problem of finding all the data graphs that are isomorphic to the query graph. Graph isomorphism query processing is a core problem in graph analysis of various application domains. In existing approaches, index construction or query processing takes much time as the graph sizes increase. In this paper, we propose an efficient algorithm for graph isomorphism query processing. We introduce the color-label distribution which represents the canonical coloring of a vertex-labeled graph. Based on degree sequences and color-label distributions, we introduce a two-level index, which helps us efficiently solve graph isomorphism query processing. Experimental results on real datasets show that the proposed algorithm is orders of magnitude faster than the state-of-the-art algorithms in terms of index construction time, and it runs faster than existing algorithms in terms of query processing time as the graph sizes increase.
- URI
- https://oasis.postech.ac.kr/handle/2014.oak/117130
- ISSN
- 1084-4627
- Article Type
- Conference
- Citation
- 38th Int’l Conf. on Data Engineering, page. 872 - 884, 2022-05-09
- Files in This Item:
- There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.