대용량 그래프 데이터 저장하지 않고도 알고리즘 계산한다

KAIST "컴퓨터 한 대로 1조 개 간선 처리 가능…1만배 효율"

한국과학기술원(KAIST)은 김민수 교수 연구팀이 정보통신(IT) 분야에서 널리 쓰이는 그래프 데이터를 저장하지 않고도 알고리즘을 계산할 수 있는 기술을 개발했다고 23일 밝혔다.

'그래프 프로세싱 시뮬레이션'이라고 이름 붙인 이 기술은 데이터를 저장할 필요 없이 컴퓨터(PC) 한 대로 1조 개 간선의 거대 규모 그래프를 처리할 수 있다.

그래프 데이터는 웹 페이지 검색, 소셜네트워크서비스(SNS), 인공지능(AI), 가상화폐 등 광범위한 분야에서 사용되는 데이터로, 수많은 정점(vertex·꼭짓점)과 간선(edge·정점을 연결하는 선)들로 이뤄져 있다.

가령 구글 웹 검색 시스템은 웹페이지를 정점, 웹페이지 링크를 간선으로 해 그 알고리즘을 수행한 뒤 순위를 계산해 중요도가 높은 웹페이지부터 보여준다.

최근에는 그래프 데이터 규모 증가로 그래프 알고리즘이나 그래프 기반 애플리케이션을 개발하는데 드는 컴퓨터 자원과 시간도 급격히 늘고 있다.

연구팀은 그래프 데이터를 실제 디스크에 저장하지 않고도, 마치 저장된 것처럼 알고리즘을 계산할 수 있는 기술을 개발했다.

기존에는 그래프 알고리즘을 개발하기 위해 우선 합성 그래프를 생성해 저장한 뒤 다시 그래프 처리 엔진에서 메모리로 옮겨 알고리즘을 계산하는 방법을 써야 하기 때문에, 대규모 클러스터 장비를 사용해야 했다.

연구팀은 합성 그래프 모델에 따라 실시간으로 그래프를 생성, 그래프 처리 엔진이 마치 실제 그래프인 것처럼 인식해 알고리즘을 계산할 수 있도록 했다.

기존 방법으로 10억 개 간선 규모의 그래프를 계산하는 데 11대의 컴퓨터가 필요했다면, 이번 기술을 이용하면 1대의 컴퓨터에서 1조 개 간선 규모의 그래프를 계산할 수 있다.

컴퓨터 자원 대비 1만배 큰 규모의 데이터를 처리할 수 있으며, 알고리즘 계산 시간도 최대 43배 빠르다고 연구팀은 설명했다.

이번 연구 결과는 전날 그리스 차니아에서 온라인으로 열린 데이터베이스 분야 국제학술대회 'IEEE ICDE'에서 발표됐다.

/연합뉴스