그래프 알고리즘은 그래프 처리 엔진 상에서 개발되고 실행된다. 이는 산업적으로 널리 사용되는 SQL 질의를 데이터베이스 관리 시스템(DBMS) 엔진 상에서 개발하고 실행하는 것과 유사한 방식이다. 또한, 그래프 알고리즘의 성능 측정을 위해 그래프의 규모가 커질 수록 합성 그래프에 의존하게 된다. 실제 그래프를 구하기 어려울 뿐만 아니라 데이터베이스 분야에서의 TPC 벤치마크처럼 합성 데이터를 사용하는 것이 객관적인 성능 측정에 유리하기 때문이다. 지금까지 RMAT, BA 등 다양한 그래프 합성 모델들이 제안되었다. 그 중 BA는 RMAT보다 더 복잡하지만 RMAT과 달리 2보다 더 큰 degree exponent를 가진 합성 그래프를 생성할 수 있어 각광받았다. 그러나 각 time step마다 이전 time step의 그래프에 의존적인 preferential attachment를 실행한다는 점 때문에 병렬화가 매우 어렵다고 알려져 있다. 본 발표에서는 서로 다른 time step에서 생성되는 두 edge들 간의 혈통 관계(lineage relationship)을 이용하여 세계 최초로 BA 그래프를 병렬화시킨 LineageBA 방법을 소개한다. 혈통 관계의 활용으로 인해 LineageBA는 소규모 클러스터에서도 1조 간선 규모의 그래프를 생성할 수 있다. RMAT이나 BA 모델은 소규모 실제 그래프로부터 특성 파라메터들을 뽑아서 대규모 합성 그래프를 생성하는 방법인 반면, graph upscaling 방법은 소규모 실제 그래프를 더 큰 규모로 확장 생성하는 방법이다. BA보다도 더 복잡하지만 훨씬 더 실제에 가까운 합성 그래프를 얻을 수 있다. 지금까지 합성 그래프에 대한 그래프 알고리즘의 실행은 합성 그래프의 생성, 생성된 그래프에 대한 알고리즘 실행의 두 단계를 따르는 것을 당연한 방식으로 여겨왔다. 그러나 합성 그래프의 규모가 커질 수록 많은 수의 컴퓨터들과 실행시간이 소요되는 문제가 있다. 이에 본 발표에서는 소규모 실제 그래프만 가지고도 최대 1조 간선 규모의 그래프를 생성하고 이에 대해 알고리즘을 실행한 것과 같은 결과를 구할 수 있는 그래프 프로세싱 시뮬레이션 기술(일명: T-GPS)을 소개한다. T-GPS 기술은 그래프 알고리즘이 접근하는 그래프의 일부분을 on the fly 방식으로 생성함으로써 PC 1대만으로도 1조 간선 규모의 합성 그래프에 대한 알고리즘 실행을 가능케 한다.

온라인 줌 링크: https://snu-ac-kr.zoom.us/j/3349805948

김민수 교수는 한국과학기술원(KAIST)에 영년직 부교수로 근무하고 인포랩을 이끌고 있다. 김민수 교수는 2020년 KAIST에 부임하기 전에는 대구경북과학기술원(DGIST)에서 영년직 부교수로 근무를 했었으며, 전공책임교수 및 학술본부장을 역임했다. 2006년에 KAIST에서 데이터베이스 분야로 전산학 박사학위를 취득했으며, 그 후 미국 일리노이 대학교 어배너-섐페인(UIUC)에서 그래프 데이터 마이닝을 연구하고, 미국 IBM 알마덴 연구소에서 상용 분산 인-메모리 OLAP 엔진을 개발한 바 있다. 김민수 교수의 연구분야는 데이터베이스, 데이터 마이닝, 기계학습, 바이오인포매틱스로서 해당 분야에서 선도연구센터(ERC), SW스타랩, 삼성전자 미래기술육성센터 등 여러 과제들을 연구책임자로 수행했거나 수행하고 있고, 분야 최고 국제학회(ACM SIGMOD, ACM KDD, IEEE ICDE) 및 최고 국제저널(Nucleic Acids Research)에 꾸준히 연구논문들을 발표해오고 있다.