Incremental Processing Scheme for Graph Streams Considering Data Reuse

데이터 재사용을 고려한 그래프 스트림의 점진적 처리 기법

Incremental Processing Scheme for Graph Streams Considering Data Reuse

조중권^*, 한진수^**, 김민수^**, 최도진^**, 복경수^**, 유재수^**

충북대학교 빅데이터학과^*, 충북대학교 정보통신학과^**

Jungkweon Cho([email protected])^*, Jinsu Han([email protected])^**, Minsoo Kim([email protected])^**, Dojin Choi([email protected])^**,

Kyoungsoo Bok([email protected])^**, Jaesoo Yoo([email protected])^**

요약

최근 소셜 미디어, IoT 등에 대한 활용이 증가됨에 따라 대용량의 그래프 스트림이 생성되고 있으며 그래 프 스트림을 실시간으로 처리하기 위한 많은 연구들이 진행되고 있다. 본 논문에서는 그래프가 지속적으로 변경될 때 이전 결과 데이터를 재사용하는 점진적인 그래프 스트림 처리 기법을 제안한다. 또한, 점진적 처리와 정적인 처리를 선택적으로 수행하기 위한 비용 모델을 제안한다. 제안하는 비용 모델은 실제 처리된 이력을 바탕으로 재계산 영역의 탐색 비용 및 처리 비용의 예측 값을 계산하여 점진적 처리가 정적인 처리 보다 이득인 경우 점진적 처리를 수행한다. 제안하는 점진적 처리는 그래프 갱신이 발생하면 변경되는 부분 만을 처리하여 효율성을 증가시킨다. 또한, 변경되는 부분의 이전 결과 데이터만을 수집하여 점진적인 처리 를 수행함으로써 디스크 I/O 비용을 감소시킨다. 다양한 성능평가를 통해 제안하는 기법이 기존 기법에 비 해 성능이 우수함을 보인다.

■ 중심어 :∣스트림 처리∣그래프 처리∣점진적 처리∣데이터 재사용∣비용 모델∣

Abstract

Recently, as the use of social media and IoT has increased, large graph streams has been generating and studies on real-time processing for them have been actively carrying out. In this paper we propose a incremental graph stream processing scheme that reuses previous result data when the graph changes continuously. We also propose a cost model to selectively perform incremental processing and static processing. The proposed cost model computes the predicted value of the detection cost and the processing cost of the recalculation area based on the actually processed history and performs the incremental processing when the incremental processing is more profit than the static processing. The proposed incremental processing increases the efficiency by processing only the part that changes when the graph update occurs. Also, by collecting only the previous result data of the changed part and performing the incremental processing, the disk I/O costs are reduced. It is shown through various performance evaluations that the proposed scheme outperforms the existing schemes.

■ keyword :∣Stream Processing∣Graph Processing∣Incremental Processing∣Data Reuse∣Cost Model∣

* 이 논문은 과학기술정보통신부 및 정보통신기술진흥센터의 대학ICT연구센터육성지원사업(IITP-2017-2013-0-00881), 2017년도 정부(과학기술정보통신부)의 재원으로 한국연구재단-차세대정보・컴퓨팅기술개발사업(No. NRF-2017M3C4A 7069432), 2016년도 정부(과학기술정보통신부)의 재원으로 한국연구재단의 지원(No. 2016R1A2B3007527) 및 2015년도 충 북대학교 학술연구지원사업의 교내연구비 지원에 의하여 연구되었음

접수일자 : 2017년 10월 17일 수정일자 : 2017년 10월 31일

심사완료일 : 2017년 10월 31일

교신저자 : 유재수, e-mail : [email protected]

I. 서 론

소셜 네트워크에서 사용자간의 관계 및 정보의 흐름 을 표현하거나 IoT(Internet of Things)에서 각종 사물 들 사이에 상호 작용을 표현하기 위해 그래프 데이터가 활용되고 있다. 최근 다양한 분야에서 그래프 데이터를 분석하여 중요한 비즈니스 가치를 창출하기 위해 연구 가 진행되고 있다[1-4]. 예를 들어, IoT나 재난안전 분 야에서 센서 간 상호관계를 그래프 스트림으로 나타내 고 실시간으로 분석하여 위험 발생을 감지하고 예측한 다. 소셜 네트워크 분야에서는 사용자간의 상호작용을 실시간으로 트렌드 분석하여 광고주의 전략에 맞는 정 확한 광고를 제공할 수 있다.

그래프는 G = (V, E)로 나타내며, V는 정점(vertex) 집합을 나타내고, E는 간선(edge) 집합을 나타낸다. 각 정점에는 정점의 특징이나 정보가 포함될 수 있으며, 이와 유사하게 간선에는 간선의 정보와 정점간의 관계 같은 정보가 있을 수 있다. 소셜 네트워크에서 신규 가 입한 사용자가 기존 사용자와 팔로우 관계가 형성되었 을 경우 정점과 간선이 새롭게 삽입되는 것처럼 그래프 스트림은 정점의 삽입과 삭제, 간선의 삽입과 삭제가 그래프의 시간에 따라 계속적으로 발생하는 그래프 이 벤트의 흐름이다.

소셜 네트워크의 대표적인 예로 페이스북은 추천이 나 댓글과 같은 정보가 분당 약 330만 건 정도 생성되 며, 트위터의 경우 분당 약 35만 건 정도의 트윗이 생성 된다. 또한, PageRank 알고리즘으로 검색엔진을 구축 한 구글은 분당 약 410만 건의 질의를 처리한다[5]. 이 러한 대용량 그래프 처리를 위한 분산 처리 기법에 대 한 연구들이 진행되고 있다[6-9]. 그래프 병렬 처리 시 스템은 거대한 양의 데이터를 분산 저장하고 병렬 처리 하여 빠르게 분석하기 위해 개발되었다. 가장 대표적인 연구로는 PowerGraph[8]이 있다. PowerGraph는 그래 프 분산 데이터 처리 시스템으로 단일 서버의 한계를 극복하기 위해 여러 서버에 데이터를 분산저장하고 병 렬 처리한다. 정점 기반의 절단 기법(vertex-cut)과 GAS(Gather-Apply- Scatter) 모델을 도입하여 저장 및 통신 비용을 크게 절감한다. 하지만 대부분의 그래

프 데이터는 끊임없이 변화하고 점차 증가하지만 그래 프 병렬 처리 시스템의 대다수는 정적인 환경에서 계산 을 지원한다. 그래프 갱신에 의해 그래프가 변경되면 정적인 처리 기법은 변하지 않은 영역까지 전체를 계산 하기 때문에 자주 변경되는 그래프에서 불필요한 중복 처리를 하고 매 수행 시 누적되어 더욱 악화된다. 정적 처리의 불필요한 중복 계산 문제로 인해 실시간 분석 결과를 제공하기 어려운 문제점이 발생하며 이를 해결 하기 위해 변경되는 부분만을 처리하는 점진적 처리 기 법의 도입이 필요하다.

점진적인 처리 기법은 지속적인 그래프 갱신을 처리 하기 위해 그래프에 대한 변경 사항을 수집하여 변경된 부분만을 처리하고 기존 결과와 병합함으로서 기존 그 래프 병렬 처리 기법의 중복 계산 문제점을 해결한다.

그래프 분석 작업의 상당 부분은 이미 이전 작업에서 완료되었으므로 작은 변화에서 전체를 처리하는 기법 보다 효율적인 성능을 나타낼 수 있다. Gupta et al.[10]

은 그래프의 변경되는 부분만을 재계산하는 점진적인 처리 기법을 이용하여 불필요한 중복 계산을 제거한다.

하지만, 재계산이 필요한 정점에 많은 정점이 연결된 경우 재계산되기 위해 수많은 정점을 다시 탐색하여 연 결된 정점의 수만큼 디스크 I/O 비용이 생기는 문제점 이 있다.

본 논문에서는 데이터 재사용을 통한 점진적인 그래 프 스트림 처리 기법을 제안한다. 제안하는 기법은 그 래프 스트림 환경에서 실시간 분석 결과를 제공해주기 위해 PowerGraph[8]의 GAS 모델을 점진적으로 처리 되도록 변형한다. 즉 제안하는 기법은 그래프의 변경되 는 부분만을 처리하고 이전 결과 데이터를 재사용함으 로써 데이터를 탐색하는 비용을 감소시킨다. 한편 그래 프 스트림에 의해 변경되는 영역이 큰 경우 탐색 비용 및 처리 비용이 증가할 수 있다. 그래프 데이터 전체를 정적으로 처리하는 경우에는 처리 비용만 발생하지만 점진적 처리에서는 그래프 갱신에 의해 영향을 받아 재 계산되어야 하는 부분을 탐색하는 비용이 포함된다. 따 라서 변경되는 영역이 큰 경우 재계산 영역을 탐색하고 처리하는 점진적 처리 기법보다 그래프 전체를 일괄적 으로 처리하는 기법이 더 우수한 성능을 보일 수 있다.

그래프 변화량에 따라 점진적인 처리와 정적인 처리를 선택적으로 수행하기 위하여 비용 모델을 제안한다. 비 용 모델은 실제 처리된 이력을 바탕으로 탐색 비용과 처리 비용의 예측값을 계산하고 점진적 처리가 이득인 경우 점진적 처리를 수행한다.

본 논문의 구성은 다음과 같다. 제 II장에서는 관련 연구를 설명한다. 제 III장에서는 제안하는 점진적 그래 프 스트림 처리 기법을 기술한다. 제 IV장에서는 성능 평가 결과를 기술하고 마지막으로 제 V장에서는 본 논 문의 결론과 향후 연구 방향을 제시한다.

II. 관련 연구

그래프 데이터에 대한 처리는 정적 처리와 점진적 처 리에 대한 연구가 있다. 정적 처리 기법은 전체 데이터 를 일괄적으로 처리하는 방식으로 대용량의 그래프 데 이터를 빠르게 처리하는 것에 초점을 맞추고 있으며, 점진적 처리 기법은 변경되는 부분만을 계산한 뒤 기존 결과와 병합하는 방식으로 연산량을 감소시키는 것에 초점을 맞추고 있다.

Pregel[6]은 구글에서 대용량 그래프 병렬처리를 위 해 구현된 시스템이며 BSP(Bulk Synchronous Parallel)모델을 사용한다. 프로그램이 수행될 때 슈퍼 스텝의 단위로 동기식처리를 지원한다. 슈퍼스텝 내에 서 이전 슈퍼스텝의 메시지를 끝내기 전까지 배리어가 적용되며, 모든 메시지가 처리된 이후 다음 슈퍼스텝으 로 진입한다.

GraphLab[7]은 분산 공유 메모리 환경에서 비동기식 처리를 지원한다. 프로그램은 인접한 정점 값을 읽어서 알고리즘을 수행하고 그 결과를 Ghosting을 사용하여 분산된 서버에 공유메모리를 통해 액세스가 가능하도 록 한다.

GraphX[9]는 널리 사용되는 대용량 데이터 처리엔진 인 Apache Spark위에 구축된 분산 인-메모리 그래프 처리 시스템이다. GraphX는 정점과 간선을 두 개의 테 이블로 나누고 RDD(Resilient Distributed Datasets)로 생성하여 각 서버에 정점절단 방식으로 파티셔닝 한다.

그리고 각 서버에서는 구현된 그래프 알고리즘을 수행

한다.

Bhatotia et al.[11]이 제안한 점진적 처리 기법은 기 존의 맵리듀스 모델을 계속 유지하면서 그래프의 작은 변화만을 처리하기 위해 계산 단위를 더 작은 단위로 나눈다. 그 후 변경전파 알고리즘에 의해 그래프의 모 든 연산을 추적하고 변경된 부분만 재 수행한 뒤 하위 로 전파하여 변경되지 않은 기존 결과와 병합한다.

iGraph[12]의 경우 그래프 스트림 데이터를 여러 배 치단위로 나누어 처리한 뒤 그래프 갱신이 발생하면 그 래프 갱신에 의해 영향을 받는 배치들을 탐색 및 재계 산하여 기존 결과와 병합하는 전략을 사용한다.

Gupta et al.[10]이 제안한 점진적 처리 기법은 그래 프 갱신에 의해 영향을 받는 영역과 영향을 받지 않는 영역으로 나누어 처리하고 결과를 병합한다. 그래프의 재계산 영역에서 점진적으로 처리하고 변경 내용을 기 반으로 결과를 갱신하여 중복 계산을 회피한다.

그래프 데이터의 처리 시간을 감소시키기 위해 정적 인 처리 기법과 점진적 처리 기법이 제안되었지만 정적 처리 기법[6-9]은 전체 그래프 데이터를 일괄적으로 처 리하기 때문에 불필요한 중복 계산이 발생하여 처리의 실시간성을 보장할 수 없으며 기존에 제안된 Bhatotia et al.[11]의 점진적 처리 기법은 계산 단위를 나눌 때 너무 작은 단위로 분할되면 복잡도의 문제로 높은 처리 비용과 네트워크 오버헤드를 초래한다. iGraph[12]의 경우 그래프 갱신이 발생할 때 배치에 포함되지만 변하 지 않은 부분도 재계산하여 부분적인 중복 계산이 발생 된다. 또한, 여러 배치에서 변경되는 경우 동시에 많은 디스크 I/O 비용 및 처리 비용이 발생한다. Gupta et al.[10]이 제안한 점진적인 처리 기법의 문제점은 재계 산될 정점에 많은 연결이 있는 경우 그 수만큼 연결된 정점을 다시 탐색하여 그만큼의 탐색 비용 및 디스크 I/O 비용이 발생한다. 그래프 스트림 환경에서 실시간 으로 분석 결과를 제공해주기 위해 점진적 처리 기법을 도입하여 정적 처리 기법의 중복계산 문제를 회피하고 기존의 점진적 처리 기법의 부분적인 중복계산과 탐색 비용 및 디스크 I/O 비용을 감소시키는 차별화된 효율 적인 그래프 처리 기법이 필요하다.

그림 1. 제안하는 기법의 처리 구조

III. 제안하는 점진적 그래프 스트림 처리 기법

1. 시스템 구조

각종 센서 또는 사용자들이 실시간으로 생성하는 그 래프 스트림 환경에서 그래프는 점차 증가하고 동적으 로 변화한다. 본 논문에서는 그래프 데이터의 실시간 분석 결과를 제공하기 위해 효율적인 점진적 처리 기법 을 제안한다. 새로운 그래프 스트림이 발생했을 때 전 체를 계산하는 것 보다 변경된 일부분만을 계산하는 것 이 더욱 효율적일 수 있다.

기존 정적 처리 기법의 문제점인 중복 계산을 회피하 기 위해 그래프 갱신 시 영향을 받는 부분만 처리하고 연결된 정점들을 다시 탐색하는 비용과 디스크 I/O 비 용을 감소시키기 위하여 이전 결과 데이터를 재사용하 는 기법을 제안한다. 또한, 그래프 변화에 따라 재계산 영역에 대한 탐색 및 처리 비용이 증가하기 때문에 정 적 처리와 점진적 처리를 선택적으로 수행하는 비용 모 델을 제안한다. 비용 모델은 과거 이력을 바탕으로 각 처리 방법의 예측값을 계산하여 점진적 처리의 이득을 판별한다. 점진적 처리가 이득인 경우 그래프 갱신에 의해 영향을 받는 영역을 탐색하고 그 영역에 대해 점 진적인 처리를 수행하여 결과를 생성한다.

[그림 1]은 제안하는 기법의 처리 구조를 나타낸다.

각종 센서나 사용자들로부터 생성되는 그래프 스트림 이 발생하면 변화 탐지는 실제 처리된 이력을 바탕으로 통계치를 계산한다. 비용 모델은 각 처리 기법의 예측 값을 계산하여 점진적 처리 여부를 판별한다. 점진적

처리가 이득인 경우 제안하는 기법인 iGAS (Incremental Gather-Apply-Scatter)를 수행하여 그래 프 갱신에 의해 영향을 받은 영역을 점진적으로 처리하 고 점진적 처리가 이득을 보지 못하는 경우 GAS에서 전체 데이터를 정적으로 처리한다.

2. 변화 탐지

그래프 갱신이 발생하면 전체 그래프에서 얼마만큼 의 변화가 일어나는지 파악할 수 있어야 점진적 처리 시 예상되는 탐색 비용과 처리 비용을 계산할 수 있다.

변화 탐지는 비용 모델을 계산하기 위해 필요한 인자를 수집 및 계산하여 비용 모델로 전달하는 단계이다. 그 래프의 변화량과 각 처리 비용을 파악하기 위하여 그래 프 갱신에 의해 영향을 받아 평균적으로 재계산 되어야 하는 개수의 과거 통계치(^), 탐색 비용의 과거 통계치 (^), 처리 비용의 과거 통계치(^)가 수식(1, 2, 3)에 의 해 계산되어 비용 모델로 전달된다.

  

  



_

_



(1)

  

  



_

_



(2)

  

  



_

_



(3)

평균적으로 재계산 되어야하는 개수의 과거 통계치 (^)는 하나의 데이터가 입력되었을 때 전체 그래프에서 영향을 받아 재계산되어야하는 정점들의 평균적인 개 수이며, 하나의 정점에 많은 연결이 있는 정점의 경우

가 증가하면 비례적으로 ^의 값도 증가된다. [그림 1]

의 그래프 스트림에서 업데이트 개수(^)와 iGAS에서 실제 처리된 이력을 바탕으로 그래프 갱신에 의해 영향 을 받는 정점의 개수(^)를 수집하여 계산된다. 수식(1, 2, 3)에 공통적으로 들어가는 ^는 그래프 갱신 발생 횟 수를 의미한다.

탐색 비용의 과거 통계치()는 하나의 정점을 탐색하 는데 발생하는 비용을 의미하며, 변화량이 큰 경우 탐 색 비용이 증가하며 탐색 비용의 과거 통계치 또한 비 례적으로 증가한다. 그래프 갱신에 의해 영향을 받는 정점의 개수()와 실제 재계산 영역 탐색 비용()을 수 집하여 계산된다. 처리 비용의 과거 통계치(^)는 하나 의 정점을 처리하는데 발생하는 비용을 의미하며, 시스 템 부하에 따라 값이 유동적으로 변할 수 있다. 그래프 갱신에 의해 영향을 받는 정점의 개수()와 실제 처리 비용(^)을 수집하여 계산된다. 예를 들어, 그래프 갱신 에 의한 입력과 영향을 받는 데이터가 각 ^ ,

_ , _ , _ , _ , _  세 번 발생했다 고 가정한다. 이때 ^는 수식 (1)에 의하여

     가 되며 1개의 입력이 발생할 때 평균적으로 4개를 처리해야한다. 그래프 갱신에 의 해 영향을 받는 개수(^)는 앞선 예제와 동일하고 실제 탐색 비용과 처리 비용이 각 ^ , ^ ,

_ , _ , _ , _  가정한다. 이때 탐색 비용과 처리 비용의 과거 통계치는 수식 (2), (3)에 의하여      가 되며 하 나의 정점을 탐색하거나 처리하는데 각 0.002의 비용이 발생하게 되는 것을 나타낸다.

3. 비용 모델

변경되는 부분만으로 점진적인 처리를 한다면 처리 량과 디스크 I/O 비용을 감소시킬 수 있지만 그래프 갱 신에 의해 그래프의 대부분을 재계산해야 하는 경우 점 진적 처리는 재계산 영역을 탐색하는 비용이 포함되기

때문에 정적 처리보다 이점을 얻을 수 없다. 따라서 변 화량이 많은 경우에는 재계산 영역을 탐색하지 않고 일 괄적으로 처리하는 정적인 처리 기법이 이득일 것이며 변화량이 작은 경우에는 영향을 받아 재계산해야하는 영역만을 탐색한 후 처리하는 점진적 처리 기법이 이득 일 것으로 예상된다.

제안하는 비용 모델은 실제 처리된 이력을 바탕으로 그래프 갱신에 의해 앞으로 발생할 정적 처리 비용과 점진적 처리 비용의 예측값을 계산하고 점진적 처리 기 법이 이득인 경우 선택적으로 수행한다. 비용 모델은 예상 정적 처리 비용과 예상 점진적 처리 비용의 차로 수식(4)와 같이 나타낸다.

    (4)

예상 정적 처리 비용은 전체 그래프 데이터의 개수와 처리 비용의 과거 통계치의 곱으로 계산된다. 예상 점 진적 처리 비용은 재계산 영역을 탐색하는 비용 (detection cost)과 재계산 영역을 처리하는 비용 (processing cost)이 모두 반영해야 한다.

   ×  (5)

      (6)

예상 점진적 처리 비용에서 고려되는 탐색 비용(7)과 처리 비용(8)은 재계산할 그래프 영역에 있는 데이터의 개수가 많을수록 증가한다.

  × ×  (7)

  ×  ×  (8)

탐색 비용과 처리 비용을 고려한 예상 점진적 처리 비용은 최종적으로 수식 (9)와 같이 정리된다.

    × ×  (9)

전체 그래프의 데이터(τ)가 40개이고   일 때 예상 정적 처리 비용은 수식(5)에 의하여 0.08이 되고

  , ^{  }, ^{  }, ^{  }일 때 예상 점진적 처 리 비용은 0.048이 되어 비용 모델의 결과로서 점진적 처리의 이득을 판단하여 iGAS를 수행한다.

4. iGAS 모델

본 논문에서는 실시간으로 분석 결과를 제공하기 위 해 기존의 PowerGraph[8]에서 제안된 GAS모델을 점 진적으로 처리되도록 변형한 iGAS 모델을 제안한다.

iGAS 모델은 변경되는 부분만을 처리함으로서 중복 계 산을 하지 않는다. 또한, 이전에 생성된 결과 데이터를 재사용함으로서 데이터를 다시 탐색하는 비용을 감소 시킨다.

PowerGraph[8]은 정적 처리 기법으로 데이터를 처리 하기 때문에 [그림 2]의 모든 영역(a)을 계산하여 영향 을 받지 않는 부분까지 재계산 하게 된다. 기존의 제안 된 점진적인 처리 기법[10]은 [그림 2]의 영역(b)에서 정점 B가 삽입되는 경우 직접적으로 영향을 받는 정점 A와 그로 인해 영향을 받는 정점 C, D, E는 재계산 영 역에 포함된다. 하지만 정점 F, G, H, I, J 또한 정점 A 가 계산되기 위해 재계산 영역에 포함되어야 한다. 기 존의 제안된 점진적인 처리 기법[10]은 영역(b)와 같이 정점 A가 계산 되어야 할 때 많은 수의 연결이 있는 경 우 정점 A에 연결된 정점 수만큼 다시 데이터를 다시 탐색하여 계산해야 하는 문제점이 발생한다. 본 논문에 서는 기존 점진적 처리 기법의 문제점을 개선하고자 GAS 모델에 이전에 생성된 결과 데이터를 재사용하여 다시 탐색하는 비용을 줄일 수 있도록 하였다. 이를 통 해 그래프 갱신에 의해 영향을 받는 영역(c)만을 처리 하여 데이터 처리 시간을 감소시킨다.

그림 2. 재계산 영역

GAS모델은 그래프를 처리하기 위한 계산 모델로서 Gather-Apply-Scatter 세 단계로 구분되고, Gather단 계는 분산 환경에서 Pregel과 같이 서버의 처리되는 정 보를 중간 취합하여 메시지를 받는 방식을 사용하며 연 결된 정점의 정보를 수집한다. Apply는 수집된 정보를 계산하고, GraphLab의 Ghosting 방식을 적용하여 계산 된 결과를 공유메모리를 통해 서버 간 공유한다.

Scatter단계에서는 계산된 결과를 주변 정점으로 전파 하는 과정이며, GAS 모델은 세 가지 단계를 반복적으 로 수행한다.

[그림 3]은 GAS 모델을 나타낸다. GAS모델은 기존 그래프 병렬처리 시스템들 중 가장 빠른 분석결과를 제 공해주며, 대부분의 그래프 분석 알고리즘은 해당 정점 의 값이 계산되기 위하여 주변 정점들의 정보를 반복적 으로 요청하는 형태를 갖고 있기 때문에 GAS모델은 그래프 분석 알고리즘에서 성능과 구조적면에서 효율 적이다.

Algorithm 1: GAS Vertex-Program

Input: Center vertex  foreach neighbor  is empty do

_ ← sum(_, gather(_, _{  }, _)) end

_^ ← apply(_, _)

foreach neighbor  scatter_nbrs() do (_{  }, ∆) ← scatter(_, _{  }, _) end

그림 3. GAS Vertex-Program

본 논문에서는 기존의 GAS모델을 점진적으로 변형 하여 변경되는 영역만을 재계산한다. [그림 4]는 iGAS 모델을 나타낸다. 제안하는 iGAS 모델에서 Gather단계 는 인접한 정점들 중 변경되는 정점의 이전 값과 현재 값을 수집하고 캐시된다. 캐시 정책에 의해 이전 값이 캐시에 존재하는 경우 캐시에서 수집하고 캐시에 존재 하지 않는 경우 디스크에서 읽어온 뒤 캐시에 저장한 다. 수집 단계가 완료된 후 Apply단계에서는 변경되는 정점의 데이터를 이용하여 정점의 새로운 값을 계산한 다. PageRank 알고리즘의 경우 역함수를 취해 남은 인

접 정점들로부터 수집된 값에서 변경된 부분의 정점 값 만을 수정하여 새로운 값을 계산한다. Scatter단계는 인 접한 정점으로 Apply단계에서는 해당 정점이 변경되었 음을 기록하고 계산된 새로운 값을 전파한다.

Algorithm 2: iGAS Vertex-Program

if cached reuse data is empty then

foreach neighbor changed data _ in gather_nbrs() do if (_{} ) then

_←fix(_,gather(_{_},_{ _},_{},_)) end

end end

_^ ← apply(_, _)

foreach neighbor  scatter_nbrs() do delta = (_{  }, ∆)

if delta is not converged then _{ } 

delta ← scatter(_) end

end

그림 4. iGAS Vertex-Program

제안하는 기법은 변경되는 부분의 이전 결과 데이터 만 수집하여 연결되어있는 전체 데이터를 수집할 필요 가 없으므로 기존에 제안된 점진적인 처리 기법[10]보 다 디스크 I/O 비용을 감소시킬 수 있다. [그림 5]는 iGAS 수행시 수집되는 정점을 나타낸다. 정점 ^이 그 래프 갱신에 의해 변경되었다면, 계산되는 해당 정점  는 인접한 정점들 중 변경되는 정점 ^의 이전 결과 데 이터와 현재 결과 데이터를 수집하고 적용단계에서 정 점 의 새로운 값을 계산한다. 새로 계산된 정점 의 값을 인접한 정점 에게 전파하고 정점 는 정점  의 값만을 수집하여 새로운 값을 계산한다. 제안하는 점진적 처리 기법을 통해 그래프 스트림 처리 시 데이 터의 중복 처리가 감소하고 연결된 정점의 재탐색 비용 을 감소시켜 데이터의 처리 속도가 향상된다.

그림 5. 점진적 처리 시 수집되는 정점

5. 캐시

캐시에는 변경되는 데이터의 주변 데이터가 프리패 치되어 계산시 디스크 I/O 비용을 줄일 수 있다. 또한, 한번 읽어온 이전 결과 데이터와 처리된 결과 데이터를 캐시에 저장하고 사용한다. 데이터를 캐시에 저장하고 사용함으로써 반복적인 계산을 효율적으로 가속화한 다. 이를 통해 새로운 데이터와 이전 결과 데이터를 결 합하여 새로운 결과를 만들 수 있으며 전체적인 데이터 처리 효율을 높인다.

캐시에 데이터가 누적되다가 가득 차게 되면 더 이상 데이터를 저장할 수 없기 때문에 효율적인 메모리 관리 가 필요하다. 일반적으로 실시간 그래프 분석에 사용되 는 데이터는 최신의 데이터를 중심으로 이루어지므로 LRU 기법을 사용하여 메모리 관리를 수행한다. LRU 기법은 사용한지 가장 오래된 데이터를 퇴출시키는 알 고리즘으로 메모리 공간이 부족한 경우 최저 사용 빈도 를 갖는 데이터를 디스크로 저장하는 기법이다.

IV. 성능 평가

제안하는 기법의 우수성을 입증하기 위해 정적 처리 기법으로 전체를 계산하는 기법과 변경된 부분만을 재 계산 하는 점진적 처리 기법의 성능 비교를 수행한다.

성능 평가 대상인 정적 처리 기법의 PowerGraph[8]는 그래프 병렬처리 시스템으로 그래프 분석 알고리즘에 서 성능과 GAS의 구조적면에서 효율적이기 때문에 성 능 평가 대상으로 선택되었고 점진적 처리 기법에서는 Gupta et al.[10]이 제안한 기존 기법과 본 논문에서 제 안하는 iGAS, iGAS와 비용 모델을 같이 사용한 기법의 성능 평가를 수행한다. Gupta et al.[10]이 제안한 기존

기법은 다른 기존 점진적 처리 기법[11][12]과 달리 부 분적인 중복 계산을 하지 않기 때문에 성능 평가 대상 으로 선택하였다. 성능 평가의 환경은 Intel(R) Core i5 CPU 프로세서, 32G 메모리, 1 TB 디스크로 구성된다.

[표 1]은 실험 데이터의 특성을 나타낸다. 실험 데이터 는 실제 데이터[13]과 임의적으로 생성한 데이터 두 종 류를 사용하였으며 실제 데이터에서는 주변에 영향을 주는 정점의 비율을 파악하기 어렵기 때문에 동일한 그 래프를 10개 복제한 데이터를 사용하여 그래프 변화량 에 따른 수행 시간을 비교한다. 실제 데이터는 그래프 알고리즘의 연산 속도를 비교하기 위해 라이브저널과 트위터 데이터를 사용한다.

구분 정점 간선

라이브저널 1,070,383 개 3,372,093 개

트위터 81,543 개 2,419,738 개

생성 데이터 106,018 개 1,105,922 개

표 1. 실험 데이터의 특성

[그림 6]은 비용 모델의 타당성을 입증하기 위해 정 적 처리 기법과 비교하여 iGAS, iGAS와 비용 모델을 같이 사용한 기법의 PageRank 알고리즘의 수행시간을 나타낸다. [그림 6]의 (a)는 변화량에 따른 정적 처리 기 법과 비용 모델을 적용하지 않은 점진적 처리 기법의 수행시간을 비교한 결과를 나타낸다. [그림 6]의 성능 평가 (a)와 같이 변화량이 60% 이상인 경우 iGAS는 정 적인 처리 기법보다 수행시간이 더 오래 걸리는 것을 확인할 수 있다. 그래프 갱신에 의해 그래프의 대부분 을 재계산해야 하는 경우 iGAS는 재계산 영역을 탐색 하는 비용이 포함되기 때문에 정적 처리보다 이점을 얻 을 수 없다. [그림 6]의 성능 평가 (b)는 iGAS에 비용 모델을 적용하여 그래프 변화에 따라 선택적인 처리가 수행되도록 성능 평가를 진행하였다. 비용 모델에 따라 점진적인 처리가 비효율적인 경우 정적 처리 기법을 사 용하여 변경된 부분을 탐색하지 않고 전체 데이터를 처 리한다. 변화량 10%에서 100%까지 각 기법의 수행시 간을 합산하여 비교해보면 정적 처리 기법 대비 iGAS 만 사용하였을 경우에는 약 95%로 정적 처리 기법보다 오래 걸렸고 iGAS와 비용 모델을 같이 사용한 경우에

는 약 136%로 비용 모델을 사용한 것이 iGAS만 사용 하였을 때보다 이점이 있음을 확인할 수 있다.

(a) 정적 처리 기법과 점진적 처리 기법(only iGAS)의 수행시간

(b) 정적 처리 기법과 비용 모델을 적용한 점진적 처리 기법(iGAS+비용 모델)의 수행시간

그림 6. 변화량에 따른 수행시간 비교

[그림 7]은 기존 기법들[8][10]과 제안하는 iGAS, iGAS에 비용 모델을 도입한 기법의 성능을 비교하기 위해 PageRank 알고리즘을 각 데이터별로 10회 반복 하고 합산한 결과이다. 매 반복마다 그래프를 갱신하여 성능 평가를 수행하였다. 그래프 갱신이 발생하는 상황 에서 정적인 처리 기법[8]은 전체 데이터를 계산하여 중복된 결과를 재생성하기 때문에 효율을 얻을 수 없었 고, 기존의 점진적 처리 기법[10]은 그래프 갱신에 의해 영향을 받는 부분만을 계산하지만, 정점에 연결된 수만 큼 전체를 탐색하는 비용과 디스크 I/O 비용이 발생하 기 때문에 iGAS보다 상대적으로 오래 걸리는 것을 확 인할 수 있다. 기존 점진적 처리 기법 보다 iGAS는 평 균 약 150%, iGAS와 비용 모델을 같이 사용한 기법은 평균 약 203%정도 우수한 성능을 보였다. iGAS 기법만 을 적용하였을 때는 그래프의 대다수가 변경되는 상황

에서 처리 비용은 정적 처리와 비슷한 성능을 보이지 만, 변경된 만큼 탐색 비용이 발생하기 때문에 상황에 따라 정적 처리 기법보다 성능이 저하될 수 있다. 제안 하는 기법은 점진적인 처리와 비용 모델을 사용하여 우 수한 성능을 보여주는 것을 확인할 수 있다.

(a)Live Journal 수행시간

(b) Twitter 수행시간

그림 7. PageRank 수행시간

V. 결론 및 향후연구

본 논문에서는 데이터 재사용을 통한 그래프 스트림 의 점진적인 처리 기법을 제안하였다. 제안하는 기법은 하나의 정점에 여러 정점이 연결되어있는 경우 이전에 생성된 결과 데이터를 재사용하여 연결된 정점의 탐색 비용 및 디스크 I/O 비용을 감소시켰다. 또한, 비용 모 델을 제안하여 처리 비용의 예측값을 계산하고 변화량 에 따른 정적인 처리 기법과 점진적인 처리 기법을 선 택적으로 수행하여 iGAS만을 사용했을 때 보다 처리 속도를 향상시켰다. 그래프에서 변경되는 부분이 작은 경우 점진적으로 변경된 부분만을 처리하여 정적인 처

리 기법의 중복계산을 회피하기 때문에 효율적이며, 변 경되는 부분이 큰 경우 정적인 처리 기법을 수행하여 탐색 비용이 발생하지 않아 점진적 처리 기법보다 효율 적이다. 성능 평가를 통해 제안하는 기법의 데이터를 처리하는 속도가 기존 점진적 처리 기법에 비해 약 203% 향상된 것을 확인할 수 있었다. 또한, 정적 처리 기법과 제안하는 기법의 처리속도를 변화량에 따라 비 교함으로써 비용 모델의 타당성을 입증하였다. 제안하 는 기법은 소셜 네트워크나 IoT 등과 같은 분야에서 실 시간 그래프 분석 및 처리에 적용할 수 있으며 특히, 패 턴 변화 또는 이상 감지 파악에 활용될 수 있다. 그러나 제안하는 기법은 연결성이 높은 특정 정점에 변화가 발 생할 경우 재계산 영역을 판별하기 위한 비용이 증가될 수 있으며 제안하는 비용 모델에서 실제 처리된 이력을 바탕으로 탐색 비용을 계산하기 때문에 상황에 따라 오 차가 발생할 수 있다. 향후 연구로는 재계산 영역에 대 한 탐색 비용을 감소시키고 비용 모델의 정확도에 관한 성능 평가를 추가할 예정이다. 또한, 다양한 그래프 알 고리즘에서 제안하는 점진적인 처리 기법을 적용하여 성능 평가를 수행할 예정이다.

참 고 문 헌

[1] O. Salem, L. Yaning, and M. Ahmed, "Anomaly detection in medical wireless sensor networks,"

Computing Science and Engineering, Vol.7, No.4, pp.272-284, 2013.

[2] F. Elijorde, K. Sungho, and L. Jaewan, "A wind turbine fault detection approach based on cluster analysis and frequent pattern mining," KSII Transactions on Internet and Information Systems, Vol.8, No.2, pp.664-677, 2014.

[3] Y. A. Kim and G. W. Park, "Topic-Driven SocialRank: Personalized search result ranking by identifying similar, credible users in a social network," Knowledge-Based Systems, Vol.54, pp.230-242, 2013.

[4] 서복일, 김재인, 황부현, "스트림 데이터 환경에서 배치 가중치를 이용하여 사용자 특성을 반영한 빈발항목 집합 탐사," 한국콘텐츠학회논문지, 제 11권, 제1호, pp.56-64, 2011.

[5] https://carestruck.org/happens-internet-minute/

[6] G. Malewicz, H. M. Austern, J. A. Bik, J.

Dehnert, I. Horn, N. Leiser, and G. M.

Czajkowski, "Pregel: a system for large-scale graph processing," Proc. ACM SIGMOD International Conference on Management of data, pp.135-146, 2010.

[7] Y. Low, J. Gonzalez, A. Kyrola, D. Bickson, C.

Guestrin, and J. Hellerstein, "Distributed GraphLab: A Framework for Machine Learning in the Cloud," Proceedings of the VLDB Endowment, Vol.5, No.8, pp.716-727, 2012.

[8] J. Gonzalez, Y. Low, H. Gu, D. Bickson, and C.

Guestrin, "PowerGraph: Distributed graph- parallel computation on natural graphs," Proc.

USENIX Symposium on Operating Systems Design and Implementation, pp.17-30, 2012.

[9] R. S. Xin, J. Gonzalez, F. J. Michael, and S. Ion,

"Graphx: A resilient distributed graph system on spark," Proc. International Workshop on Graph Data Management Experiences and Systems, p.2, 2013.

[10] U. Gupta and L. Fegaras, "Distributed Incremental Graph Analysis," Proc. IEEE International Congress on Big Data, pp.75-82, 2016.

[11] B. Pramod, W. Alexander, A. E. Istemi, R.

Rodrigo, and A. A. Umut, "Large-scale incremental data processing with change propagation," Proc. USENIX Workshop on Hot Topics in Cloud Computing, 2011.

[12] J. Wuyang, L. Jianxin, Y. Weiren, and Z.

Richong, "iGraph: an incremental data processing system for dynamic graph,"

Frontiers of Computer Science, Vol.10, No.3, pp.462-476, 2016.

[13] https://snap.stanford.edu/data/

저 자 소 개

조 중 권(Jungkweon Cho) 준회원

▪2014년 2월 : 청주대학교 통계학 과(이학사)

▪2015년 4월 : ㈜리얼타임테크 연 구원

▪2016년 3월 ～ 현재 : 충북대학교 빅데이터 협동과정 석사과정 <관심분야> : 데이터베이스 시스템, 빅데이터, 그래프

스트림

한 진 수(Jinsu Han) 준회원

▪2016년 2월 : 충북대학교 정보통 신공학과(공학사)

▪2016년 3월 ～ 현재 : 충북대학교 정보통신공학과 석사과정

<관심분야> : 그래프 분산처리, 빅데이터

김 민 수(Minsoo Kim) 정회원

▪2013년 2월 : 충북대학교 정보통 신학부(공학사)

▪2014년 9월 : 매크로 임팩트 연구 원

▪2017년 2월 : 충북대학교 정보통 신공학과(공학석사)

▪2017년 3월 ～ 현재 : 충북대학교 정보통신공학과 박 사과정

<관심분야> : 빅데이터, RDF, 그래프, 고차원 인덱스

최 도 진(Dojin Choi) 정회원

▪2014년 2월 : 한국교통대학교 컴 퓨터공학과(공학사)

▪2016년 2월 : 한국교통대학교 컴 퓨터공학과(공학석사)

▪2016년 3월 ～ 현재 : 충북대학 교 정보통신공학과 박사과정 <관심분야> : 연속 질의 처리, 그래프 스트림

복 경 수(Kyoungsoo Bok) 종신회원

▪1998년 2월 : 충북대학교 수학과 (이학사)

▪2000년 2월 : 충북대학교 정보통 신공학과(공학석사)

▪2005년 8월 : 충북대학교 정보통 신공학과(공학박사)

▪2005년 3월 ～ 2008년 2월 : 한국과학기술원 정보전 자연구소 Postdoc

▪2008년 3월 ～ 2011년 2월 : 가인정보기술 연구소 연 구원

▪2011년 3월 ～ 현재 : 충북대학교 전자정보대학 정보 통신공학부 초빙부교수

<관심분야> : 데이터베이스 시스템, 이동 객체 데이터 베이스, 이동 P2P 네트워크, 소셜 네트워크 서비스, 빅데이터

유 재 수(Jaesoo Yoo) 종신회원

▪1989년 2월 : 전북대학교 컴퓨터 공학과(공학사)

▪1991년 2월 : 한국과학기술원 전 산학과(공학석사)

▪1995년 2월 : 한국과학기술원 전 산학과(공학박사)

▪1995년 2월 ～ 1996년 8월 : 목포대학교 전산통계학 과 전임강사

▪1996년 8월 ～ 현재 : 충북대학교 전자정보대학 정교수 <관심분야> : 데이터베이스 시스템, 멀티미디어 데이 터베이스, 센서 네트워크, 바이오 인포메틱스, 빅데 이터