서브그래프 구조를 이용한 효율적인 하이퍼그래프 질의 시스템

Abstract

다수의 객체가 하나의‘관계’로 연결된 것을 표현할 수 없는 일반그래프의 한계에 따라 하이퍼그래프 개념이 생겨났다. 하이퍼에지로 다양하고 복잡한 관계들의 표현이 가능해짐으로써, 효율적인 저장뿐만 아니라 데이터를 활용할 질의 시스템의 필요성이 요구된다. 하지만, 조사결과 노드 레이블이 적용된 하이퍼그래프를 위한 질의 시스템은 일반그래프에 대한 여러 질의 알고리즘에 비해 연구된 것이 없다. 본 논문에서는 기존에 노드 레이블이 적용된 대형 일반그래프에 대한 최신 질의 알고리즘 중 경로 기반 질의 검색 SPath와 트리 기반 질의 검색 TurboISO를 요약 설명하고, 하이퍼그래프 질의 시스템 설계에 그대로 적용할 시 하이퍼에지 특성에 의해 발생하는 문제들을 제시한다. 문제 해결을 위해 하이퍼그래프 질의 시 하이퍼에지 정보를 포함하여 서브그래프 단위로 매치 여부를 검사하는 질의 알고리즘을 제시하고 실험을 통해 효율성을 검증한다.