Distributed link-based ranking in P2P Web retrieval

One of the main differences between modern search engines and traditional ones is the adoption of link-based ranking algorithm in ordering Web documents. Google has claimed that it is its link-based ranking algorithm, PageRank that has made the quality of its search results superior. However, existing link-based ranking algorithms are mostly logically centralized although techniques of distributed data management and load balancing have been used in search engines to improve the performance and availability of the systems. With the scale of the Web becoming larger and larger, the scalability of traditional search engines is very much limited by the current centralized algorithms, models, and architectures. The centralization in link-based ranking computation has brought in several critical problems that are hard to solve: centralized bottleneck and single point of failure, prohibitively high computation cost, lag in availability of fresh information, etc. In response to these problems, we have explored several approaches to address them: incremental computation, new distributed model based algorithms, and a common decentralized framework. In particular, we have proposed the new distributed approach based on a Layered Markov Model to distinguish stochastic transitions among Web sites and Web documents. Based on this model, we propose two different methods for computation of ranking of Web documents, a centralized one and a decentralized one. Both produce a well-defined ranking for a given Web graph. We then formally prove that the two approaches are equivalent. This provides a theoretical foundation for decomposing link-based rank computation and makes the computation for a Web-scale graph feasible in a decentralized fashion, such as required for Web search engines having a Peer-to-Peer (P2P) architecture. Furthermore, personalized rankings can be produced by adapting the computation at both the local layer and the global layer. The empirical results show that the ranking generated by our model is qualitatively comparable to or even better than the ranking produced by PageRank. On the other hand, the common framework for Peer-to-Peer Information Retrieval (IR) is situated in a more general scope. It captures the essence of individual models and describes the overall behavior of P2P Web retrieval systems. Such a framework characterizes notions like ranking, ranking aggregation and combination, etc. Algebraic properties of them are explored and guidelines for ranking computation based on those properties are proposed. Application scenarios are then given to show how different search engines and their algorithms can be formalized within this common framework. As two representative examples, heuristic and model-guided distributed ranking compositions are elaborated to demonstrate the power and potentials of this common framework. Results of my research work can be used in modern search companies to build a truly distributed search engine system; they also form a solid base for future research on topics of distributed ranking computation for P2P Web retrieval, including specific layered decentralized algorithms, and problems within the general common framework.

Using a Layered Markov Model for Decentralized Web Ranking

Karl Aberer, Jie Wu

The link structure of the Web graph is used in algorithms such as Kleinberg's HITS and Google's PageRank to assign authoritative weights to Web pages and thus rank them. In HITS, a solid theoretical model is lacking and the algorithm often leads to non-unique or non-intuitive rankings where zero weights may inappropriately be assigned to parts of a network. In PageRank, a model of random walks is proposed such that the theory about the stationary state of a Markov process can be applied to assure convergence to a unique ranking. Both algorithms require a centralized computation of the ranking if used to rank the complete Web graph. In this paper, we propose a new approach based on a Layered Markov Model to distinguish transitions among Web sites and Web documents. Based on this model, we propose two different approaches for computation of ranking of Web documents, a centralized one and a decentralized one. Both produce a well-defined ranking for a given Web graph. We then formally prove that the two approaches are equivalent. This provides a theoretical foundation for decomposing link-based rank computation and makes the computation for a Web-scale graph feasible in a decentralized fashion, such as required for Web search engines having a peer-to-peer architecture. Furthermore, personalized rankings can be produced by adapting the computation at both the local layer and the global layer. Our empirical results show that the ranking generated by our model is qualitatively comparable to or even better than the ranking produced by PageRank.

2004

A high-performance distributed hash table for peer-to-peer information retrieval

Fabius Klemm

This thesis describes our research results in the context of peer-to-peer information retrieval (P2P-IR). One goal in P2P-IR is to build a search engine for the World Wide Web (WWW) that runs on up to hundreds of thousands or even millions computers distributed all over the world. The idea is not only to distribute the content, e.g., web pages, but also an index for searching this content. The main focus of this thesis lies on designing an overlay network that is capable of transporting data between the different parts of such a distributed search engine. We built a Distributed Hash Table (DHT) that is able to sustain and efficiently handle high traffic loads, which are typically generated by a distributed IR application. We first analyze the behavior of a state-of-the-art DHT under heavy load and show that a DHT can suffer a so-called "congestion collapse" if it does not have a congestion control mechanism. We propose different ways of integrating congestion control into DHTs to achieve stable behavior of the system under heavy load. We then look into mechanisms for increasing the throughput of a DHT by adapting its routing function to perceived congestion. We propose an algorithm that avoids congested parts of the DHT and thus increases the throughput by exploiting underutilized resources. We evaluate our fully operational DHT prototype using a ModelNet cluster and the PlanetLab testbed to assess the performance of the proposed algorithms. Furthermore, we describe an architecture of a P2P search engine for the WWW. We propose mechanisms to create a highly distributed document index. The main idea is to split the index into very small parts by using so-called highly discriminative keys. We thus achieve an extremely distributed storage of the index, which allows for high parallelism during indexing and querying. We evaluate the performance of our indexing approach with a P2P-IR prototype, which is built on top of our high-performance DHT.

EPFL2008

A high-performance distributed hash table for peer-to-peer information retrieval

Fabius Klemm

EPFL2008