Accelerating Subgraph Search in a Heterogeneous Graph Using GPUs

서브 그래프 탐색은 그래프 분석기법 중 하나이며 질의 그래프가 원본 그래프에 존재할 수 있는 모든 경우를 확인해야 하는 잘 알려진 NP-hard 문제이다. 이러한 문제점을 해결하기 위해 최근의 연구에서는 GPU를 활용하고 있으며 효율적인 필터링 방법을 제안한다. 이종 그래프의 특성을 고려한 효율적인 그래프 인코딩 전략으로 GSI(GPU-friendly Subgraph Isomorphism)가 제안되었다. 그러나 GSI 또한 그래프 크기가 커짐에 따라 인코딩 결과인 비트 테이블의 크기가 증가하여 Host-to-Device 전송 시간이 증가하게 되는 문제가 있다. 본 논문에서는 이와 같은 문제를 해결하는 이종 그래프 환경에서 효율적인 서브 그래프 탐색 기법을 제안한다. 제안하는 기법은 비트 테이블의 크기를 감소시켜 Host-to-Device 전송 시간을 줄인다. 또한, GPU를 활용한 동시 실행 전략을 통해 서브 그래프 탐색의 각 연산을 작은 연산들로 분할하고 같은 시간에 동시에 처리하여 전체 처리 시간을 효과적으로 감소시킨다. 다양한 성능 평가를 통해 제안하는 기법이 기존 기법에 비해 성능이 우수함을 보인다. 특히, 제안하는 기법은 기존 기법 대비 질의 처리 시간을 최대 3.50% 감소시킨다.