Next Generation Search Engine for the Result Clustering Technology

Introduction

Traditional search engines provide an interface to accept the queries and use the index technique to generate a list of URLs to the Web pages containing the query. The goal of search engines is to help the users fulfill their information need with minimal effort. What makes this goal challenging is that most users always tend to input very short queries. According to the literatures (Jansen, Spink, Bateman, & Saracevic, 1998; Silverstein, Henzinger, Marais, & Moricz, 1998; Spink, Wolfram, Jansen, & Saracevic, 2001), the average length of a user query is 2.3 words. In such short queries, it is a difficult task to find users’ search needs, especially for ambiguous queries. Next generation search engines will solve this problem by focusing on users’ search needs rather than the search query, and by offering various post-search tools to help the users in dealing with large sets of somewhat imprecise results. Such tools include query suggestions or refinements (e.g., Google AdWords and Yahoo Search Marketing), mapping of search results against a predetermined taxonomy (e.g., Open Directory Project and Yahoo Directory), and the result clustering (e.g., Clusty and Lingo3G). All these tools are based in full or in part on the analysis of search results.

Result clustering has recently attracted a lot of attention to provide the users with a succinct overview of relevant results. Many commercial metasearch engines with the feature of result clustering, such as Kartoo, Lingo3G, Excite, MetaCrawler, WebCrawler, Dogpile, Mamma, and Clusty, have been successfully implemented. Their effectiveness have been recognized by (Sherman, 2004, 2005), which conferred the best metasearch engines award to Dogpile, Mamma, and Clusty during 2001 to 2004. The big three search engines (Google, Yahoo, and Bing) also seem to be interested in this technology because it has been called the future of PageRank (Beal, 2004; Mook, 2005).

Result clustering was introduced in a primitive form by Northernlight and then made widely popular by Clusty (formerly Vivisimo). The problem solved by this technology consists of clustering the search results returned by a metasearch engine into hierarchical tree that is labeled with variable-length sentences. The labels assigned to the tree should capture the topic of search results contained in their associated labels. Hierarchical tree structure provides a complementary view to the search results. Users can customize their view of search results by simply navigating hierarchical tree. This navigational approach is especially useful for informative, polysemous, and poor queries (Broder, 2002).

There are three main challenges with this technology: (1) generating good descriptive labels to clusters; (2) clustering the search results into hierarchical tree; (3) clustering must be performed on-the-fly. Traditional data mining approaches are not concerned with the feature of result clustering, but in return they are often very good at grouping documents (Prado & Ferneda, 2007). Unfortunately, regardless of how good the document grouping is, users are not likely to use a clustering system if their labels are poor. Moreover, the search results are presented in hierarchical tree that can help the users to fulfill their search needs. Finally, the processing time is also a major issue of this technology because users expect fast response times.

A common method used by this technology is to cluster partial Web pages, called snippets, rather than entire Web pages. The snippet usually contains the URL, the title, and the fragment of search results summarized by remote search engines. The snippet is considerably smaller than whole Web page, thereby drastically reducing the computational cost of clustering. This is very important because it would be unacceptably costly to download whole Web page and make the labeled clustering from them.