원문정보
An Efficient Graph Similarity Query Processing Technique using MapReduce
초록
영어
Graph is widely used to model complex structured data such as biomedical data, chemical data, and social network data. It is essential to find graphs similar to a given query in many applications. In this paper, we focus on chemical graph data and propose a graph similarity query processing technique based on a filtering and verification framework. We propose a filtering technique considering the heavy computation requirement of graph data and develop a novel technique to efficiently verify candidate graphs. We also propose a distributed processing framework using MapReduce to support large scale graph data. Through the experiments on real chemical data, we show that the proposed technique substantially improves the performance of query processing.
한국어
그래는 생물학, 화학, 사회 계망 데이터 등 복잡한 구조의 데이터를 모델링하는데 리 사용되는 자료구조이다. 이러한 그래 데이터에서 서로 유사한 데이터를 찾아내는 것은 매우 다양한 응용에서 필수으로 요구되는 작업이 다. 본 논문에서는 화학 그래에 을 맞추어, 필터링-검증 임워크 기반의 유사도 기반 그래 질의 처리 기 법을 제안한다. 계산량이 많은 그래 데이터의 특징에 맞는 필터링 방법을 제안하고, 후보 그래들을 효율으로 검증하기 한 기법을 제안한다. 한, 규모 데이터에서 실시간 분석이 가능할 수 있도록 MapReduce를 이용 하는 분산처리 기법을 제안하고, 실 데이터에 한 실험을 통해 본 논문에서 제안하는 방법이 유사도 기반 그래 질의 처리의 성능을 크게 개선함을 입증한다.
목차
Abstract
1. 서론
2. 배경
2.1 그래프 편집거리
2.2 그래프 시그니처 기법
3. 그래프 유사도 질의처리 기법
3.1 후보 그래프 필터링 기법
3.2 후보 그래프 검증 기법
4. MapReduce를 이용한 분산처리 기법
4. 실험
4.1 실험 환경 및 실험 데이터
4.2 필터링 및 검증 성능 비교
4.3 MapReduce를 이용한 질의 처리 성능 비교
5. 결론
Acknowledgement
참고문헌