Distributed PageRank computation based on iterative aggregation-disaggregation methods

ABSTRACT

PageRank has been widely used as a major factor in search engine ranking systems. However, global link graph information is required when computing PageRank, which causes prohibitive communication cost to achieve accurate results in distributed solution. In this paper, we propose a distributed PageRank computation algorithm based on iterative aggregation-disaggregation (IAD) method with Block Jacobi smoothing. The basic idea is divide-and-conquer. We treat each web site as a node to explore the block structure of hyperlinks. Local PageRank is computed by each node itself and then updated with a low communication cost with a coordinator. We prove the global convergence of the Block Jacobi method and then analyze the communication overhead and major advantages of our algorithm. Experiments on three real web graphs show that our method converges 5-7 times faster than the traditional Power method. We believe our work provides an efficient and practical distributed solution for PageRank on large scale Web graphs.

REFERENCES

• 1: P. Boldi , S. Vigna, The webgraph framework I: compression techniques, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988752]
• 2: Andrei Z. Broder , Ronny Lempel , Farzin Maghoul , Jan Pedersen, Efficient pagerank approximation via graph aggregation, Proceedings of the 13th international World Wide Web conference on Alternate track papers & posters, May 19-21, 2004, New York, NY, USA [doi>10.1145/1013367.1013537]
• 3: Wei-Lu Cao , William J. Stewart, Iterative aggregation/disaggregation techniques for nearly uncoupled markov chains, Journal of the ACM (JACM), v.32 n.3, p.702-719, July 1985 [doi>10.1145/3828.214137]
• 4: Françoise Chatelin, Iterativ Aggregation/Disaggregation Methods, Proceedings of the International Workshop on Computer Performance and Reliability, p.199-207, September 26-30, 1983
• 5: P. Courtois and P. Semal. Block iterative algorithm for stochastic matrices. Linear Algebra and its Application, Vol 76, pages 59--70, 1986.
• 6: Nadav Eiron , Kevin S. McCurley , John A. Tomlin, Ranking the web frontier, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988714]
• 7: D. Gleich, L. Zhukov, and P. Berkhin. Fast parallel pagerank: A linear system approach. Technical report, Yahoo Corp., 2004.
• 8: Gene H. Golub , Charles F. Van Loan, Matrix computations (3rd ed.), Johns Hopkins University Press, Baltimore, MD, 1996
• 9: Ilse C. F. Ipsen , Steve Kirkland, Convergence Analysis of a PageRank Updating Algorithm by Langville and Meyer, SIAM Journal on Matrix Analysis and Applications, v.27 n.4, p.952-967, 2006 [doi>10.1137/S0895479804439808]
• 10: H. Kafeety, C. Meyer, and W. Stewart. A general framework for iterative aggregation/ disaggregation methods. In Proc. of the 4th Copper Mountain Conf. on Iterative Methods, 1992.
• 11: S. Kamvar, T. Haveliwala, and G. Golub. Adaptive methods for the computation of pagerank. Technical report, Stanford Univ., 2003.
• 12: S. Kamvar, T. Haveliwala, C. Manning, and G. Golub. Exploiting the block structure of the web for computing pagerank. Technical report, Stanford Univ., 2003.
• 13: Sepandar D. Kamvar , Taher H. Haveliwala , Christopher D. Manning , Gene H. Golub, Extrapolation methods for accelerating PageRank computations, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775190]
• 14: L. Kaufman. Matrix methods for queueing problems. SIAM J. Sci. Statist. Comput., 4(3):525--552, 1983.
• 15: M. Kendall and J. Gibbons. Rank Correlation Methods. Edward Arnold, London, 5 edition, 1990.
• 16: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Journal of the ACM (JACM), v.46 n.5, p.604-632, Sept. 1999 [doi>10.1145/324133.324140]
• 17: Amy Nicole Langville , Carl Dean Meyer, Updating pagerank with iterative aggregation, Proceedings of the 13th international World Wide Web conference on Alternate track papers & posters, May 19-21, 2004, New York, NY, USA [doi>10.1145/1013367.1013491]
• 18: A. Langville and C. Meyer. Deeper inside pagerank. Internet Mathematics, 1(3):335--380, 2005.
• 19: C. Lee, G. Golub, and S. Zenios. A fast two-stage algorithm for computing pagerank and its extensions. Technical report, Stanford Univ., 2003.
• 20: P. Lyman, H. Varian, J. Dunn, A. Strygin, and K. Swearingen. How much information project. Technical report, Univ. of California, Berkeley, 2003.
• 21: Ivo Marek , Petr Mayer, Iterative Aggregation/Disaggregation Methods for Computing Some Characteristics of Markov Chains, Proceedings of the Third International Conference on Large-Scale Scientific Computing-Revised Papers, p.68-80, June 06-10, 2001
• 22: I. Marek and P. Mayer. Convergence theory of some classes of iterative aggregation-disaggregation methods for computing stationary probability vectors of stochastic matrices. Linear Algebra and Its Applications, 363:177--200, 2003.
• 23: I. Marek and I. Pultarova. A note on local and global convergence analysis of iterative aggregation-disaggregation methods. Submitted to Linear Algebra and Applications, 2005.
• 24: C. D. Meyer, Stochastic complementation, uncoupling Markov chains, and the theory of nearly reducible systems, SIAM Review, v.31 n.2, p.240-272, June 1989 [doi>10.1137/1031050]
• 25: M. Neumann and R. Plemmons. Convergent nonnegative matrices and iterative methods for consistent linear systems. Numer. Math., 31:265--279, 1978.
• 26: L. Page, S. Brin, R. Motwani, and T. Winograd. The pagerank citation ranking: Bringing order to the web. Technical report, Stanford Univ., 1998.
• 27: G. Stewart, W. Stewart, and D. McAllister. A two stage iteration for solving nearly completely decomposable markov chains. Recent Advances in Iterative Methods, IMA Vol. Math. Appl. 60:201--216, 1993.
• 28: D. Szyld. The mystery of asynchronous iterations convergence when the spectral radius is one. Research Report 98--102, Temple Univ., 1998.
• 29: Y. Takahashi. A lumping method for numerical calculations of stationary distributions of markov chains. Technical Report B-18, Dept. of Information Sciences, Tokyo Institute of Technology, 1975.
• 30: H. Vantilborgh. The error of aggregation in decomposable systems. Technical Report R453, Philipps Research Laboratory, Brussels, Belgium, 1981.
• 31: Y. Wang and D. DeWitt. Computing pagerank in a distributed internet search engine system. In Proc. of VLDB'04 Conf., pages 420--431, 2004.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process

General Terms:
Algorithms, Performance

Keywords:
PageRank, block Jacobi, distributed search engines, iterative aggregation-disaggregation