Graph Indexing for Label-Constrained Reachability Queries

Abstract

계속해서 발전하는 세계에서 우리는 간선에 레이블이 포함된 그래프로 표현된 소셜 네트워크, 세만틱 웹 및 인용 네트워크 데이터를 계속해서 접하게 된다. 이렇게 그래프 형태로 구축된 데이터 내의 지식은 기저의 그래프를 질의함으로서 영향력을 발휘한다. 기본적으로 수행되는 그래프 질의는 주어진 소스 정점과 타켓 정점간의 도달 가능성을 판별한다. 또한 해당 질의는 간선에 라벨이 부여된 그래프 형태에 대해서 대상 라벨 집합을 제한하는 형태로도 주로 수행된다. Valstar 등[SIGMOD-2017]에 의해 상기 문제가 제시되었으며, 그들은 해당 라벨 제한 질의를 빠르게 지원하는 landmark indexing이라는 방식을 제안하였다. 본 논문을 통해 우리는 간편하고 실제적이며 공간 효율적으로 처리할 수 있는 제한된 라벨 도달 질의 수행 방식을 소개한다. 다양한 종류의 그래프에 대한 실험을 통하여 우리가 제시한 질의 알고리즘이 상당한 수준의 공간 효율성을 보임을 확인한다. 또한 landmark indexing과 비교하였을 때 제안된 처리 방식의 질의 처리 시간 및 사용되는 공간이 개선되었음을 보인다.

In our ever-growing world, we are faced with graph data in social networks, semantic webs, or a citation network stored in an edge-labeled graph. A good deal of knowledge in such a graph-structured data can be leveraged by querying the underlying graph. A fundamental query determines reachability between a given source and a target. The reachability query in the edge-labeled graph often also involves constraining the label set. This problem has recently been addressed by Valstar et al.~[SIGMOD-2017], who proposed an approach called Landmark Indexing to support label-constrained queries faster. In this work, we introduce simple, practical, and space-efficient solutions for efficiently evaluating label-constrained reachability (LCR) queries. Experimental results on both real and synthetic graphs demonstrate significant space efficiency benefits of our solutions. In fact, our schemes improve upon both the query time and space usage in comparison with landmark indexing.