Index-based Searching for Isomorphic Subgraphs in Hypergraph Databases

Dae Geun Ha, Tae Wook Ha, Jung Hyuk Seo, Myoung Ho Kim

http://doi.org/10.5626/JOK.2019.46.7.697

A graph data type can represent relationships of objects in the real world and can be used for analyzing given relationships. A hypergraph is a generalized version of a normal graph where a hyperedge represents a relationship between more than or equal to two objects. In this paper, we propose a method that searches isomorphic subgraphs in a data hypergraph to a given query hypergraph. In order to reduce high computational costs of subgraph isomorphism search, previous studies have explored candidates that might be possible answers for each query node and return isomorphic subgraphs that consist of a combination of candidates. In this research, to enhance search performance, we have decomposed a query hypergraph into several subgraphs and discovered the candidates for each subgraph with the proposed structural index, and the proposed search algorithm checks subgraph isomorphism. With real-world datasets, experimental results demonstrate that the search response time of the proposed method is at least 10 times faster than the existing methods.