Fast Graph Query Processing Algorithms Using Dynamic Programming

Abstract

Over the last several decades, a great deal of efforts have been made to develop practical solutions for NP-hard graph query processing problems because of diverse graph data publicly available. Despite such efforts, the existing algorithms still show a limited scalability in handling large and/or many graphs. In this thesis we consider three important and well-known graph query processing problems, which are subgraph query processing, subgraph matching, and supergraph search.

First, we propose fast algorithms for subgraph query processing and subgraph matching. We describe three advanced techniques including dynamic programming. Experiments on real-world and synthetic datasets show that our algorithms are faster than state-of-the-art subgrpah query processing and subgraph matching algorithms by up to orders of magnitude in terms of query processing time.

Second, we develop a fast and scalable algorithm for the supergraph search problem. We use four novel techniques including dynamic programming. Extensive experiments with real datasets show that our approach outperforms state-of-the-art algorithms by up to orders of magnitude in terms of indexing time and query processing time.

몇 십 년 전부터 다양한 그래프 데이터가 공개되면서, NP-hard 그래프 쿼리 프로세싱 문제들을 위한 실용적인 애플리케이션을 개발하는 데 방대한 노력이 투입되었다. 이러한 노력에도 불구하고 현존하는 알고리즘들은 대용량 혹은 대량의 그래프를 다루는 데 한계를 보여준다. 본 논문에서는 부분그래프 검색, 부분그래프 매칭, 수퍼그래프 검색 등 그래프 쿼리를 처리하는 중요한 문제들을 다룬다.

첫 번째로, 본 논문에서는 부분그래프 쿼리 처리와 부분그래프 매칭을 위한 빠른 알고리즘들을 제안한다. 이를 위해 동적 프로그래밍 (dynamic programming)을 포함하여 세 가지 고급 테크닉을 사용한다. 실제 데이터과 합성 데이터에 대한 실험을 통해 본 알고리즘들이 쿼리 처리 시간에서 현존하는 가장 빠른 알고리즘들보다 최대 수백 배에서 수십만 배 빠름을 검증하였다.

두 번째로, 본 논문에서는 수퍼그래프 검색을 위한 빠르고 확장성 있는 알고리즘을 개발한다. 이를 위해 동적 프로그래밍을 비롯하여 네 가지 새로운 테크닉을 이용한다. 본 논문에서는 실제 데이터를 대상으로 한 방대한 실험을 통해 본 알고리즘이 인덱싱 시간과 쿼리 처리 시간에서 현존하는 가장 빠른 알고리즘보다 최대 수천 배 빠르다는 사실을 보였다.