[연구의 필요성]
동적 서브그래프 매칭은 데이터 그래프가 업데이트될 때, 주어진 질의 그래프와 새롭게 매치되거나 더 이상 매치되지 않는 서브그래프를 찾는 문제이다. 동적 서브그래프 매칭은 사기 탐지를 비롯한 다양한 실생활 응용 분야에서 활용된다. 동적 서브그래프 매칭을 수행하는 다양한 방법이 개발됨에 따라, 각 방법을 공정하게 비교하고 장단점을 분석할 필요가 있다. 그러나 기존에 수행된 연구들은 동일한 방법들을 서로 다르게 구현하는 등 공정한 비교를 하지 못했고, 성능 차이를 만드는 핵심 요인 또한 분석하지 않았다. 최근에는 기존 방법들을 하나의 프레임워크 상에 구현하여 성능을 비교하고 분석하려는 시도가 있었지만, 기존 방법들을 틀리게 혹은 비효율적으로 구현하여 잘못된 실험 결과를 얻었으며, 방법별로 공통된 부분을 통합하지 않고 각각 별도로 구현하여 성능 차이에 대한 원인을 정확히 분석하지 못하였다. 따라서,동적 서브그래프 매칭 방법들을 공정하고 심도있게 비교할 수 있는 새로운 프레임워크의 개발이 필요하다.

[포스텍이 가진 고유의 기술]
본 기술은 동적 서브그래프 매칭 문제를 관계형 데이터베이스의 점진적 뷰 유지(IVM)에서의 델타 질의라는 공통된 관점으로 보고, 각 동적 서브그래프 매칭 방법들을 델타 질의 플랜으로 표현 및 수행하는 프레임워크를 제안함으로써 앞서 언급한 문제들을 해결하였다. 먼저, 모든 방법에서 동일한 물리적 연산자에 대해 통일된 구현을 사용하여 기존 방법들을 공정하게 비교하였다. 또한, 기존 방법들에서 사용하는 다양한 기술들을 플랜 일부만 수정함으로써 쉽게 통합하거나 제거할 수 있게 되었고, 이를 통해 각 기술이 성능에 미치는 영향을 상세히 분석했다. 추가적으로, 본 기술은 질의 플랜 컴파일레이션과 같은 관계형 데이터베이스의 기술을 활용하여 기존 방법들의 성능을 더욱 개선하였다.

[연구의 의미]
본 연구는 기존에 수행된 연구들에서 보인 실험 결과 및 분석이 잘못되었음을 밝혔으며, 기존 방법들을 우리 프레임워크를 사용하여 공평하게 다시 비교하였고, 방법들 간의 성능 차이를 내는 요인을 논리적, 물리적 플랜의 관점에서 자세히 분석하였다. 특히, 가장 최신에 나온 방법보다 성능이 낮다고 알려진 기존 방법들도, 제안한 프레임워크 상에서 올바르게 구현한다면 최신 방법보다 최대 48.6배 높은 성능을 보인다는 사실을 밝혔다.

[연구결과의 진행 상태 및 향후 계획]
본 연구는 데이터베이스 시스템 분야 최고 학술대회인 ACM SIGMOD 2024에 발표될 예정이다. 향후 본 연구를 확장하여 동적 서브그래프 매칭 방법들에 대한 비용 기반의 최적화기를 개발하고자 한다.

[성과와 관련된 실적]
Lee, Y., Kim, K., Lee, W., and Han, W.-S., “In-depth Analysis of Continuous Subgraph Matching in a Common Delta Query Compilation Framework,” In 50th Int’l Conf. on Management of Data, ACM SIGMOD, Chile, June 2024. (Corresponding author)

[성과와 관련된 이미지]

(그림 1) 기존 방법인 TurboFlux를 질의 플랜으로 표현한 예시

(그림 2) 기존 방법인 SymBi를 질의 플랜으로 표현한 예시