부분그래프 매칭은 보안 위협 탐지 및 생물학적 네트워크 분석을 포함하여 광범위한 분야에서 활용되는 핵심 그래프 분석 기법이다. 특히 노드와 엣지에 다양한 라벨이 존재하는 이기종 그래프에서는 구조적 매칭과 라벨 매칭을 모두 고려해야 하므로 보다 정밀한 분석이 요구된다. 그러나 이기종 그래프에서의 부분그래프 매칭은 계산 복잡성이 높은 NP-완비 문제로 규정된다. 이러한 문제를 해결하기 위해 최근 Graphics Processing Units(GPUs)의 병렬성을 활용하는 다양한 부분그래프 매칭 방법들이 제안되었다. 이러한 방법들에서 매칭 공간을 줄이는 후보 필터링(candidate filtering) 전략은 전체 성능에 있어 핵심적인 역할을 한다. 특히 GPU에서 빠른 병렬 비교를 통해 후보 필터링을 수행하는 그래프 인덱싱(graph indexing) 기반 방법들이 점차 주목을 받고 있다. 그중에서도 GSI는 정점 및 이웃 정보를 비트 수준으로 인코딩하여 GPU 상의 병렬 비교를 통한 빠른 후보 필터링을 가능하게 하는 대표적인 그래프 인덱싱 기반 방법이다. 그러나 그래프의 크기와 라벨의 수가 증가할수록 후보 필터링을 위한 인덱스 구조의 크기 역시 증가하여, 호스트 대 디바이스 전송 시간이 길어지고 GPU 메모리 소비가 커지는 문제가 발생한다. 본 논문에서는 이러한 한계를 해결하고 이기종 그래프 환경에서의 탐색 효율을 향상시키기 위한 새로운 GPU 기반 부분그래프 매칭 방법을 제안한다. 제안된 방법은 쿼리 순서를 고려하는 동시 실행(concurrent execution) 전략과 함께 경량의 그래프 인덱스 구조를 도입한다. 다양한 성능 평가에 따르면, 제안된 방법은 쿼리 처리 시간과 GPU 메모리 효율 측면에서 기존 방법들에 비해 우수한 성능을 보인다.

*본 초록은 AI를 통해 원문을 번역한 내용입니다. 정확한 내용은 하기 원문에서 확인해주세요.