Conceptually, a graph consists of a set of vertices and edges where both vertices and edges may have attributes to represent complex information associated with themselves. There are a lot of real-world datasets, which can be easily expressed as graphs. For example, it is natural to represent computer networks, food webs, protein interactions, and social networks as graphs. From the users` point of view, the main concern is how to quickly find information they needed from these graph datasets after issuing graph-structured queries. The goal of this thesis is to provide efficient ways of processing graph queries over large graph datasets.
In this thesis, we focus on two types of graph query problems, i.e., subgraph matching and graph containment. We first answer to a subgraph matching query problem. The results of a subgraph matching query are all occurrences of the query in a target data graph. Since a target data graph typically has a lot of vertices, the main challenge of the problem is how to filter out unqualified vertices, which are not eligible to be mapped to vertices in the query. Here we analyze all possible vertex features, which are made of the combination of label distribution and connectivity information within two hops of neighbor of a vertex, and choose vertex features that are balanced with pruning power and extraction cost. Then, we propose a feature indexing method over the chosen vertex features, which is used for finding candidates for each vertex in query processing.
Meanwhile, due to potential errors and noises in real-world graph datasets, exact subgraph matching may be sometimes inappropriate in practice. Thus approximate subgraph matching is also required. In this thesis, we investigate an approximate subgraph matching model that allows missing edges. A simple solution is to first generate all query subgraphs from a query within a threshold and perform exact subgraph matching for each query subgraph separately. The main challenge of the approximate subgraph matching query problem is how to reduce the number of query subgraphs that are required to exact subgraph matching. We propose a sharing-based method, which is based on the observation that query subgraphs are highly overlapped each other and thus the matching results of one query subgraph can be computed from the matching results of the other query subgraph without subgraph matching from scratch. With the proposed method, the query processing performance is largely improved compared to the state-of-the-art approach.
In the second part of our work, we investigate efficient ways of processing graph containment queries. The results of a graph containment query are a subset of a set of target data graphs that contains the query. In this thesis, we treat multiple graph containment queries instead of a single query. For this problem, we use MapReduce, a parallel data processing framework, as a programming interface. Features, e.g., substructures for representing graphs, are also used to filter out unqualified graphs like vertices in a subgraph matching problem. The challenge of the problem with MapReduce is how to properly assign tasks for retrieving results to map/reduce functions and how to configure the size of features. We propose an ecient method that adaptively tunes a feature size at runtime, which also performs multiple feature set inclusion tests concurrently by the aid of an on-the-fly generated index. We show that the proposed method is scalable to the size of a cluster.
본 학위논문은 데이터셋과 질의가 모두 그래프 구조를 띄는 환경에서 그래프 질의를 효율적으로 처리하는 방법을 제안하고자 한다. 그래프는 기본적으로 정점 집합과 간선 집합으로 구성된다. 또한 정점과 간선은 속성을 가질 수 있다. 데이터베이스 분야에서 다루는 다양한 데이터와 최근 많은 이슈가 되고 있는 소셜 네트워크 데이터는 자연스럽게 그래프로 표현될 수 있다. 데이터베이스 연구자의 입장에서 본다면, 개체는 정점으로 표현하고 개체 간의 관계는 간선으로 표현할 수 있다. 또한 데이터가 가지고 있는 복잡한 정보는 정점이나 간선의 속성으로 표현할 수 있다. 이런 일련의 전환 과정은 단순하고 직관적이기 때문에 실세계의 많은 데이터를 그래프로 표현할 수 있다. 예를 들면, 컴퓨터 네트워크에서 컴퓨터나 라우터를 개체로 표현하고, 컴퓨터나 라우터간의 접속을 간선으로 표현한다면 보다 직관적으로 컴퓨터 네트워크를 바라볼 수 있다. 또한 생태학에서 먹이사슬 표현하거나, 사회학에서 사람 간의 교류를 표현하거나, 생물학에서 단백질 간의 상호작용을 표현할 때도 그래프를 이용한 모델링은 매우 유용하다.
한편 사용자 입장에서 가지는 주된 관심은 자신들이 취급하는 그래프 데이터셋에서 그들이 원하는 정보, 즉 그래프로 표현되는 질의의 결과를 빠르게 받아보는 것이다. 대상이 되는 데이터셋과 질의의 형태는 분야별로 다양하지만 이들 그래프 질의는 크게 두 가지 타입으로 분류할 수 있다. 첫 번째는 주어진 그래프 데이터에서 사용자가 관심을 가지는 정보가 어느 위치에서 발생하는지 즉, "그래프 질의가 대상 데이터 그래프의 어느 부분에 출현하는가?"이다. 이런 형태의 질의는 대상이 되는 그래프 데이터의 크기가 매우 클 때, 즉 많은 정점을 가지고 있을 때 어떻게 빠르게 찾을 것인가가 이슈이다. 두 번째는 여러 개의 그래프를 가지는 데이터셋에서, 예를 들면 화합물 데이터베이스와 같은 경우, "사용자가 관심을 가지는 정보를 포함하고 있는 모든 그래프"를 찾고 싶은 경우이다. 우리는 첫 번째 종류의 그래프 질의를 부분그래프 매칭 질의라고 부르고, 두 번째 종류의 그래프 질의를 그래프 포함 질의라고 부른다. 또한 데이터셋에서 그래프 질의를 찾을 때 정확히 일치하는 것을 찾을 것인지, 아니면 오차를 허용할 것인지에 따라 정확한 또는 근사 그래프 질의로 구분한다. 본 학위논문에서는 그래프 질의 중에서 1) 정확한 부분 그래프 매칭 2) 근사 부분그래프 매칭 3) 정확한 그래프 포함 질의 등 세 가지의 질의 종류에 대한 효율적인 처리 방법을 연구하고자 한다.
첫 번째로 정확한 부분그래프 매칭 질의 문제를 다룬다. 정확한 부분그래프 매칭 문제에서 이슈가 되는 것은 대상이 되는 데이터 그래프의 크기에 있다. 그 크기가 매우 클 때 즉, 포함된 정점의 갯수가 수 만에서 수 십만개가 있을 때 어떻게 효율적으로 질의 그래프의 각 정점에 매핑될 가능성이 있는 후보의 갯수를 줄일수 있을까 하는 것이다. 이를 위해 기존연구에서는 정점 주변의 레이블 분포를 추출하거나 정점 주변에서 특수한 형태의 연결 구조를 찾아내어 이를 해당 정점의 특징으로 삼았다. 이렇게 질의 그래프의 정점과 데이터 그래프의 정점을 비교할 때 정점이 가지고 있는 본연의 정보 즉, 레이블이나 차수 뿐만이 아니라 그 주변의 특징을 비교한다면 후보의 갯수를 확연히 줄일 수 있다. 하지만, 여기에는 한 가지 고려해야 할 사항이 있는데, 정점 주변의 정보를 많이 이용하기 위하여 복잡한 특징을 추출한다면 특징 자체를 뽑아내는 시간과 이를 비교하는 시간이 전체 질의를 처리하는 시간에서 많은 부분을 차지하게 되어 오히려 전체적인 성능의 저하를 가져 올 수 있다. 따라서, 정점 특징에 따른 가지치기 효과와 그 정점 특징을 추출하는 시간을 잘 고려하여 이들 간에 균형을 맞추는 것이 중요하다. 본 학위논문에서는 각 정점의 2-홉이내의 주변에서 추출할 수 있는 모든 특징을 나열하고 분석한다. 그리고, 그 중에서 시간 복잡도가 일정 수준 이하인 것을 선택하고 다른 정점 특징에 의해 커버될 수 있는 것들을 제외함으로써 추출비용에 대한 간접비를 줄이고자 노력한다. 우리가 제안하는 방법은 정점 특징의 가기치기 효과와 추출 비용간의 균형을 유지하기 때문에 기존 연구와 비교하여 좋은 성능을 보였다.
두 번째 문제는 근사 부분그래프 매칭 문제이다. 이 문제에서 우선 정의되어야 할 것은 "유사도"를 어떻게 측정할 것인가이다. 우리는 간선 거리를 를 정의하여 그것을 유사도의 측정 단위로 사용한다. 간선 거리란 하나의 그래프를 다른 그래프로 변환하기 위해 제거한 간선의 갯수를 말한다. 근사 부분그래프 매칭 문제를 해결하는 단순한 방식은 사용자로부터 입력받은 간선 거리 범위 내의 모든 질의 부분그래프를 생성한 다음, 그 각각과 동형인 부분그래프를 데이터 그래프에서 찾는 방법이다. 하지만 이 방법은 많은 시간을 필요로 하다. 왜냐하면 우선 동형을 찾는 문제 자체가 어려운 문제이며, 질의 부분그래프의 갯수도 원래 질의 그래프의 크기와 간선거리의 허용치에 따라 매우 많아 질 수 있기 때문이다. 우리가 제안하는 방식은 질의 부분그래프가 서로 간에 많은 부분에서 동일한 구조를 가지고 있다는 관찰 결과에서 아이디어를 얻는다. 그래서 격자 구조라 불리는 질의 부분그래프간의 포함 관계도를 구성한 다음, 최소의 갯수를 선택하여 전체 질의 부분그래프의 매칭 결과를 얻을 수 있도록 한다. 우리가 제안하는 방법은 기존 방식와 비교할 때 동형 문제를 풀어야 하는 질의 부분그래프의 갯수가 작거나 같음을 증명하였고 다양한 실험을 통해 우리가 제안한 방법이 좋은 성능을 보임을 확인하였다.
세 번째 문제는 그래프 포함 질의를 효율적으로 처리하는 문제이다. 이 문제는 그래프 질의 문제들 중에서 가장 많은 관련 연구가 진행되어 있다. 본 학위논문에서는 기존 연구에서 다루는 문제와 다르게 여러 개의 그래프 포함 질의를 처리하는 문제를 다룬다. 질의 집합의 크기가 1일때는 기존 연구와 동일한 문제가 된다. 하지만, 기존 연구 결과를 그래프 포함 질의 집합에 그대로 적용하는 데는 한계가 있다. 즉, 기존 연구 결과를 적용하려면 질의를 한 개씩 순서대로 처리하게 되는데 이는 중간 결과를 공유할 수 없어 비효율적이다. 또한, 기존 연구에서는 수만 개의 그래프가 포함된 데이터셋을 대상으로 그래프 포함 질의 문제를 다루고 있다. 하지만, 최근에 등장한 그래프 데이터셋의 크기는 수 천만개에 이를 정도로 매우 커서 한 개의 그래프 질의를 처리할 때도 기존 방법을 적용하는 데 한계가 있다. 우리는 매우 많은 그래프를 포함한 데이터셋을 효율적으로 다루기 위해 MapReduce라는 분산 프로그래밍 모델을 도입한다. MapReduce를 도입함으로써 클러스터를 이용할 때 발생하는 다양한 문제들, 예를 들면, 데이터 분산, 실패 복구 등의 문제를 직접 처리하지 않아도 된다. 우리는 그래프 포함 질의 집합을 효율적으로 처리하기 위해서 분산 컴퓨팅 환경에서 적응적으로 그래프 특징의 크기를 결정하는 방법을 제안하며, 알고리즘 내부에서 사용되는 여러 개의 집합 포함 문제를 빠르게 처리하기 위해 인덱스를 사용한 집합 포함 관계를 빠르게 체크할 수 있는 방법을 제안한다. 이를 통해 우리는 수천 만개의 그래프 데이터셋에 대해 수천 개의 그래프 포함 질의도 유연히 처리할 수 있음을 실험을 통해 확인할 수 있었다.
향후 그래프로 표현할 수 있는 데이터의 종류는 더욱 늘어 날 것이며 그 크기도 점점 커질 것이다. 따라서, 그래프 질의 처리 문제는 주요한 이슈가 될 것이다. 본 학위논문에서는 그래프 질의를 효율적으로 처리할 수 있는 방법을 제안했으며, 그 결과의 이용 가능성이 증대될 것으로 기대된다.
