MapReduce를 이용한 효율적인 유사도 기반 그래프 질의 처리 기법
An Efficient Graph Similarity Query Processing Technique using MapReduce
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
그래는 생물학, 화학, 사회 계망 데이터 등 복잡한 구조의 데이터를 모델링하는데 리 사용되는 자료구조이다. 이러한 그래 데이터에서 서로 유사한 데이터를 찾아내는 것은 매우 다양한 응용에서 필수으로 요구되는 작업이 다. 본 논문에서는 화학 그래에 을 맞추어, 필터링-검증 임워크 기반의 유사도 기반 그래 질의 처리 기 법을 제안한다. 계산량이 많은 그래 데이터의 특징에 맞는 필터링 방법을 제안하고, 후보 그래들을 효율으로 검증하기 한 기법을 제안한다. 한, 규모 데이터에서 실시간 분석이 가능할 수 있도록 MapReduce를 이용 하는 분산처리 기법을 제안하고, 실 데이터에 한 실험을 통해 본 논문에서 제안하는 방법이 유사도 기반 그래 질의 처리의 성능을 크게 개선함을 입증한다.
Abstract
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.
참고문헌 (20)
- X. Yan, "Gspan: Graph-based substructure pattern mining", ICDM, pp.721~724 (2002)
- C. Chen, "Mining graph patterns efficiently via randomized summaries", PVLDB, 2(1), pp.742~753 (2009)
- X. Yan, "Graph indexing:A frequent structure-based approach", SIGMOD Conference, pp.335~346 (2004)
- H. He, "Closure-tree: An index structure for graph queries", ICDE, pp.38~ (2006)
- C. Chen, "Towards graph containment search and indexing", VLDB, pp.926~937 (2007)
- P. Zhao, "Graph indexing: Tree + delta >= graph", VLDB, pp.938~949 (2007)
- L. Gravano, "Approximate string joins in a database (almost) for free", VLDB (2001)
- C. Xiao, "Ed-Join: an efficient algorithm for similarity joins with edit distance constraints", PVLDB, 1(1), pp.933~944 (2008)
- C. Li, "Efficient merging and filtering algorithms for approximate string searches", ICDE, pp.257~266 (2008)
- C. Li, "VGRAM:Improving performance of approximate queries on string collections using variable-length grams", VLDB (2007)
- H. Bunke, "Inexact graph matching for structural pattern recognition", Pattern Recognition Letters, 1(4), pp.245~253 (1983)
- A. Sanfeliu, "A Distance measure between attributed relational graphs for pattern recognition", IEEE transactions on systems, man, and cybernetics, 13(3), pp.353~362 (1983)
- G. Wang, "Efficiently indexing large sparse graphs for similarity search", Knowledge and Data Engineering, IEEE Transactions on, (99) (2010)
- X. Zhao, "Efficient Graph Similarity Joins with Edit Distance Constraints", ICDE (2012)
- Z. Zeng, "Comparing stars : On approximating graph edit distance", PVLDB, 2(1), pp.25~36 (2009)
- P. Hart, "A Formal Basis for the Heuristic Determination of Minimum Cost Paths", IEEE Transactions on Systems Science and Cybernetics, 4(2), pp.100~107 (1968)
- K. Riesen, "Speeding up graph edit distance computation with a bipartite heuristic", MLG (2007)
- 김진욱, "편집거리 계산을 위한 맵리듀스 알고리즘", 한국차세대컴퓨팅학회 논문지, 11(2), pp.79~89 (2015), 한국차세대컴퓨팅학회
- 최병은, "이기종 빅데이터 분석을 위한 Spark 기반 join 기법", 한국차세대컴퓨팅학회 논문지, 11(6), pp.91~99 (2015), 한국차세대컴퓨팅학회
- 김경율, "영상 대비와 특징추출 알고리즘 성능평가의 관계 분석", 한국차세대컴퓨팅학회 논문지, 8(5), pp.6~20 (2012), 한국차세대컴퓨팅학회