In this thesis, we research how to analyze big graphs which do not fit in a main memory or disks of a single machine. Many researches are currently being done on mining large graphs using distributed platforms. MapReduce is a famous distributed computing platform, and widely used for large-scale graph mining due to its simplicity and massive scalability. However, the design principle of MapReduce often has a constraint on data access when MapReduce is used for graph algorithms. MapReduce only supports sequential access to data while many graph algorithms require random access. For this reason, MapReduce has limitations for fast large-scale graph mining.
To solve this problem, we propose UNICORN, a graph mining package on top of an open source version of Bigtable called HBase. UNICORN decreases graph processing time by exploiting the random write characteristic supported by HBase. Our experiments show that UNICORN surpasses PEGASUS, the state-of-the-art large-scale graph mining platform, by an order of magnitude, e.g. up to 10.5 x for a graph with 68 billion edges.
빅 그래프 데이터는 유용한 정보를 얻기 위해 많은 분야에서 분석되고 있다. 예를 들어, 웹페이지의 정보, 소셜 네트워크의 정보, 위협 정보, 추천 정보, 특이사항 감지 등의 정보를 획득하기 위해 분석되고 있다. 따라서 거대한 그래프 데이터를 분석하는 일은 중요한 일이 되었다. 하지만, 기존 단일 시스템으로는 하나의 머신에서 해결 할 수 없을 정도의 크기를 가지고 있는 거대한 그래프 데이터를 처리할 수 없다. 이러한 거대한 그래프 데이터를 처리하기 위해서 분산 처리 시스템이 필요하다. 분산 처리 시스템의 대표적인 예로는 맵리듀스가 있다. 맵리듀스는 높은 확장성과 간결성 그리고 결함 내성을 갖추고 있기 때문에, 많은 그래프 마이닝 플랫폼에서 사용하고 있다. 그러나 맵리듀스는 배치 접근만을 제공하는 제약사항으로 인해 무작위 접근을 필요로 하는 대부분의 그래프 알고리즘에 대하여 문제점을 가지고 있다. 따라서 맵리듀스가 가지는 이러한 문제를 해결하기 위해서 본 논문은 디스크와 메모리를 동시에 사용하여 임의 접근을 할 수 있는 빅테이블을 이용하여 그래프 마이닝 플랫폼을 설계하였다.
