Scalable peer-to-peer Web search using highly discriminative keys

Standard general-purpose Web retrieval relies on centralized search engines that do not realistically scale when applied to the exponentially growing number of documents available on the Web. By taking advantage of the resource sharing principle, Peer-to-Peer (P2P) techniques represent a promising architectural alternative for building decentralized Web search engines offering true Web-size scalability, provided that enough peers are available. However, in all such P2P approaches proposed so far, excessive network bandwidth consumption during retrieval, caused by the necessary transmission of possibly very long posting lists, was identified as the major bottleneck for implementing truly scalable P2P full-text Web retrieval. The main objective of the present research is thus to find a decentralized indexing/retrieval strategy that fully exploits the distributed computation possibilities provided by P2P networks, but keeps the required network bandwidth consumption scalable, while guaranteeing an acceptable retrieval quality. To address this problem we introduce a novel indexing/retrieval model based on Highly Discriminative Keys (HDKs), which correspond to carefully selected indexing terms and term sets associated with posting lists truncated to the top-k most relevant documents with respect to the associated key. Using HDKs for indexing thus increases the number of indexing features but, at the same time, strictly limits the size of the associated posting lists. When combined with an adequate retrieval model, this leads to strongly reduced network traffic. More precisely, our experimental results show that HDK-based indexing and retrieval lead to storage and bandwidth requirements that remain manageable with respect to the growth of document collection while preserving a fully acceptable retrieval quality.

Beyond term indexing: A P2P framework for Web information retrieval

Karl Aberer, Fabius Klemm, Vinh Toan Luu, Ivana Podnar, Martin Rajman

Web search over peer-to-peer (P2P) networks shows promise to become an alternative to the state-of-the-art search engines since P2P overlays offer means for decentralized search across widely-distributed document collections. However, the design of effective techniques for P2P indexing and retrieval raises a number of technical challenges due to potentially unscalable resource (e.g. bandwidth, storage) consumption. The paper presents a framework for full-text information retrieval in structured P2P networks and introduces a novel retrieval model based on highly discriminative keys—terms and term sets appearing in a restricted number of documents—that ensure efficient and scalable retrieval. Our goal is to design scalable techniques for building a global key index in structured P2P overlays for large document collections. We present experimental results that show acceptable indexing and retrieval costs while the retrieval quality is comparable to standard centralized solutions with BM25 relevance computation scheme.

2006

Distributed link-based ranking in P2P Web retrieval

Jie Wu

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.

EPFL2006

Scalable Peer-to-Peer Web Retrieval with Highly Discriminative Keys

Karl Aberer, Fabius Klemm, Vinh Toan Luu, Ivana Podnar, Martin Rajman

The suitability of peer-to-peer (P2P) approaches for full-text Web retrieval has recently been questioned because of the claimed unacceptable bandwidth consumption induced by retrieval from very large document collections. In this contribution we formalize a novel indexing/retrieval model that achieves high performance, cost-efficient retrieval by indexing with highly discriminative keys (HDKs) stored in a distributed global index maintained in a structured P2P network. HDKs correspond to carefully selected terms and term sets appearing in a small number of collection documents. We provide a theoretical analysis of the scalability of our retrieval model and report experimental results obtained with our HDK-based P2P retrieval engine. These results show that, despite increased indexing costs, the total traffic generated with the HDK approach is significantly smaller than the one obtained with distributed single-term indexing strategies. Furthermore, our experiments show that the retrieval performance obtained with a random set of real queries is comparable to the one of centralized, single-term solution using the best state-of-the-art BM25 relevance computation scheme. Finally, our scalability analysis demonstrates that the HDK approach can scale to large networks of peers indexing Web-size document collections, thus opening the way towards viable, truly-decentralized Web retrieval.

IEEE2007

Distributed link-based ranking in P2P Web retrieval

Jie Wu

EPFL2006