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

조중권; 한진수; 김민수; 최도진; 복경수; 유재수

doi:10.5392/jkca.2018.18.01.465

문제 정의

각종 센서 또는 사용자들이 실시간으로 생성하는 그래프 스트림 환경에서 그래프는 점차 증가하고 동적으로 변화한다. 본 논문에서는 그래프 데이터의 실시간 분석 결과를 제공하기 위해 효율적인 점진적 처리 기법을 제안한다. 새로운 그래프 스트림이 발생했을 때 전체를 계산하는 것 보다 변경된 일부분만을 계산하는 것이 더욱 효율적일 수 있다.
기존의 제안된 점진적인 처리 기법[10]은 영역(b)와 같이 정점 A가 계산 되어야 할 때 많은 수의 연결이 있는 경우 정점 A에 연결된 정점 수만큼 다시 데이터를 다시 탐색하여 계산해야 하는 문제점이 발생한다. 본 논문에서는 기존 점진적 처리 기법의 문제점을 개선하고자 GAS 모델에 이전에 생성된 결과 데이터를 재사용하여 다시 탐색하는 비용을 줄일 수 있도록 하였다. 이를 통해 그래프 갱신에 의해 영향을 받는 영역(c)만을 처리하여 데이터 처리 시간을 감소시킨다.
본 논문에서는 기존의 GAS모델을 점진적으로 변형하여 변경되는 영역만을 재계산한다. [그림 4]는 iGAS모델을 나타낸다.
본 논문에서는 데이터 재사용을 통한 그래프 스트림의 점진적인 처리 기법을 제안하였다. 제안하는 기법은 하나의 정점에 여러 정점이 연결되어있는 경우 이전에 생성된 결과 데이터를 재사용하여 연결된 정점의 탐색 비용 및 디스크 I/O 비용을 감소시켰다.
본 논문에서는 데이터 재사용을 통한 점진적인 그래프 스트림 처리 기법을 제안한다. 제안하는 기법은 그래프 스트림 환경에서 실시간 분석 결과를 제공해주기 위해 PowerGraph[8]의 GAS 모델을 점진적으로 처리되도록 변형한다.
본 논문에서는 실시간으로 분석 결과를 제공하기 위해 기존의 PowerGraph[8]에서 제안된 GAS모델을 점진적으로 처리되도록 변형한 iGAS 모델을 제안한다. iGAS 모델은 변경되는 부분만을 처리함으로서 중복 계산을 하지 않는다.

가설 설정

그래프 갱신에 의해 영향을 받는 개수(σ)는 앞선 예제와 동일하고 실제 탐색 비용과 처리 비용이 각 1=0.02, 2=0.03, 3=0.04, δ1=0.02, δ2=0.03, δ3=0.04 가정한다.

제안 방법

성능 평가 대상인 정적 처리 기법의 PowerGraph[8]는 그래프 병렬처리 시스템으로 그래프 분석 알고리즘에서 성능과 GAS의 구조적면에서 효율적이기 때문에 성능 평가 대상으로 선택되었고 점진적 처리 기법에서는 Gupta et al.[10]이 제안한 기존 기법과 본 논문에서 제안하는 iGAS, iGAS와 비용 모델을 같이 사용한 기법의 성능 평가를 수행한다. Gupta et al.
[11]이 제안한 점진적 처리 기법은 기존의 맵리듀스 모델을 계속 유지하면서 그래프의 작은 변화만을 처리하기 위해 계산 단위를 더 작은 단위로 나눈다. 그 후 변경전파 알고리즘에 의해 그래프의 모든 연산을 추적하고 변경된 부분만 재 수행한 뒤 하위로 전파하여 변경되지 않은 기존 결과와 병합한다.
그래프 변화량에 따라 점진적인 처리와 정적인 처리를 선택적으로 수행하기 위하여 비용 모델을 제안한다. 비용 모델은 실제 처리된 이력을 바탕으로 탐색 비용과 처리 비용의 예측값을 계산하고 점진적 처리가 이득인 경우 점진적 처리를 수행한다.
GraphX는 정점과 간선을 두 개의 테이블로 나누고 RDD(Resilient Distributed Datasets)로 생성하여 각 서버에 정점절단 방식으로 파티셔닝 한다. 그리고 각 서버에서는 구현된 그래프 알고리즘을 수행한다.
기존 정적 처리 기법의 문제점인 중복 계산을 회피하기 위해 그래프 갱신 시 영향을 받는 부분만 처리하고 연결된 정점들을 다시 탐색하는 비용과 디스크 I/O 비용을 감소시키기 위하여 이전 결과 데이터를 재사용하는 기법을 제안한다. 또한, 그래프 변화에 따라 재계산 영역에 대한 탐색 및 처리 비용이 증가하기 때문에 정적 처리와 점진적 처리를 선택적으로 수행하는 비용 모델을 제안한다.
기존 정적 처리 기법의 문제점인 중복 계산을 회피하기 위해 그래프 갱신 시 영향을 받는 부분만 처리하고 연결된 정점들을 다시 탐색하는 비용과 디스크 I/O 비용을 감소시키기 위하여 이전 결과 데이터를 재사용하는 기법을 제안한다. 또한, 그래프 변화에 따라 재계산 영역에 대한 탐색 및 처리 비용이 증가하기 때문에 정적 처리와 점진적 처리를 선택적으로 수행하는 비용 모델을 제안한다. 비용 모델은 과거 이력을 바탕으로 각 처리 방법의 예측값을 계산하여 점진적 처리의 이득을 판별한다.
[그림 7]은 기존 기법들[8][10]과 제안하는 iGAS, iGAS에 비용 모델을 도입한 기법의 성능을 비교하기 위해 PageRank 알고리즘을 각 데이터별로 10회 반복하고 합산한 결과이다. 매 반복마다 그래프를 갱신하여 성능 평가를 수행하였다. 그래프 갱신이 발생하는 상황에서 정적인 처리 기법[8]은 전체 데이터를 계산하여 중복된 결과를 재생성하기 때문에 효율을 얻을 수 없었고, 기존의 점진적 처리 기법[10]은 그래프 갱신에 의해 영향을 받는 부분만을 계산하지만, 정점에 연결된 수만큼 전체를 탐색하는 비용과 디스크 I/O 비용이 발생하기 때문에 iGAS보다 상대적으로 오래 걸리는 것을 확인할 수 있다.
[표 1]은 실험 데이터의 특성을 나타낸다. 실험 데이터는 실제 데이터[13]과 임의적으로 생성한 데이터 두 종류를 사용하였으며 실제 데이터에서는 주변에 영향을 주는 정점의 비율을 파악하기 어렵기 때문에 동일한 그래프를 10개 복제한 데이터를 사용하여 그래프 변화량에 따른 수행 시간을 비교한다. 실제 데이터는 그래프 알고리즘의 연산 속도를 비교하기 위해 라이브저널과 트위터 데이터를 사용한다.
비용 모델은 각 처리 기법의 예측값을 계산하여 점진적 처리 여부를 판별한다. 점진적 처리가 이득인 경우 제안하는 기법인 iGAS(Incremental Gather-Apply-Scatter)를 수행하여 그래프 갱신에 의해 영향을 받은 영역을 점진적으로 처리하고 점진적 처리가 이득을 보지 못하는 경우 GAS에서 전체 데이터를 정적으로 처리한다.
본 논문에서는 데이터 재사용을 통한 점진적인 그래프 스트림 처리 기법을 제안한다. 제안하는 기법은 그래프 스트림 환경에서 실시간 분석 결과를 제공해주기 위해 PowerGraph[8]의 GAS 모델을 점진적으로 처리되도록 변형한다. 즉 제안하는 기법은 그래프의 변경되는 부분만을 처리하고 이전 결과 데이터를 재사용함으로써 데이터를 탐색하는 비용을 감소시킨다.
본 논문에서는 데이터 재사용을 통한 그래프 스트림의 점진적인 처리 기법을 제안하였다. 제안하는 기법은 하나의 정점에 여러 정점이 연결되어있는 경우 이전에 생성된 결과 데이터를 재사용하여 연결된 정점의 탐색 비용 및 디스크 I/O 비용을 감소시켰다. 또한, 비용 모델을 제안하여 처리 비용의 예측값을 계산하고 변화량에 따른 정적인 처리 기법과 점진적인 처리 기법을 선택적으로 수행하여 iGAS만을 사용했을 때 보다 처리속도를 향상시켰다.
제안하는 비용 모델은 실제 처리된 이력을 바탕으로 그래프 갱신에 의해 앞으로 발생할 정적 처리 비용과 점진적 처리 비용의 예측값을 계산하고 점진적 처리 기법이 이득인 경우 선택적으로 수행한다. 비용 모델은 예상 정적 처리 비용과 예상 점진적 처리 비용의 차로수식(4)와 같이 나타낸다.
제안하는 기법은 그래프 스트림 환경에서 실시간 분석 결과를 제공해주기 위해 PowerGraph[8]의 GAS 모델을 점진적으로 처리되도록 변형한다. 즉 제안하는 기법은 그래프의 변경되는 부분만을 처리하고 이전 결과 데이터를 재사용함으로써 데이터를 탐색하는 비용을 감소시킨다. 한편 그래프 스트림에 의해 변경되는 영역이 큰 경우 탐색 비용 및 처리 비용이 증가할 수 있다.
GraphLab[7]은 분산 공유 메모리 환경에서 비동기식 처리를 지원한다. 프로그램은 인접한 정점 값을 읽어서 알고리즘을 수행하고 그 결과를 Ghosting을 사용하여 분산된 서버에 공유메모리를 통해 액세스가 가능하도록 한다.

대상 데이터

Gupta et al.[10]이 제안한 기존기법은 다른 기존 점진적 처리 기법[11][12]과 달리 부분적인 중복 계산을 하지 않기 때문에 성능 평가 대상으로 선택하였다. 성능 평가의 환경은 Intel(R) Core i5 CPU 프로세서, 32G 메모리, 1 TB 디스크로 구성된다.
[10]이 제안한 기존기법은 다른 기존 점진적 처리 기법[11][12]과 달리 부분적인 중복 계산을 하지 않기 때문에 성능 평가 대상으로 선택하였다. 성능 평가의 환경은 Intel(R) Core i5 CPU 프로세서, 32G 메모리, 1 TB 디스크로 구성된다. [표 1]은 실험 데이터의 특성을 나타낸다.
실험 데이터는 실제 데이터[13]과 임의적으로 생성한 데이터 두 종류를 사용하였으며 실제 데이터에서는 주변에 영향을 주는 정점의 비율을 파악하기 어렵기 때문에 동일한 그래프를 10개 복제한 데이터를 사용하여 그래프 변화량에 따른 수행 시간을 비교한다. 실제 데이터는 그래프 알고리즘의 연산 속도를 비교하기 위해 라이브저널과 트위터 데이터를 사용한다.

데이터처리

제안하는 기법의 우수성을 입증하기 위해 정적 처리 기법으로 전체를 계산하는 기법과 변경된 부분만을 재계산 하는 점진적 처리 기법의 성능 비교를 수행한다. 성능 평가 대상인 정적 처리 기법의 PowerGraph[8]는 그래프 병렬처리 시스템으로 그래프 분석 알고리즘에서 성능과 GAS의 구조적면에서 효율적이기 때문에 성능 평가 대상으로 선택되었고 점진적 처리 기법에서는 Gupta et al.

성능/효과

[그림 6]의 (a)는 변화량에 따른 정적 처리 기법과 비용 모델을 적용하지 않은 점진적 처리 기법의 수행시간을 비교한 결과를 나타낸다. [그림 6]의 성능평가 (a)와 같이 변화량이 60% 이상인 경우 iGAS는 정적인 처리 기법보다 수행시간이 더 오래 걸리는 것을 확인할 수 있다. 그래프 갱신에 의해 그래프의 대부분을 재계산해야 하는 경우 iGAS는 재계산 영역을 탐색하는 비용이 포함되기 때문에 정적 처리보다 이점을 얻을 수 없다.
그래프 갱신이 발생하는 상황에서 정적인 처리 기법[8]은 전체 데이터를 계산하여 중복된 결과를 재생성하기 때문에 효율을 얻을 수 없었고, 기존의 점진적 처리 기법[10]은 그래프 갱신에 의해 영향을 받는 부분만을 계산하지만, 정점에 연결된 수만큼 전체를 탐색하는 비용과 디스크 I/O 비용이 발생하기 때문에 iGAS보다 상대적으로 오래 걸리는 것을 확인할 수 있다. 기존 점진적 처리 기법 보다 iGAS는 평균 약 150%, iGAS와 비용 모델을 같이 사용한 기법은 평균 약 203%정도 우수한 성능을 보였다. iGAS 기법만을 적용하였을 때는 그래프의 대다수가 변경되는 상황에서 처리 비용은 정적 처리와 비슷한 성능을 보이지만, 변경된 만큼 탐색 비용이 발생하기 때문에 상황에 따라 정적 처리 기법보다 성능이 저하될 수 있다.
제안하는 기법은 하나의 정점에 여러 정점이 연결되어있는 경우 이전에 생성된 결과 데이터를 재사용하여 연결된 정점의 탐색 비용 및 디스크 I/O 비용을 감소시켰다. 또한, 비용 모델을 제안하여 처리 비용의 예측값을 계산하고 변화량에 따른 정적인 처리 기법과 점진적인 처리 기법을 선택적으로 수행하여 iGAS만을 사용했을 때 보다 처리속도를 향상시켰다. 그래프에서 변경되는 부분이 작은 경우 점진적으로 변경된 부분만을 처리하여 정적인 처리 기법의 중복계산을 회피하기 때문에 효율적이며, 변경되는 부분이 큰 경우 정적인 처리 기법을 수행하여 탐색 비용이 발생하지 않아 점진적 처리 기법보다 효율적이다.
성능 평가를 통해 제안하는 기법의 데이터를 처리하는 속도가 기존 점진적 처리 기법에 비해 약 203% 향상된 것을 확인할 수 있었다. 또한, 정적 처리기법과 제안하는 기법의 처리속도를 변화량에 따라 비교함으로써 비용 모델의 타당성을 입증하였다. 제안하는 기법은 소셜 네트워크나 IoT 등과 같은 분야에서 실시간 그래프 분석 및 처리에 적용할 수 있으며 특히, 패턴 변화 또는 이상 감지 파악에 활용될 수 있다.
비용 모델에 따라 점진적인 처리가 비효율적인 경우 정적 처리 기법을 사용하여 변경된 부분을 탐색하지 않고 전체 데이터를 처리한다. 변화량 10%에서 100%까지 각 기법의 수행시간을 합산하여 비교해보면 정적 처리 기법 대비 iGAS만 사용하였을 경우에는 약 95%로 정적 처리 기법보다 오래 걸렸고 iGAS와 비용 모델을 같이 사용한 경우에 는 약 136%로 비용 모델을 사용한 것이 iGAS만 사용하였을 때보다 이점이 있음을 확인할 수 있다.
그래프에서 변경되는 부분이 작은 경우 점진적으로 변경된 부분만을 처리하여 정적인 처리 기법의 중복계산을 회피하기 때문에 효율적이며, 변경되는 부분이 큰 경우 정적인 처리 기법을 수행하여 탐색 비용이 발생하지 않아 점진적 처리 기법보다 효율적이다. 성능 평가를 통해 제안하는 기법의 데이터를 처리하는 속도가 기존 점진적 처리 기법에 비해 약 203% 향상된 것을 확인할 수 있었다. 또한, 정적 처리기법과 제안하는 기법의 처리속도를 변화량에 따라 비교함으로써 비용 모델의 타당성을 입증하였다.
데이터를 캐시에 저장하고 사용함으로써 반복적인 계산을 효율적으로 가속화한다. 이를 통해 새로운 데이터와 이전 결과 데이터를 결합하여 새로운 결과를 만들 수 있으며 전체적인 데이터처리 효율을 높인다.
제안하는 기법은 변경되는 부분의 이전 결과 데이터만 수집하여 연결되어있는 전체 데이터를 수집할 필요가 없으므로 기존에 제안된 점진적인 처리 기법[10]보다 디스크 I/O 비용을 감소시킬 수 있다. [그림 5]는 iGAS 수행시 수집되는 정점을 나타낸다.
iGAS 기법만을 적용하였을 때는 그래프의 대다수가 변경되는 상황에서 처리 비용은 정적 처리와 비슷한 성능을 보이지만, 변경된 만큼 탐색 비용이 발생하기 때문에 상황에 따라 정적 처리 기법보다 성능이 저하될 수 있다. 제안하는 기법은 점진적인 처리와 비용 모델을 사용하여 우수한 성능을 보여주는 것을 확인할 수 있다.
새로 계산된 정점 u의 값을 인접한 정점 v4에게 전파하고 정점 v4는 정점 u의 값만을 수집하여 새로운 값을 계산한다. 제안하는 점진적 처리 기법을 통해 그래프 스트림 처리 시 데이터의 중복 처리가 감소하고 연결된 정점의 재탐색 비용을 감소시켜 데이터의 처리 속도가 향상된다.

후속연구

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

핵심어	질문	논문에서 추출한 답변
	그래프 데이터는 어떤 목적으로 사용되는가?	소셜 네트워크에서 사용자간의 관계 및 정보의 흐름을 표현하거나 IoT(Internet of Things)에서 각종 사물들 사이에 상호 작용을 표현하기 위해 그래프 데이터가 활용되고 있다. 최근 다양한 분야에서 그래프 데이터를 분석하여 중요한 비즈니스 가치를 창출하기 위해 연구가 진행되고 있다[1-4].
	그래프 데이터를 분석하여 비즈니스 가치를 창출하는 사례는?	최근 다양한 분야에서 그래프 데이터를 분석하여 중요한 비즈니스 가치를 창출하기 위해 연구가 진행되고 있다[1-4]. 예를 들어, IoT나 재난안전 분야에서 센서 간 상호관계를 그래프 스트림으로 나타내고 실시간으로 분석하여 위험 발생을 감지하고 예측한다. 소셜 네트워크 분야에서는 사용자간의 상호작용을 실시간으로 트렌드 분석하여 광고주의 전략에 맞는 정확한 광고를 제공할 수 있다.
	그래프란?	그래프는 G = (V, E)로 나타내며, V는 정점(vertex) 집합을 나타내고, E는 간선(edge) 집합을 나타낸다. 각 정점에는 정점의 특징이나 정보가 포함될 수 있으며, 이와 유사하게 간선에는 간선의 정보와 정점간의 관계 같은 정보가 있을 수 있다.

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증

데이터 재사용을 고려한 그래프 스트림의 점진적 처리 기법
Incremental Processing Scheme for Graph Streams Considering Data Reuse 원문보기

초록
AI-Helper

Abstract ▼ AI-Helper

주제어

AI 본문요약
AI-Helper

문제 정의

가설 설정

제안 방법

대상 데이터

데이터처리

성능/효과

후속연구

질의응답

이 논문을 인용한 문헌

저자의 다른 논문 :

연구과제 타임라인

관련 콘텐츠

원문 보기

원문 URL 링크

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

연합인증

데이터 재사용을 고려한 그래프 스트림의 점진적 처리 기법 Incremental Processing Scheme for Graph Streams Considering Data Reuse 원문보기

초록 용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

Abstract ▼ AI-Helper

주제어

AI 본문요약 엑셀 다운로드 AI-Helper

문제 정의

가설 설정

제안 방법

대상 데이터

데이터처리

성능/효과

후속연구

질의응답

이 논문을 인용한 문헌

저자의 다른 논문 :

조중권 (1) 한진수 (4) 김민수 (5) 최도진 (18) 복경수 (88) 유재수 (329)

연구과제 타임라인

전체(0) 논문(0) 특허(0) 보고서(0)

전체(0) 논문(0) 특허(0) 보고서(0)

관련 콘텐츠

원문 보기

원문 URL 링크

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

데이터 재사용을 고려한 그래프 스트림의 점진적 처리 기법
Incremental Processing Scheme for Graph Streams Considering Data Reuse 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper