Graphs are everywhere from a biological network to the World Wide Web, and they are usually enormous. As graph patterns represent various characteristics of the graph, diverse interesting graph mining applications rely on graph pattern analyses. In this dissertation, we propose scalable distributed algorithms for three graph pattern queries that are the basic building blocks of many other graph pattern queries. The three pattern queries are the triangle pattern query, the subgraph pattern query, and the connected component pattern query. The proposed algorithms are based on vertex coloring and pre-partitioning for balancing the workload and minimizing the size of intermediate data and the number of rounds.
생물학 네트워크부터 월드 와이드 웹까지, 우리 주변에 그래프는 어디에나 존재하고, 그 크기는 대게 매우 크다. 그래프 패턴이 그래프의 다양한 특성을 나타냄에 따라, 다양한 흥미로운 그래프 마이닝 응용들이 그래프 패턴 분석을 필요로 한다. 이 논문에서는, 다양한 그래프 패턴 질의의 기본 구성 요소인 세 가지 그래프 패턴 질의를 소개하고, 이들을 위한 확장 가능한 분산 알고리즘을 제안한다. 세 가지 기본 그래프 패턴들은 삼각형 패턴 질의, 서브그래프 패턴 질의, 그리고 연결 요소 패턴 질의 등 이다. 제안하는 알고리즘은 정점 색칠 기법과 그래프 사전 분할 기법을 통해 작업 부하를 고르게 분산하고 중간 데이터와 반복수행 회수를 최소화한다.