Top-k 개인화된 페이지랭크 질의 처리 알고리듬

Abstract

오늘날 그래프 데이터의 지속적인 축적과 생성으로 인해 그래프 데이터를 효율적으로 분석, 계산하여 새로운 데이터들을 빨리 결과에 반영하는 작업이 중요해지고 있다. 개인화된 페이지랭크는 북마크 혹은 출발 노드라 불리는 몇몇 주요 노드에 선호도를 부여하여 다른 노드들의 상대적 중요도 혹은 연관도를 계산하는 방법으로, 그래프 데이터를 이용한 대표적인 계산 방법 중 하나이다.

하지만 개인화된 페이지랭크를 계산하는 작업은 막대한 계산 비용을 초래한다. 많은 응용에서는 이 문제를 해결하기 위해 모든 혹은 일부의 출발 노드에 대한 개인화된 페이지랭크 값을 미리 계산하여 그 결과를 저장한 후, 필요할 때마다 그 결과를 읽어 들여 보여주는 방식을 이용한다. 하지만 이 방식은 대규모의 저장 공간이 필요하며, 새로운 데이터의 반영이 늦어지는 문제를 발생시킨다. 검색 로그나 소셜 네트워크처럼 실시간으로 데이터가 생성되는 시스템에서는 이러한 방식은 올바른 계산 결과를 보여준다고 하기 어렵다.

본 연구에서는 개인화된 페이지랭크를 사용하는 응용들이 주로 상위 k개의 노드를 활용하는 점과 약간의 오차가 허용된다는 점에 착안하여, 주어진 출발 노드의 분포에 대하여 개인화된 페이지랭크 값을 구하는 대신 상위 k개의 개인화된 페이지랭크 값을 갖는 노드들을 실시간으로 찾아주는 방법인 ProbScoring을 제시한다. 기존의 방법들이 선계산 방식을 이용하기 때문에 앞서 살펴본 저장 공간의 문제, 새로운 데이터의 반영 문제 등이 발생한 반면, 본 연구에서 제시하는 방법은 질의가 발생하는 시점에 실시간으로 빠르게 계산하는 방식을 이용하기 때문에 이러한 문제점이 생기지 않는다. 실시간 계산을 위해 본 연구에서는 계층화된 그래프의 개념을 도입하고, 계층화된 그래프와 개인화된 페이지랭크의 관계를 파악한다. 그리고 계층화된 그래프를 활용한 ProbScoring의 자세한 진행 과정을 설명한다. 실제 그래프 데이터를 대상으로 실험한 결과 ProbScoring은 선계산 방식 없이도 질의가 발생한 시점에 기존의 방법들보다 효율적으로 상위 k개의 노드를 찾아주는 동시에 높은 수준의 정확도를 보여준다. 결론적으로 ProbScoring은 선계산 방식 없이도 질의가 발생한 시점에 실시간으로 상위 k의 개인화된 페이지랭크 값을 갖는 노드들을 찾아준다.

In recent years, an efficient method of performing analyses and computations on graph networks, regarding newly created data, has been needed due to continuous growth of datasets. Personalized PageRank is one of the most well-known computation methods for graphs. Personalized PageRank computes the relative importance or relevance with respect to a set of given nodes, called start nodes or bookmark.

However, the online computation of Personalized PageRank on a massive size of datasets is infeasible due to its huge computational cost. So many applications have considered the way of precomputing Personalized PageRank for all or some nodes, keeping them in a secondary storage, and reading the results on demand. This method, though, has two problems; it requires an enormous size of storages and it is difficult to use new data to affect the results. For applications that cope with frequent updates to data such as search logs or social networks, the precomputation is not a suitable method.

In this thesis, the two observations can be noticed. One is that applications using Personalized PageRank mainly need to find the top-k nodes with the largest values of Personalized PageRank. The other is that an erroneous detection of a small number of nodes in the top-k is allowable. With these observations, I propose ProbScoring, an online approximate method of finding the top-k nodes with the largest values of Personalized PageRank with respect to a distribution of start nodes, rather than computing the Personalized PageRank for each node. While the previous methods have faced the challenges of storages of keeping precomputation results and hardness of utilizing new data, ProbScoring is far from those issues since it computes top-k nodes quickly at query time. For online computation, I introduce the notion of layered graph and discover the relationship between layered graph and Personalized PageRank. And I explain the process of ProbScoring using the layered graph. The experimental results verify that ProbScoring shows better efficiency and accuracy of finding top-k nodes than previous methods. In conclusion, ProbScoring is an online computation method of finding top-k nodes with the largest values of Personalized PageRank at query time without precomputation.