Distributed web search
Yuan Wang, David J. DeWitt · 2004
The explosive growth of the Web has dramatically increased the amount of information that can be accessed by web users. Consequently, the problem confronting web users is that it can be exceedingly difficult to locate high-quality resources that are relevant to their information requests. Thus, Web search engines such as Google, AltaVista, etc., which make use of hyperlink structure for discovering high-quality information on the Web, are widely used. Existing Internet search engines use crawlers to collect web pages. Page quality is measured on central servers, where user queries are also processed. This dissertation argues that using crawlers has a list of disadvantages. Most importantly, crawlers do not scale. Even Google, the leading search engine, indexes less than 1% of the entire Web. This dissertation proposes a distributed search engine framework, in which every web server answers queries over its own data. Results from multiple web servers will be merged to generate a ranked hyperlink list on the query submitting server. Among many challenges in building such a distributed search engine framework, this dissertation focuses on two key issues: query routing and page ranking. First, it presents the design and implementation of GALANX, a peer-to-peer search engine that was implemented using the Apache HTTP server and BerkeleyDB. GALANX directs user queries to relevant nodes by consulting a local peer index that is maintained on each node. The use of peer indices to direct search queries was experimentally evaluated using a 100 processor cluster. A number of alternative query routing strategies were also implemented and evaluated in the GALANX framework. Experimental results demonstrate that the use of peer indices can significantly improve performance over some existing approaches. With respect to distributed source evaluation, this dissertation presents a series of algorithms that compute PageRank in a distributed environment. The preliminary experiments on a real data set demonstrate that the system achieves comparable accuracy on PageRank vectors to Google's well-known PageRank algorithm and, therefore, high quality of query results. Finally, a group of experiments are presented as both peer indices and distributed PageRank algorithms are combined and integrated in GALANX.