Peer-to-peer systems, search engines, combining fuzzy information, information retrieval.
Most major search engines are currently based on cluster architectures, with large numbers of low-cost servers located at one or a few locations and connected by high-speed LANs [2]. Recently, there has been a lot of interest in using peer-to-peer (P2P) architectures to provide large-scale services, and several groups have proposed scalable substrates for P2P applications [10,12,14,17].
Here, we study the problem of building a P2P-based search engine for massive document collections on top of such a substrate. We describe a prototype system called ODISSEA (Open DIStributed Search Engine Architecture) that is currently under development in our group. ODISSEA provides a highly distributed global indexing and query execution service that can be used for content residing inside or outside of a P2P network. ODISSEA is different from most other approaches to P2P search in that it assumes a two-tier search engine architecture and a global index structure that is distributed over the nodes of the system. In this short paper, we give an overview of the proposed system and discuss some basic design choices. We also discuss some preliminary simulation results for distributed query processing on a terabyte-size web page collection that indicate good scalability for our approach. An expanded version of this paper appears in [15], and updated information is available here.
ODISSEA is a distributed global indexing and query execution service, i.e., a system that maintains a global index structure under document insertions and updates and node joins and failures, and that executes simple but general classes of search queries in an efficient manner. This system provides the lower tier of a proposed two-tier search infrastructure. In the upper tier, there are two classes of clients that interact with this P2P-based lower tier:
There are two main differences that distinguish ODISSEA from other P2P search systems. First, the assumption of a two-tier architecture that aims to give as much freedom as possible to clients to implement their own ranking policies. We note however that there are limits to this freedom as discussed later. The second difference is our assumption of a global inverted index structure. Most current approaches (see [11] for an exception) for P2P search assume a local index, where each node maintains an index for its local documents, and queries have to be broadcast to all, or usually at least a significant fraction, of the nodes, in order to get the best results.
Figure 1: ODISSEA as a web search infrastructure, with a web crawler as update client, and a client-based and a web service-based search client.
Figure 1 shows the basic design. We decided to implement the system on top of an underlying global address space provided by a DHT structure, in particular Pastry [12]. Each object is identified by a hash of its name, where the name is the URL of a document or a string such as index://chair for the index structure for the term ``chair'', and is assigned a location determined by the DHT mapping scheme. Thus, the only way to move an object is to rename it, resulting in a mapping to a random other node. We have four main applications in mind:
Two-tier approach: Given the increases in speed and bandwidth of desktop systems, we see the potential for a rich variety of novel search tools and interfaces that exploit client computing resources, and that rely on a powerful lower-level web search infrastructure. These tools may perform a large number of web server or search engine accesses during a single user interaction, in order to prefetch, analyze, aggregate, and render content from various sources. Early examples of client-based tools are the Alexa and Google Toolbars, Leticia and PowerScout [8], or tools built with the Google API.
The proposed system would provide such a lower-level search infrastructure, with a powerful open and agnostic API that is accessed by client- and proxy-based tools. By agnostic, we mean an API that is not limited to a single method for ranking pages (e.g., the Google API, which returns pages according to Google's ranking strategy), but that allows clients to implement their own ranking. There clearly are limits and trade-offs to this goal. The most general solution of performing the ranking at the client requires large amounts of data to be transferred. On the other hand, we believe that limited but powerful classes of ranking functions can be supported by providing appropriate ``hooks'' in the system. One of our main research goals is to explore this trade-off.
Global vs. local index: In a local index organization, each node creates its own index for its local documents. Thus, each node has its own postings list for common words such as ``chair'' or ``table'', and a query ``chair table'' is broadcast to all nodes and the results are combined. In a global index organization, each node holds a global postings list for a subset of the words, as determined, e.g., by hashing. Thus, a query ``chair table'' is routed to the node holding the list for ``chair'' (the shorter list), which sends its complete list to the node holding ``table''.
The main problem with local indexes is that all or most nodes are contacted for most queries, and thus they are unlikely to scale beyond a few hundred nodes. There have been attempts to overcome this issue by routing queries only to nodes likely to have good results or those in the vicinity [4, 6, 13]. However, we do not believe that this approach will work well if result quality is a major concern. To see this, consider the current web, where an approach based on local indexes at each site would be either extremely inefficient or give very poor answers.
With a global index, on the other hand, large amounts of data are transmitted, since large document collections result in lists of megabytes or more for many common words. This problem has led some people to reject global indexes as unrealistic for environments with limited bandwidth. However, we believe this problem can be overcome with smart algorithmic techniques. Some work in this direction was recently described in [7, 11], where Bloom filters and other ideas are used to decrease the cost of intersecting lists over the network, though this only improves results by a small factor. In our approach, we are using distributed query execution algorithms based on ideas by Fagin and others [5] that asymptotically reduce communication. Thus, only a small fraction of the inverted lists is usually transmitted. We believe that these techniques, combined with good query optimization, will allow interactive response times on terabyte data sets.
Search engines typically process queries by computing a score for each document containing all the query terms, and then returning the k documents with the highest score. There are many factors that may contribute to this score, including standard term-based scores, global page scores due to Pagerank [3] and similar methods, or distances between search terms in the documents. The simplest approach is to evaluate the score function for all documents in the intersection of the inverted lists for the search terms, resulting in transmissions of multiple megabytes. However, recent work by several groups [5] shows how to evaluate top-k queries without scanning over the entire intersection. The algorithms, originally proposed for multimedia queries (e.g., image retrieval) presort the inverted lists by the term-specific scores that contribute to the final score, and then attempt to determine the top k results by only accessing a small prefix of the lists and performing a limited number of random lookups on the list. In particular, for queries with two terms, only a number of postings proportional to the square root of the total number of documents is usually transmitted [5]. We note that slightly similar techniques has also been proposed in the IR community [1, 9], but these usually access a much larger fraction of each list as they seek to avoid any random lookups.
We have designed a simple distributed protocol based on these techniques, and have measured the performance of this protocol based on a trace from the Excite web search engine and a real data set of 120 million web pages that we crawled from the web. Table 1 shows average results for 781 queries with two keywords, excluding stop words and very rare words. There are three columns of data, corresponding to queries with a very small, median, and very large length of the shorter of the two lists. The first line shows the average length of the shorter lists, which is the cost of the basic algorithm. The next lines show the number of postings sent from the shorter to the longer list, and vice versa. The final three lines show the total number of bytes transmitted and the time in milliseconds; these were computed by assuming 8 bytes per posting and a TCP performance model from [16] that models the effect of the TCP congestion window in a typical wide area environment, with bandwidths of 400 kilobits and 2 megabits per second. The score function was a standard cosine measure, and similar results are obtained when including a normalized Pagerank score. We note that these results will be somewhat worse for even larger collections, and for queries with more keywords or with phrases. On the other hand, there are several additional optimizations that we are currently testing.
shortest 20% |
middle 20% |
longest 20% |
|
Lists |
9,616 |
227,669 |
3,460,122 |
| A to B | 2,156 |
4,477 |
4,242 |
| B to A | 8,097 |
4,388 |
4,136 |
| Total bytes sent | 82,024 |
70,920 |
67,024 |
| Time 400 kbps | 2,372 |
2,159 |
2,068 |
| Time 2 mbps | 849 |
832 |
814 |
Table 1: Communication costs of the protocol.
We thank Hojun Lee and Malathi Veeraraghavan for their help with the TCP performance model. This research was partly supported by NSF CAREER Award NSF CCR-0093400.