Divide and conquer approach for efficient pagerank computation

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Divide and conquer approach for efficient pagerank computation

Full text

Pdf (388 KB)

Source

ACM International Conference Proceeding Series; Vol. 263 archive
Proceedings of the 6th international conference on Web engineering table of contents

Palo Alto, California, USA

SESSION: Session 9: searching table of contents

Pages: 233 - 240

Year of Publication: 2006

ISBN:1-59593-352-2

Authors

Prasanna Kumar Desikan	University of Minnesota, Minneapolis, MN
Nishith Pathak	University of Minnesota, Minneapolis, MN
Jaideep Srivastava	University of Minnesota, Minneapolis, MN
Vipin Kumar	University of Minnesota, Minneapolis, MN

Sponsor

ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 110, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTex EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1145581.1145629 What is a DOI?

ABSTRACT

PageRank is a popular ranking metric for large graphs such as theWorld Wide Web. Current research techniques for improving computational efficiency of PageRank have focussed on improving the I/O cost, convergence and parallelizing the computation process. In this paper, we propose a divide and conquer strategy for efficient computation of PageRank. The strategy is different from contemporary improvements in that itcan be combined with any existing enhancements to PageRank, giving way to an entire class of more efficient algorithms. Wepresent a novel graph-partitioning technique for dividing thegraph into subgraphs, on which computation can be performed independently. This approach has two significant benefits. Firstly, since the approach focuses on work-reduction, it can be combined with any existing enhancements to PageRank. Secondly, the proposed approach leads naturally into developing an incremental approach for computation of such ranking metrics given that these large graphs evolve over a period of time. The partitioning technique is both lossless and independent of the type (variant) ofPageRank computation algorithm used. The experimental results for a static single graph (graph at a single time instance) as well as for the incremental computation in case of evolving graphs, illustrate the utility of our novel partitioning approach. The proposed approach can also be applied for the computation of anyother metric based on first order Markov chain model.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	L. Page, S. Brin, R. Motwani and T. Winograd The PageRank Citation Ranking: Bringing Order to the Web Stanford Digital Library Technologies, January 1998.
	2	Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.668-677, January 25-27, 1998, San Francisco, California, United States
	3	P. Desikan, J. Srivastava, V. Kumar, P.-N. Tan, Hyperlink Analysis - Techniques & Applications, Army High Performance Computing Center Technical Report, 2002.
	4	Taher H. Haveliwala, Topic-sensitive PageRank, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511513]
	5	Divya Padmanabhan , Prasanna Desikan , Jaideep Srivastava , Kashif Riaz, WICER: A Weighted Inter-Cluster Edge Ranking for Clustered Graphs, Proceedings of the The 2005 IEEE/WIC/ACM International Conference on Web Intelligence (WI'05), p.522-528, September 19-22, 2005 [doi>10.1109/WI.2005.166]
	6	Taher Haveliwala. "Efficient Computation of PageRank," Stanford University Technical Report, September 1999.
	7	Yi-Jen Chiang , Michael T. Goodrich , Edward F. Grove , Roberto Tamassia , Darren Erik Vengroff , Jeffrey Scott Vitter, External-memory graph algorithms, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.139-149, January 22-24, 1995, San Francisco, California, United States
	8	Yen-Yu Chen , Qingqing Gan , Torsten Suel, I/O-efficient techniques for computing pagerank, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA [doi>10.1145/584792.584882]
	9	A. Arasu, J. Novak, A. Tomkins, and J. Tomlin. PageRank computation and the structure of the web: Experiments and algorithms. In Poster presentation at the 11th Int. World Wide Web Conference, May 2002.
	10	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]
	11	P. Berkhin, A survey on PageRank computing, Internet Mathematics, Internet Mathematics, Vol 2 Issue 1(2005-2006).
	12	A. N. Langville and C. D. Meyer, Deeper inside PageRank, Internet Mathematics, 1 (2003-4), 335--380.
	13	S. Chien, C. Dwork, R. Kumar, D. Sivakumar, D. Simon, Link evolution: Analysis and algorithms. First Workshop on Algorithms and Models for the Web-graph 2002.
	14	Google, http://www.google.com
	15	Glen Jeh , Jennifer Widom, Scaling personalized web search, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775191]
	16	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]