단일 머신 그래프 처리 시스템에서의 하이브리드 그래프 정렬 기법

Abstract

최근 몇 년간 대규모의 소셜 네트워크와 웹 그래프에 대한 처리 수요가 나날이 증가하면서 데이터베이스 분야에서는 효과적인 그래 프 처리에 대한 많은 연구가 진행되었다. 큰 규모의 데이터를 처리 하기 위해 다수의 노드를 이용한 메모리 기반의 분산 그래프 처리 시스템들이 개발되었고 많은 관심을 얻었다. 그러나 분산 시스템을 구성하기 위한 비용 문제와 네트워크 바틀넥 문제, 분산 알고리즘 개발 및 구현에 대한 어려움 등으로 인해 단일 머신 기반의 그래프 엔진들이 주목을 얻기 시작했다. 단일 머신 그래프 처리 시스템들은 대규모 그래프를 처리하기 위 해 데이터를 디스크에 저장해두고 필요할 때마다 접근하는 out of core 방식으로 그래프를 처리한다. 그 결과, 메모리 계층 간 속도 차 이를 해결하기 위해 각각의 시스템들은 저마다의 독창적인 처리 기 법과 자료 구조로 효율적인 계산과 적은 I/O 비용으로 이러한 문제 를 해결했다. 최근에는 단일 머신 엔진의 단점을 극복하기 위해 그 래프의 구조적 특징을 이용한 그래프 정렬 기법이 연구되고 있다. 이 기법은 입력 그래프 데이터에 전 처리를 가하여 자주 접근되는 데이터들이 디스크 상에서 인접하게 저장되도록 하는 것으로써, 한 번의 전 처리 과정으로 그래프 엔진에 대한 변형 없이 수행 시간을 개선할 수 있다는 장점이 있다. 본 논문은 그래프 엔진의 특징과 데이터의 구조적 특성을 분석하 고 기존 그래프 정렬 기법들을 검토한 후, 이 기법들의 단점을 보완 하기 위해 허브 정점의 특성, 그리고 그래프 데이터 및 알고리즘의 특징을 모두 고려한 하이브리드 그래프 정렬 기법인 Horder를 제안 한다. 다양한 데이터와 알고리즘을 활용한 실험을 통해 Horder가 성 능 향상과 I/O 비용 절감 측면에서 기존 그래프 정렬 기법들을 유 의미하게 개선하였음을 확인하였다.

For recent years as the demand for effectively processing social network data and web graphs increases, there are many studies in this area. To process the huge real world graphs, various distributed graph processing frameworks which utilize multiple machines have been proposed. However, because of cost issues about organizing the distributed environment, network bottleneck issues, and the difficulty of implementing the distributed algorithms, single machine based graph processing systems have been considered an attractive research topic. As single machine based graph engines store the data in the disk storage and access them, the speed gap between the memory hierarchy has been considered important issues. Recently, to deal with this problem, graph ordering technique which utilizes the characteristics of graph topology has been studied. This technique makes frequently accessed data to be stored adjacently by pre-processing the input graph data. In this paper we analyze the characteristics of single machine graph engine and topological properties of graph data and compare the various graph ordering techniques. And, we propose the hybrid graph ordering technique, Horder, which considers both properties of hub nodes and the graph topology. Our evaluation shows that Horder provides the improved performance and I/O cost efficiency compared to other ordering techniques.