동형 서브그래프 질의 처리를 위한 효율적인 그래프 경로 기반 인덱싱 기법

김동현; 송광호; 김유성; DongHyun Kim; Kwangho Song; Yoo-sung Kim; 하태욱; 김명호; Tae Wook Ha; Myoung Ho Kim

연구문헌

국내 논문지

홈 > 연구문헌 > 국내 논문지 > 한국정보과학회 논문지 > 정보과학회 컴퓨팅의 실제 논문지 (KIISE Transactions on Computing Practices)

정보과학회 컴퓨팅의 실제 논문지 (KIISE Transactions on Computing Practices)

Current Result Document : 4 / 14 이전건 다음건

한글제목(Korean Title)	동형 서브그래프 질의 처리를 위한 효율적인 그래프 경로 기반 인덱싱 기법
영문제목(English Title)	An Efficient Path-based Indexing Technique for Subgraph Isomorphism Query Processing
저자(Author)	김동현 송광호 김유성 DongHyun Kim Kwangho Song Yoo-sung Kim 하태욱 김명호 Tae Wook Ha Myoung Ho Kim
원문수록처(Citation)	VOL 24 NO. 05 PP. 0245 ~ 0250 (2018. 05)
한글내용 (Korean Abstract)	동형 서브그래프 질의 처리(Subgraph isomorphism query processing)란 대용량의 여러 작은 그래프들 혹은 하나의 큰 그래프로 이루어진 그래프 데이터베이스에 대해 사용자로부터 주어진 질의 그래프와 구조적으로 동일한(isomorphic) 여러 서브그래프들을 찾아주는 과정이다. 기존 연구에서는 그래프 경로(path) 기반 인덱스와 각 경로에 대한 테이블 간 조인(join) 연산을 통해 질의를 처리하는 방법을 제안 하였다. 하지만 동일한 구조이거나 공통 에지(edge)를 가지는 경로들의 경우 데이터 그래프에 대한 중복정보를 가져 인덱스의 크기가 불필요하게 커지는 문제점이 있다. 본 논문에서는 패스 코드(path-code)와 유니크 코드를(unique-code)를 이용하여 데이터 그래프에 대한 중복 정보를 제거하는 효율적인 경로 기반 인덱싱 방법을 제안한다. 실험에서는 기존 경로 기반의 인덱싱 방법과 비교하여 제안한 인덱싱 방법의 효율성을 보인다. 또한, 실제 그래프 데이터베이스에 대해 제안한 방법이 빠른 질의 처리를 가짐을 보인다.
영문내용 (English Abstract)	Given a graph database which consists of small graphs or a single large graph, the subgraph isomorphism query processing finds all subgraphs isomorphic to a query graph from a user. The previous research proposed a query processing method using join operations between tables, which include path information of a database graph, from a path-based index. However, there is a problem if the index contains a lot of duplicate information because of paths that are the same or have common edges. In this paper, we propose an efficient path-based indexing technique without duplicate information using a path-code and a unique-code of a path. In the experiments, we show the effectiveness of our proposed method by comparing it with the previous indexing method. We also show that our method does a fast query processing on real graph databases.
키워드(Keyword)	비디오 주석 생성 시스템 자동 비디오 주석 생성 외부 인식기 연동 API 상황 인식용 지상 실측 데이터 제작 외부 이미지 인식기 연동 video annotation system automatic video annotation generation third-party detector linking API ground truth data for event recognition third-party image detector linking 그래프 동형 서브그래프 질의 처리 경로 기반 인덱싱 패스 코드 유니크 코드 graph subgraph isomorphism query processing path-based index path-code unique-code
파일첨부	PDF 다운로드