Paper Info
Title
Efficient and decentralized PageRank approximation in a peer-to-peer web search network
Abstract
PageRank-style (PR) link analyses are a cornerstone of Web search engines and Web mining, but they are computationally expensive. Recently, various techniques have been proposed for speeding up these analyses by distributing the link graph among multiple sites. However, none of these advanced methods is suitable for a fully decentralized PR computation in a peer-to-peer (P2P) network with autonomous peers, where each peer can independently crawl Web fragments according to the user's thematic interests. In such a setting the graph fragments that different peers have locally available or know about may arbitrarily overlap among peers, creating additional complexity for the PR computation.This paper presents the JXP algorithm for dynamically and collaboratively computing PR scores of Web pages that are arbitrarily distributed in a P2P network. The algorithm runs at every peer, and it works by combining locally computed PR scores with random meetings among the peers in the network. It is scalable as the number of peers on the network grows, and experiments as well as theoretical arguments show that JXP scores converge to the true PR scores that one would obtain by a centralized computation.
Year
Venue
Field
2006
VLDB
Data mining,PageRank,Graph,Search engine,Web mining,Peer-to-peer,Web page,Computer science,Database,Scalability,Computation
DocType
Citations 
PageRank 
Conference
14
0.75
References 
Authors
27
12
Name
Order
Citations
PageRank
Josiane Xavier Parreira179142.14
Debora Donato2166583.29
Sebastian Michel394658.72
Gerhard Weikum4127102146.01
Umeshwar Dayal584522538.92
Kyu-Young Whang62282716.85
David B. Lomet71986795.28
Gustavo Alonso85476612.79
Guy M. Lohman92846965.94
Martin L. Kersten103243509.01
Sang K. CHA11623123.99
Young-kuk Kim1224250.17