Fast Algorithm for Top-k Personalized PageRank Queries with Layered Graphs


Title Fast Algorithm for Top-k Personalized PageRank Queries with Layered Graphs
Yongjin Kwon, Sang-goo Lee
Year 2012 / 08
Keywords layered graph, Personalized PageRank, top-k query processing, online processing, graph networks
Acknowledgement NRF
Publication Type International Conference
Publication Proceeding of the 35th International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR 2012), pp. 1027-1028
Link url


In recent years, an efficient method of performing analyses and computations on graph networks, regarding recent and up-to-date data, has been needed due to continuous growth of datasets. Per- sonalized 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 adopt up-to-date 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 paper, we suggest a novel algorithm, ProbScoring, an approximate method of finding the top-k nodes at query time, that leverages the advantages of layered graphs. ProbScoring is far from those issues, and it is empirically verified that ProbScoring is a fast and accurate method.