서울대 컴퓨터공학부 박근수 교수 연구진,
SIGMOD 2019에 논문 게재

박근수 교수 연구진의 부분그래프 매칭 (subgraph matching) 알고리즘에 관한 최신 연구 논문이 SIGMOD 2019에 게재되었다. SIGMOD는 데이터베이스와 빅데이터 분야에서 세계 최고로 인정받고 있는 학회이다.

본 논문은 소셜 네트워크 등에서 특정한 패턴을 찾아내는 알고리즘을 제시한 것으로서 현재까지 알려진 알고리즘 중에서 가장 빠른 성능을 보인다. 논문에서 제안한 알고리즘은 benchmark 그래프들에서 이전 최고 성능 알고리즘보다 최대 10,000배 빠르게 패턴을 찾아내며, 크기가 큰 패턴도 빠르게 찾을 수 있다.

확장성(scalability)에 있어서도 획기적인 개선이 있어서, 이전 알고리즘이 최대 million-scale 그래프에 대해 실험을 했던 것에 비해 본 알고리즘은 billion-scale 그래프 Twitter에서도 뛰어난 성능을 보여준다.

본 논문은 2019년 7월에 열리는 SIGMOD 2019에서 발표될 예정이다.

M. Han, H. Kim, G. Gu, K. Park, and W.S. Han, Efficient subgraph matching: harmonizing dynamic programming, adaptive matching order, and failing set together, ACM International Conference on Management of Data (SIGMOD) 2019, Amsterdam, Netherlands.