[논문]분산 환경에서 경로 질의 기반 서브 그래프 탐색 기법

김민영; 최도진; 박재열; 김연동; 임종태; 복경수; 최한석; 유재수

doi:10.5392/jkca.2019.19.01.141

분산 환경에서 경로 질의 기반 서브 그래프 탐색 기법
Subgraph Searching Scheme Based on Path Queries in Distributed Environments 원문보기

한국콘텐츠학회논문지 = The Journal of the Korea Contents Association, v.19 no.1, 2019년, pp.141 - 151

김민영 (충북대학교 정보통신공학과) , 최도진 (충북대학교 정보통신공학과) , 박재열 (충북대학교 정보통신공학과) , 김연동 (충북대학교 정보통신공학과) , 임종태 (충북대학교 정보통신공학과) , 복경수 (충북대학교 정보통신공학과) , 최한석 (목포대학교 컴퓨터공학과) , 유재수 (충북대학교 정보통신공학과)

초록
AI-Helper

개체 간의 상호 작용을 나타내기 위해 그래프 데이터 형태의 네트워크가 많은 애플리케이션에서 사용되고 있다. 최근에는 빅데이터 기술의 발달로 처리해야할 네트워크의 크기가 점점 커짐에 따라 하나의 서버에서 이를 처리하기 어려워졌기 때문에 분산 처리의 필요성 또한 증가하고 있다. 본 논문에서는 이러한 그래프 데이터가 분산 저장되어있는 환경에서 서브 그래프 탐색을 효율적으로 수행하기 위한 분산 처리시스템을 제안한다. 불필요한 탐색을 줄이기 위해 데이터의 통계정보를 활용해 확률적인 스코어링을 통해 탐색 순서를 정한다. 그래프 네트워크의 정점과 차수의 관계는 데이터의 종류에 따라 다른 특성을 보일 수 있기 때문에 여러 분포적 특성을 갖는 그래프에 대해 다른 스코어링 방법을 통해 불필요한 탐색을 줄이기 위한 스코어를 계산하여 탐색 순서를 결정한다. 결정된 순서에 따라 그래프가 분산 저장된 서버에서 순차적으로 탐색한다. 성능평가에서는 제안하는 기법의 우수성을 입증하기 위해 기존 기법과의 비교를 수행하였으며, 그 결과 기존 기법보다 탐색 시간이 약 3~10% 향상됨을 보였다.

Abstract ▼ AI-Helper

A network of graph data structure is used in many applications to represent interactions between entities. Recently, as the size of the network to be processed due to the development of the big data technology is getting larger, it becomes more difficult to handle it in one server, and thus the necessity of distributed processing is also increasing. In this paper, we propose a distributed processing system for efficiently performing subgraph and stores. To reduce unnecessary searches, we use statistical information of the data to determine the search order through probabilistic scoring. Since the relationship between the vertex and the degree of the graph network may show different characteristics depending on the type of data, the search order is determined by calculating a score to reduce unnecessary search through a different scoring method for a graph having various distribution characteristics. The graph is sequentially searched in the distributed servers according to the determined order. In order to demonstrate the superiority of the proposed method, performance comparison with the existing method was performed. As a result, the search time is improved by about 3 ~ 10% compared with the existing method.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

본 논문에서는 분산 환경에서 서브 그래프 탐색 질의를 처리하기 위한 경로 기반 그래프 탐색 기법을 제안하였다. 데이터 그래프의 정점과 그 정점의 간선 사이의 분포를 통해 질의 그래프 탐색 시 불필요한 탐색을 제거할 수 있는 필터링 값을 계산한다.
본 논문에서는 질의 그래프와 동일한 레이블을 갖는 서브 그래프를 찾기 위해 데이터 분산 처리 플랫폼인 Spark에서 경로 질의 기반 그래프 탐색 기법을 제안한다. 그래프의 통계정보를 바탕으로 탐색하지 않아도 되는 정점을 필터링하는 확률 값을 예측하여 불필요한 탐색을 줄이도록 탐색 순서를 결정한다.
그러나 [12]는 시작 정점을 선정하는 특별한 기준이 없고, 탐색 비용을 줄일 수 있는 비용모델을 구축하지 않기 때문에 시작 정점이 되는 헤드 세그먼트의 레이블과 일치하는 정점의 개수가 많거나 해당 정점의 차수가 클 경우 탐색비 용이 선형적으로 증가한다는 문제점을 가지고 있다. 본 연구에서는 이러한 경로 기반 질의 탐색 방법을 기반으로 탐색 비용을 줄일 수 있는 경로로 탐색하는 방법을 제안한다. 데이터 그래프에 대해 수집된 통계정보를 바탕으로 정점 당 발생할 수 있는 차수의 확률밀도함수를 통해, 해당 정점의 차수가 등장할 확률을 고려하여 탐색하지 않아도 되는 확률을 스코어링한다.

제안 방법

[12]는 경로 탐색에 대한 비용예측이 없이 분할된 질의 그래프에 대해 탐색을 수행하였다. [표 1]은 성능평가 환경을 보여준다, 성능 평가 환경은 Intel(R) Core(TM) i7-6700 CPU 3.40GHz 프로세서, 30G메모리, 3개의 클러스터 환경으로 구성되었고, Spark의 GraphX로 Scala를 통해 구현하였다. 실험 평가를 위해 실제 데이터 집합과 가상의 데이터 집합을 사용하였다.
데이터 그래프의 정점과 그 정점의 간선 사이의 분포를 통해 질의 그래프 탐색 시 불필요한 탐색을 제거할 수 있는 필터링 값을 계산한다. 계산된 필터링 값을 통해 가장 많은 필터링이 될 수 있는 정점을 탐색의 시작 정점으로 선정하고, 필터링 값에 따라 질의 그래프를 작은 단위의 서브 질의로 분할하여 탐색을 수행 한다. 이로 인해 기존 기법보다 빠르게 서브 그래프에 대한 탐색이 가능하다.
본 연구에서는 이러한 경로 기반 질의 탐색 방법을 기반으로 탐색 비용을 줄일 수 있는 경로로 탐색하는 방법을 제안한다. 데이터 그래프에 대해 수집된 통계정보를 바탕으로 정점 당 발생할 수 있는 차수의 확률밀도함수를 통해, 해당 정점의 차수가 등장할 확률을 고려하여 탐색하지 않아도 되는 확률을 스코어링한다. 이 값은 질의 그래프와 데이터 그래프의 차수의 차이로 인해 탐색하지 않아도 되는 정점을 필터링할 수 있는 확률이다.
본 논문에서는 분산 환경에서 서브 그래프 탐색 질의를 처리하기 위한 경로 기반 그래프 탐색 기법을 제안하였다. 데이터 그래프의 정점과 그 정점의 간선 사이의 분포를 통해 질의 그래프 탐색 시 불필요한 탐색을 제거할 수 있는 필터링 값을 계산한다. 계산된 필터링 값을 통해 가장 많은 필터링이 될 수 있는 정점을 탐색의 시작 정점으로 선정하고, 필터링 값에 따라 질의 그래프를 작은 단위의 서브 질의로 분할하여 탐색을 수행 한다.
본 논문에서는 이를 기반으로 그래프의 정점과 그 정점과 연결된 간선이 특정한 분포를 보일 경우, 탐색에서 제외될 확률적인 필터링 값을 계산하고 질의 그래프의 어떤 정점을 우선적으로 탐색할 것인지에 대한 탐색 순서를 결정한다. 데이터의 특성에 따라 소셜 네트워크 등에서 나타나는 power-law형 분포를 보일 경우와 여타 다른 그래프에서 데이터의 분포가 대부분 평균에 가까운 정규 분포를 보일 경우를 모두 고려하여 두 가지 스코어링 방법을 제안하였다
필터링 단계를 거친 후보 집합은 질의 그래프의 응답에 해당하는 결과에 false positive에 해당하는 결과가 포함되어 있기 때문에 후보집합에 대한 검증이 필요하다. 때문에 두 번째 단계인 검증단계에서 기생성된 후보 집합에 대한 서브 그래프 동형성 검사를 수행하여, 최종적으로 질의 그래프에 대한 결과집합을 생성한다.
[그림 2](a)에서 G_L(v_i)의 동일한 레이블 수가 1개인 4번 정점을 시작으로 경로를 탐색할 경우보다, 동일한 레이블 수가 2개인 3, 6번 정점을 시작으로 경로를 탐색하는 것이 더 많은 탐색이 필요하다. 때문에 제안하는 기법에서는 그래프 G의 각 정점들의 레이블 수의 통계를 수집하고, 적은 수의 레이블을 갖는 정점이 시작 정점으로 선정되도록 고려한다
또한 적절한 수의 정점을 시작으로 탐색을 이어 나간다고 해도 연결된 이웃 정점을 모두 탐색해야 하기 때문에 연결된 간선의 수에 따라 탐색해야할 경우의 수도 무수히 많아진다. 때문에 제안하는 기법에서는 불필요한 탐색을 줄이고 더 적은 탐색으로 질의 그래프와 일치하는 서브 그래프를 탐색하기 위하여 정점의 수와 차수를 고려해 필터링 스코어를 계산한다.
제안하는 기법은 시나리오에 따라 데이터의 분포를 고려한 스코어링 방법과 평균차수만을 고려한 스코어링 방법으로 나뉜다. 또한 분포를 고려한 스코어링 방 법은 데이터의 분포에 따라 다른 확률밀도함수를 사용하기 때문에 각 방법에 대한 자체 성능평가를 수행하였다. 시나리오 1은 분포에 따라 정규분포와 power-law 분포로 나뉘며, 각 분포에서 질의 그래프의 차수가 발생할 확률을 통해 스코어링한다.
[15]에 따르면 실제로 많은 그래프 네트워크에서 각 정점과 그 정점의 차수가 power-law형태를 보임을 보였다. 본 논문에서는 이를 기반으로 그래프의 정점과 그 정점과 연결된 간선이 특정한 분포를 보일 경우, 탐색에서 제외될 확률적인 필터링 값을 계산하고 질의 그래프의 어떤 정점을 우선적으로 탐색할 것인지에 대한 탐색 순서를 결정한다. 데이터의 특성에 따라 소셜 네트워크 등에서 나타나는 power-law형 분포를 보일 경우와 여타 다른 그래프에서 데이터의 분포가 대부분 평균에 가까운 정규 분포를 보일 경우를 모두 고려하여 두 가지 스코어링 방법을 제안하였다
본 연구에서는 제안하는 기법의 우수성을 보이기 위해 기존 기법[12]와의 성능비교와 그래프의 분포에 따른 시나리오에 대한 자체비교를 수행하였다. [12]는 경로 탐색에 대한 비용예측이 없이 분할된 질의 그래프에 대해 탐색을 수행하였다.
서브 그래프 탐색을 위한 여러 기법 중, 본 연구에서는 경로 기반의 탐색 기법을 차용하였다. 경로 기반의 탐색 기법은 데이터 그래프에 대해 여러 가지 특징에 대한 인덱스를 구축할 필요가 없고, 한 정점과 연결된 이웃정점만을 선택해서 탐색하여 데이터 그래프 전체에 대한 서브 그래프 동형성 검사를 수행하지 않아, 전체적인 탐색비용에 대한 이점이 있다.
데이터의 분포는 정점과 그 차수가 대체적으로 균일하게 분포되도록 생성하였다. 성능평가로는 그래프의 분포 시나리오에 따른 자체 평가, 질의 그래프의 구조적 차이에 따른 탐색 시간을 비교하였다
또한 분포를 고려한 스코어링 방 법은 데이터의 분포에 따라 다른 확률밀도함수를 사용하기 때문에 각 방법에 대한 자체 성능평가를 수행하였다. 시나리오 1은 분포에 따라 정규분포와 power-law 분포로 나뉘며, 각 분포에서 질의 그래프의 차수가 발생할 확률을 통해 스코어링한다. 정규분포는 normalFS로, power-law분포는 powerFS로 표기하였다.
그래프의 통계정보를 바탕으로 탐색하지 않아도 되는 정점을 필터링하는 확률 값을 예측하여 불필요한 탐색을 줄이도록 탐색 순서를 결정한다. 이러한 순서를 바탕으로 질의 그래프를 서브 질의로 분할하고 각 슬레 이브 서버에서 탐색을 수행한다.
따라서 G_L(v_i)보다 낮은 차수를 갖는 Q_L(v_i)은 필터링할 수 있는 정점이다. 이를 기반으로 본 연구에서는 차수의 차이로 인해 탐색할 정점을 필터링 할 수 있는 스코어를 계산한다
제안하는 기법은 시나리오에 따라 데이터의 분포를 고려한 스코어링 방법과 평균차수만을 고려한 스코어링 방법으로 나뉜다. 또한 분포를 고려한 스코어링 방 법은 데이터의 분포에 따라 다른 확률밀도함수를 사용하기 때문에 각 방법에 대한 자체 성능평가를 수행하였다.
이로 인해 기존 기법보다 빠르게 서브 그래프에 대한 탐색이 가능하다. 제안한 기법은 소셜 네트워크, 단백질-단백질 상호작용 네트워크 또는 여타 정규분포를 따르는 그래프에서 그래프의 분포적 특성에 따라 스코어링 방법을 달리하여 적용하여 여러 데이터 그래프에 적용할 수 있다. 이를 통해 다양한 분포적 특성을 갖는 데이터에 대해 서브 그래프 탐색 질의를 효율적으로 수행할 수 있다.
[12]는 이러한 경로 기반 질의 탐색기법을 제안하였다. 질의 그래프를 트리플렛 형태의 세그먼트로 분할하고, 세그먼트 단위로 탐색을 수행한다. 첫 탐색 순서인 헤드 세그먼트에서, 헤드 세그먼트 정점의 레이블과 일치하는 정점을 각 그래프에서 찾아 시작 정점으로 선정한다.

대상 데이터

실험 평가를 위해 실제 데이터 집합과 가상의 데이터 집합을 사용하였다. Standford에서 제공하는 데이터와 Graph Generator 소프트웨어인 GTgraph를 사용하였다. skitter는 인터넷 토폴로지 데이터로, 약 170만개의 정점과 1100만개의 간선으로 이루어져 있다.
시나리오 2는 데이터 그래프에서의 평균 차수만을 통해 스코어링하는 방법으로, avgDgFS으로 표기하였다. 실험 데이터 집합에서 정규분포형 데이터는 GTgraph를 사용해 생성한 랜덤 데이터를 사용하였고, power-law분포형 데이터는 실제 데이터 집합을 사용하였다.
40GHz 프로세서, 30G메모리, 3개의 클러스터 환경으로 구성되었고, Spark의 GraphX로 Scala를 통해 구현하였다. 실험 평가를 위해 실제 데이터 집합과 가상의 데이터 집합을 사용하였다. Standford에서 제공하는 데이터와 Graph Generator 소프트웨어인 GTgraph를 사용하였다.

데이터처리

제안하는 기법과 기존 기법과의 비교평가를 위해 질의 그래프의 구조적 유형에 따라 탐색시간의 차이를 평가하였다. 질의 그래프가 연결된 구조적 특성은 탐색 성능에 유의미한 영향을 미친다.

성능/효과

[그림 6]은 시나리오별 탐색 시간을 나타낸 것이다. 데이터 집합에 관계없이 시나리오 1의 확률밀도함수의 필터링 확률과 레이블 수로 스코어를 계산하는 방법이 시나리오 2의 평균차수와 레이블 수로 스코어를 계산하는 방법보다 우세한 성능을 보였다. 이는 그래프의 정점과 차수가 특정한 분포를 따르고 있기 때문으로 보인다.
이를 통해 다양한 분포적 특성을 갖는 데이터에 대해 서브 그래프 탐색 질의를 효율적으로 수행할 수 있다. 성능평가 결과, 두 가지 데이터에서 모두 기존 기법보다 탐색 시간이 약 3~10% 향상됨을 확인할 수 있었다. 본 논문에서는 스코어링을 위해 단순히 정점의 수와 정점의 차수를 사용하였지만, 실제로 필터링에 영향을 미칠 수 있는 요소들은 간선의 특성이나 사이클 등이 다양하게 존재한다.
제안하는 기법에서는 무작위로 탐색하는 것이 아닌, 질의 그래프에 대해 각 정점이 그래프에서 발생할 확률을 예측하여 적은 탐색 횟수로도 질의 그래프를 만들 수 있는 경로의 탐색방법을 예측하기 때문에 q4같은 혼합된 구조의 질의에서 강점을 보였다.
그러나 질의 간 큰 차이를 확인할 수는 없었는데, 데이터의 랜덤성으로 인한 것으로 보인다. 질의 간 탐색 시간의 차이는 크지 않지만 탐색 방법에서는 제안하는 기법의 normalFS와 avgDgFS의 성능이 우수함을 확인할 수 있다

후속연구

본 논문에서는 스코어링을 위해 단순히 정점의 수와 정점의 차수를 사용하였지만, 실제로 필터링에 영향을 미칠 수 있는 요소들은 간선의 특성이나 사이클 등이 다양하게 존재한다. 그러므로 향후에는 그래프의 다양한 요소를 고려하여 필터링 성능 향상을 위해 연구할 예정이다.

질의응답

핵심어	질문	논문에서 추출한 답변
	경로 기반 질의 탐 색기법의 문제점은 무엇인가?	이어 서 분할된 세그먼트에 대한 탐색이 수행되고 마스터는 슬레이브 서버로부터 전송된 결과를 취합한다. 그러나 이 기법은 시작 정점을 선정하는 특별한 기준이 없고, 탐색 비용을 줄일 수 있는 비용모델을 구축하지 않기 때문에 시작 정점이 되는 헤드 세그먼트의 레이블과 일 치하는 정점의 개수가 많거나 해당 정점의 차수가 클 경우 탐색비용이 증가한다는 문제점을 가지고 있다.
	서브 그래프는 무엇을 의미하는가?	이러한 그래프 구조에서 질의로 주어진 그래프에 대해 일치하는 서브 그래프를 탐색하는 서브 그래프 탐색(Subgraph searching)은 중요한 의미를 갖 는다. 소셜 네트워크에서 서브 그래프는 어떤 관계를 중심으로 한 사용자 간의 그룹을 의미할 수 있으며, 단 백질-단백질 상호작용 네트워크 에서는 특정 단백질 구조에 대한 분석의 기초가 되기도 한다. 서브 그래프 는 질의에 따라 완전 일치 서브 그래프 탐색[8]과 유사 서브 그래프 탐색[9]으로 분류된다.
	서브 그래프는 질의에 따라 무엇으로 분류되는가?	소셜 네트워크에서 서브 그래프는 어떤 관계를 중심으로 한 사용자 간의 그룹을 의미할 수 있으며, 단 백질-단백질 상호작용 네트워크 에서는 특정 단백질 구조에 대한 분석의 기초가 되기도 한다. 서브 그래프 는 질의에 따라 완전 일치 서브 그래프 탐색[8]과 유사 서브 그래프 탐색[9]으로 분류된다. 완전 일치 서브 그 래프 탐색은 질의 그래프와 완전하게 일치하는 서브 그 래프를 찾는 질의이며, 유사 서브 그래프 탐색은 질의 그래프와 일정 부분 유사도를 갖는 서브 그래프를 찾는 질의이다.

참고문헌 (16)

A. Cuzzocrea, F. Furfaro, G. M. Mazzeo, and D. Sacca, "A grid framework for approximate aggregate query answering on summarized sensor network readings," Proc. OTM Workshops, pp.144-153, 2004.
A. Fariha, C. F. Ahmed, C. K. Leung, S. M. Abdullah, and L. Cao, "Mining frequent patterns from human interactions in meetings using directed acyclic graphs," Proc. Pacific-Asia Conference on Knowledge Discovery and Data Mining, Springer, pp.38-49, 2013.
F. Jiang and C. K. Leung, "Mining interesting "following" patterns from social networks," Proc. International Conference on Data Warehousing and Knowledge Discovery, pp.308-319, 2014.
F. Towards, "Towards a Scalable HDFS Architecture," Proc. International Conference on Collaboration Technologies and Systems, pp.155-161, 2013.
J. Dorre, S. Apel, and C. Lengauer, "Modeling and optimizing MapReduce programs," Concurrency and Computation: Practice and Experience, Vol.27, No.7, pp.1734-1766, 2015.

상세보기
A. Alam and J. Ahmed, "Hadoop Architecture and Its Issues," Proc. International Conference on Computational Science and Computational Intelligence, pp.288-291, 2014.
X. Liao, Z. Gao, W. Ji, and Y. Wang, "An enforcement of real time scheduling in Spark Streaming," Proc. International Green and Sustainable Computing Conference, pp.1-6, 2015.
N. Talukder, and M. J. Zaki, "A distributed approach for graph mining in massive networks," Data Mining and Knowledge Discovery, Vol.30, No.5, pp.1024-1052, 2016.

상세보기
Y, Tian, R. C. McEachin, C. Santos, D. J. States, and J. M. Patel, "SAGA: a subgraph matching tool for biological graphs," Bioinformatics, Vol.23, No.2, pp.232-239, 2007.

상세보기
J. Cheng, Y. Ke, and W. Ng, "Efficient query processing on graph databases," ACM Transactions on Database Systems, Vol.34, No.1, pp.1-48, 2009.
S. Khuller, B. Raghavachari, and N. E. Young, "Balancing minimum spanning trees and shortest-path trees," Algorithmica, Vol.14, No.4, pp.305-321, 1995.

상세보기
J. Balaji and R. Sunderraman, "Distributed Graph Path Queries Using Spark," Proc. COMPSAC Workshops, pp.326-331, 2016.
X. Zhang and L. Chen, "Distance-aware selective online query processing over large distributed graphs," Data Science and Engineering, Vol.2, No.1, pp.2-21, 2017.

상세보기
N. Jing, Y. Huang, and E. A. Rundensteiner, "Hierarchical encoded path views for path query processing: An optimal model and its performance evaluation," IEEE Transactions on Knowledge and Data Engineering, Vol.10, No.3, pp.409-432, 1998.

상세보기
M. Faloutsos, P. Faloutsos, and C. Faloutsos, "On power-law relationships of the internet topology," ACM SIGCOMM 1999 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, pp.251-262, 1999.
M. L. Goldstein, S. A. Morris, and G. G. Yen, "Problems with fitting to the power-law distribution," The European Physical Journal B-Condensed Matter and Complex Systems, Vol.41, No.2, pp.255-258, 2004.

상세보기

저자의 다른 논문 :

LOADING...

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, 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

연합인증