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) 수준에서의 선별/검증 과정을 통해 이들 문제를 해결하고, 효율적인 동형 서브 하이퍼그래프 검색 알고리즘을 제안하고자 한다.
