효율적인 대용량 그래프 분석을 위한 압축 그래프 기반의 요약 기법

• 영문명: Summarization Technique on a Compressed Graph for Massive Graph Analysis
• 발행기관: 한국빅데이터서비스학회
• 저자명: Ho Jin Seo 김현욱(Hyun wook Kim) 박기성(Ki sung Park) 한용구(Yong koo Han) 이영구(Young Koo Lee)
• 간행물 정보: 『한국빅데이터서비스학회 논문지』한국빅데이터서비스학회 논문지 2권 1호, 25~35쪽, 전체 11쪽
• 주제분류: 공학 > 컴퓨터학
• 파일형태: PDF
• 발행일자: 2015.06.30

국문 초록

정보화 기기의 발달로 소셜 네트워크, 화학복합물, 시맨틱 웹 등과 같은 다양한 분야에서 대용량 그래프 데이터가 축적되고 있다. 그래프 OLAP은 그래프의 속성 또는 속성들의 조합을 다차원으로 요약 표현하여 대용량 그래프에서 유용한 정보를 찾는 기술이다. 그러나 대용량 그래프에서 다양한 OLAP 연산 사용을 위하여 그래프를 요약(graph summarization)하는데 오랜 수행 시간을 요구하는 문제점이 있다. 본 논문은 대용량 그래프의 효율적인 분석을 위하여 압축된 그래프에서 그래프 요약을 수행하는 기법을 제안한다. 제안하는 기법은 WAH(word aligned hybrid)를 통해 대용량 그래프의 물리적 공간을 효율적으로 압축 표현하고, 압축된 그래프에서 그래프 요약 기법을 적용하여 대용량 그래프를 효과적으로 분석한다. 실험을 통해 제안하는 기법이 기존의 그래프 요약 기법보다 공간 사용량은 최대 70%, 수행 시간은 최대 40% 개선함을 보인다.

영문 초록

Recently, due to development of information technologies, massive graph data are being accumulated in various applications such as social networks, chemical compounds, and semantic webs. The graph OLAP is the technique that discovers informative knowledge by summarizing properties and possible combinations of these properties of a graph as different multidimensional spaces. However, the graph summarization for graph OLAP operations requires a long running time in a massive graph. In this paper, we propose a summarization technique on a compressed graph for supporting efficient analysis of a massive graph. The proposed technique compresses a massive graph physically by using the WAH(word aligned hybrid), and then analyzes the compressed massive graph by using graph summarization. In experiments, we show that the proposed technique can reduce physical space and running time by up to 70% and 40% compared with the existing graph summarization technique, respectively.

목차

요약

Abstract

1. 서론

2. 관련 연구

3. 그래프 압축 및 요약 프레임워크

4. 성능 평가

5. 결론

6. 참고 문헌

키워드

대용량 그래프 그래프 압축 그래프 요약 Massive graph Graph compression Graph summarization