Supergraph Search 알고리즘 IDAR의 병렬화에 대한 실험 분석 = Experimental Analysis of Parallelization in Supergraph Search Algorithm IDAR

국문 초록 (Abstract)

그래프 분석에서 핵심적인 문제 중 하나는 Supergraph search 문제이다. Supergraph search 문제는 다수의 데이터 그래프들과 한 개의 쿼리 그래프에 대하여 쿼리 그래프에 임베딩(embedding)이 있는 데이터 그래프들을 찾는 문제이다. 이 문제를 해결하는 최신 알고리즘인 IDAR에서는 방향성 비사이클 그래프(IDAG)와 그래프 사이의 동적 계획법(IDAG-Graph DP) 그리고 active-first search를 통해 문제를 효율적으로 해결하였다. 본 논문에서는 IDAR에서 제안한 Supergraph search 중 query processing 과정을 병렬화를 통해 성능을 개선하였다. 또한, 병렬화를 위한 새로운 자료 구조를 도입하였고, 실제 데이터 그래프를 통해 실험을 진행하여서 성능을 측정하고 결과를 분석하였다.

참고문헌 (Reference)

1 S. Nowozin, "Weighted Substructure Mining for Image Analysis" 1-8, 2007

2 H. Kim, "Versatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching" 925-937, 2021

3 F. Chen, "Towards Graph Containment Search and Indexing" 926-937, 2007

4 S. Sun, "Scaling up subgraph query processing with efficient subgraph matching" 220-231, 2019

5 B. Lyu, "Scalable supergraph search in large graph databases" 157-168, 2016

6 G. Zhu, "Prefindex: An efficient supergraph containment search technique" 360-378, 2010

7 G. Zhu, "PrefIndex: An Efficient Supergraph Containment Search Technique" 360-378, 2010

8 H. Kim, "IDAR: fast supergraph search using DAG integration" 13 (13): 1456-1468, 2020

9 W. Fan, "Graph Pattern Matching Revised for Social Network Analysis" 8-21, 2012

10 X. Yan, "Graph Indexing : A Frequent Structure based Approach" 335-346, 2004

11 M. Han, "Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together" 1429-1445, 2019

12 N. Pržulj, "Efficient Estimation of Graphlet Frequency Distributions in Protein-protein Interaction Networks" 22 (22): 974-980, 2006

13 M. Cannataro, "Data Management of Protein Interaction Networks" John Wiley & Sons 2012

14 S. Zhang, "A novel approach for efficient supergraph query processing on graph databases" 204-215, 2009