대용량 그래프에서 프리겔 기반의 효율적인그래프 메디안 탐색 기법 (A Pregel Based Efficient Graph Median Discovery in A Massive Graph)

서지정보

· 발행기관 : 한국정보과학회
· 수록지 정보 : 데이타베이스연구 / 29권 / 3호 / 87 ~ 97페이지
· 저자명 : 박기성, 이영구, 윤영선, 김태연, 한용구

초록

최근 대용량 그래프 DB로부터 다양한 데이터 마이닝 기법을 활용하여 유용한 지식을 찾아내는 기술이 주목받고있다. 특히 그래프 메디안 기법은 색인, 분류, 군집화와 같은 고차원 분석의 고유한 특징으로 활용될 수 있는 중요한 기술이다. 기존의 인-메모리 환경에서 설계된 그래프 메디안 기법들은 대용량 그래프를 처리하지 못한다. 최근대용량 그래프를 효율적으로 분산 처리하기 위한 프리겔 프레임워크가 제안되었다. 그러나 그래프 메디안은 단일쌍의 최단경로를 버텍스 수만큼 반복 수행하기 때문에 프리겔 프레임워크에서도 비효율적이다. 본 논문에서는 그래프 메디안을 프리겔 프레임워크에서 효율적으로 분산 설계하는 방법을 제안한다. 제안하는 방법은 최단경로 합의하한 개념을 이용하여 불필요한 탐색 공간을 줄인다. 또한 컴바이너와 집계 연산을 효율적으로 설계하여 클러스터들 간의 통신 및 I/O 비용을 줄인다. 실험을 통하여 제안하는 기법이 기존의 그래프 메디안 기법보다 최대 40%까지 수행시간을 개선함을 보인다.

영어초록

Recently, mining informative knowledge from massive graph DBs has been popularly studied.
In particular, graph median is an important technique since it is utilized as fundamental operator for various data mining techniques such as indexing, classification, and clustering. An existing in-memory based graph median technique cannot be applied to massive graphs because massive graphs cannot be loaded into the memory. A Pregel framework has been proposed to process massive graphs efficiently. However, the graph median discovery is still inefficient on the Pregel framework since we need to performs a single-source shortest path algorithm iteratively as many as the number of vertices. In this paper, we propose an efficient graph median discovery technique on the Pregel framework. we reduce the search space by using lower bound of shortest distance summation. Moreover, we optimize the network and I/O cost by designing a combiner and an aggregator function efficiently. In experiments, we show that the proposed technique can reduce execution time by up to 40% compared with the naive approach.

참고자료

· 없음