서지주요정보
LatticeISO : 구조적 인덱스를 활용한 동형 서브 하이퍼그래프 검색의 효과적인 처리 = LatticeISO : efficient sub-hypergraph isomorphism search using a structural index
서명 / 저자 LatticeISO : 구조적 인덱스를 활용한 동형 서브 하이퍼그래프 검색의 효과적인 처리 = LatticeISO : efficient sub-hypergraph isomorphism search using a structural index / 하대근.
저자명 하대근 ; Ha, Dae-Geun
발행사항 [대전 : 한국과학기술원, 2019].
Online Access 원문보기 원문인쇄

소장정보

등록번호

8033865

소장위치/청구기호

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

MCS 19034

휴대폰 전송

도서상태

이용가능

대출가능

반납예정일

초록정보

Graph model has been successfully used in modeling relationship of entities that is hard to be represented in traditional relational database, and network analysis. Hypergraph model is generalized version of normal graph where the hyperedge can represent relationship between more than two entities. Subgraph isomorphism is one of the fundamental quries in the graph database system. Most of existing subgraph isomorphism search mehod have been developed for normal graph model. Some previous studies extend Ullman's algorithm to hypergraph model, but they have some limitations. First, since the selection / verification process is performed at the node level, information about neighboring nodes is hard to be stored, and thus many accesses to unnecessary data nodes occur. Second, if you do not use an index in the selection process, or if you use an index at the label level, you will not be able to reduce the number of candidates effectively. In this paper, we solve these problems through selection / verification processes at a one-hop level different from existing ones and devising indexes that use structure information around nodes as keys.

그래프는 기존의 관계형 데이터베이스에서 나타내기 어려운 엔티티간의 관계를 모델링하고 네트워크를 분석하는 데 주로 사용되어져왔다. 하이퍼그래프는 그래프의 일반화된 모델로서 하나의 하이퍼에지가 3개 이상의 엔티티가 참여하는 관계를 나타낼 수 있다. 동형 서브그래프 검색 알고리즘은 그래프 데이터베이스 시스템에서 주로 쓰이는 기본적인 질의중 하나로서 주로 일반 그래프에 대해 연구되어 왔다. Ullmann의 동형 서브그래프 알고리즘을 하이퍼그래프로 확장한 선행 연구들이 있지만 몇 가지 한계점을 가지고 있다. 첫번째로 선별/검증 과정이 노드 수준에서 이루어지기 때문에 주변 노드에 대한 정보가 저장되기 어려워 불필요한 데이터 노드로의 접근이 다수 발생한다. 두번째로 선별 과정에서 인덱스를 사용하지 않았거나, 라벨 수준에서 인덱스를 사용했을 경우 효과적으로 후보의 수를 줄이지 못한다. 본 학위논문에서는 노드 주변의 구조 정보를 키로 사용하는 인덱스를 고안/활용하고, 기존과 다른 1-홉(one-hop) 수준에서의 선별/검증 과정을 통해 이들 문제를 해결하고, 효율적인 동형 서브 하이퍼그래프 검색 알고리즘을 제안하고자 한다.

서지기타정보

서지기타정보
청구기호 {MCS 19034
형태사항 iv, 37 p. : 삽도 ; 30 cm
언어 한국어
일반주기 저자명의 영문표기 : Dae-Geun Ha
지도교수의 한글표기 : 김명호
지도교수의 영문표기 : Myoungho Kim
학위논문 학위논문(석사) - 한국과학기술원 : 전산학부,
서지주기 참고문헌 : p. 33-34
주제 하이퍼그래프
동형 서브하이퍼그래프 검색
그래프
동형 서브그래프 검색
격자 인덱스
Ohop
분해 후 조인 전략
hypergraph
subhypergraph isomorphism
graph
subgraph isomorphism
lattice index
Ohop
decompose and join strategy
QR CODE qr code