서지주요정보
효율적인 서브그래프 매칭을 위한 연결정보 기반 프레임워크 = A connection-based framework for efficient subgraph matching in a large graph
서명 / 저자 효율적인 서브그래프 매칭을 위한 연결정보 기반 프레임워크 = A connection-based framework for efficient subgraph matching in a large graph / 김상재.
저자명 김상재 ; Kim, Sang-Jae
발행사항 [대전 : 한국과학기술원, 2011].
Online Access 원문보기 원문인쇄

소장정보

등록번호

8022745

소장위치/청구기호

학술문화관(문화관) 보존서고

MCS 11006

SMS전송

도서상태

이용가능

대출가능

반납예정일

초록정보

Subgraph matching is to find all subgraphs isomorphic to a query graph in a database graph. Since subgraph matching problem is NP-complete, most conventional works use a filter-and-verification frame-work. In this framework, they reduce the number of candidate vertices to be used as input to subgraph isomorphism test by comparing vertex signatures. After that, they verify whether candidate subgraphs are isomorphic to the query graph by checking connections between candidate vertices. Connectivity information between vertices can reduce the cost of the query process. We propose a connection-based framework for efficient subgraph matching in a large graph. It maintains connectivity information as well as vertex signatures of the database graph. Both candidate vertex and connection checking operations in the verification phase can be reduced. The experimental result shows that our method significantly outperforms existing approaches for subgraph matching in a large graph.

그래프데이터베이스에서 주어진 쿼리 그래프와 동일한 모든 서브그래프를 찾는 연산을 서브그래프 매칭이라고 한다. 이러한 문제는 NP-Complete이기 때문에 일반적으로 연산 비용을 줄이기 위해 filter-and-verification 프레임워크와 휴리스틱에 기반한 검증 알고리즘을 사용한다. Filter-and-verification 프레임워크는 쿼리 그래프 정점에 대응되기 위한 필요조건을 검사해서 후보의 수를 줄인 후에 검증 알고리즘을 적용하는 방식이다. 기존 연구들은 정점 기반의 인덱스를 활용해 필터링 단계에서 효과적으로 후보의 수를 줄이는 데에 초점을 두었다. 하지만 전체 과정에서 검증 단계에서 발생하는 비용이 가장 큰 비중을 차지하기 때문에 보다 효율적으로 검증할 수 있는 방법이 필요하다. 검증 단계에서는 정점 간의 연결을 확인하는 연산이 가장 큰 비중을 차지한다. 검증 단계에서 발생하는 연결 검사의 수를 줄이기 위해 정점 간의 연결 정보를 활용할 수 있다. 본 연구에서는 서브그래프 매칭을 효율적으로 처리하기 위한 연결정보 기반의 프레임워크를 제안한다. 제안 방식은 정점 간의 연결 정보를 활용하기 위해 에지 기반의 인덱스를 사용한다. 필터링 단계에서는 필요 조건을 만족하는 정점과 직접적으로 연결된 정점만을 찾기 때문에 후보의 수를 줄일 수 있고, 검증 단계에서는 연결 정보를 활용해 연결 검사의 수를 효과적으로 줄일 수 있다. 제안 방식의 효율성과 효과를 보이기 위해 실험을 수행하였고, 실험 결과는 제안 방식이 기존 방식들보다 우수한 성능을 보였다.

서지기타정보

서지기타정보
청구기호 {MCS 11006
형태사항 iv, 28 p. : 삽도 ; 26 cm
언어 한국어
일반주기 저자명의 영문표기 : Sang-Jae Kim
지도교수의 한글표기 : 이윤준
지도교수의 영문표기 : Yoon-Joon Lee
학위논문 학위논문(석사) - 한국과학기술원 : 전산학과,
서지주기 참고문헌 : p. 25-26
주제 서브그래프 매칭
그래프 데이터베이스
Subgraph matching
graph database
QR CODE qr code