Abstract
Search engines have become an indispensable gateway to the sheer amount of information on the Web. Due to the large number of webpages available on any given topic, search results displayed to the search engine users are usually ranked in descending order of their relevance to the query. Because users typically browse only the first few pages of search results, the quality of relevance ranking is critical to the search experience.
In this thesis, we address a challenging issue for relevance ranking in Web search: underspecified queries. To improve the quality of relevance ranking for underspecified queries, we exploit user feedbacks from two different perspectives. In the first part of this thesis, we address two common problems of underspecified queries. The first problem is that the top-ranked results for underspecified queries may not contain information that is truly relevant to the user’s search intent, due to the large number of pages that could match the query. The second problem is that new webpages (even though relevant) may not be ranked high for an underspecified query due to their freshness. We propose to investigate what we called the query context, i.e. the distributional information of past queries from the search engine query logs, to refine the relevance ranking of the search results. Empirical evaluation shows that our proposal has improved over the current ranking system of a large-scale commercial Web search engine for 82% of the queries.
In the second part of the thesis, we study the modeling of collective expertise. We present a novel collaborative ranking model inspired by the network flow theory, which constructs a network based on search engine logs to describe the relationship among the entities in collaborative search: collaborators, queries, and documents. This formal model permits the theoretical investigation of the nature of collaborative ranking in more concrete terms, and the learning of the dependence relations among these heterogenous entities. We then propose FlowRank, a collaborative ranking algorithm derived from this model through an analysis of empirical usage patterns. We also discuss the implementation and evaluation of FlowRank, and report improvements over two baseline ranking algorithms.
CHAPTER 1
INTRODUCTION
1.1 THE WEB AND SEARCH ENGINES
The key factors for the success of the Web are the sheer amount of information, the exponential growth, and the decentralized content administration. There are now estimated to be close to 30 billion pages on the Web as of February 2007 [3] . The growth rate appears to be getting faster and faster [3, 31, 44] . And the total number of Web users has also surpassed 1 billion as of December 2007 [1] . Although there are a number of standardization bodies (e.g. W3C[1] and IETF[2] ), there is no “quality control” per se in terms of the online contents.
As a result, the aforementioned success factors also pose some ever-growing challenges users have to face when seeking relevant information on the Web. The huge amount of available webpages on almost any given topic, combined with the lack of supervision in the process of content authoring, has led to the situation similar to “finding needles in a haystack”.
For the same reason, the hierarchical model of browsing the Web (e.g. Yahoo! Directory[3] ) has become more obsolete. Users are increasingly dependent on query-based search engines to discover information relevant to their needs [2] .
There are different types of search engines. For example, a vertical (a.k.a. topical) search engine retrieves information in a specific domain (e.g. finding products or people), in contrast to general purpose search engines such as Google[4] or Yahoo[5] . An enterprise search engine indexes and searches the documents typically within the intra-network of an organization, in contrast to a Web search engine which freely traverses the World Wide Web. There are also multimedia search engines that are specifically designed to search images, audio and video files. In this thesis we limit our scope of discussion to Web search engines which retrieve online documents (i.e. webpages), and from now on we will use the terms documents and webpages interchangeably.
1.2 SEARCH ENGINE ARCHITECTURE
Web search engines harvest, index, and archive online contents (e.g. documents, images, and videos), and provide a retrieval service to the users.
The typical architecture of a query-based Web search engine consists of an injection pipeline (a crawler module and an indexer module) and a retrieval pipeline (a query parser module, a searcher component, and a ranking module), as shown in Figure 1.1. In the injection pipeline, the crawler module harvests online documents from the Web, and the documents are then indexed by the indexer module. The indexes are stored and maintained by the search engine, usually in a distributed and layered fashion. In the retrieval pipeline, when a user issues a search query, the query parser module parses the user query, converts it to an internal representation of the query, and pass this internal query to the searcher module. The searcher module selects from the indexes the contents based on the selection criteria, and then the ranking module ranks these contents according to the ranking criteria. Eventually, the search engine returns an ordered list of documents to the user. Note that the criteria used in the selection phase and the ranking phase can be different, depending on a number of metrics (e.g. relevance to the user query, freshness, and popularity). These modules are the essential building blocks of contemporary Web search engines.
In practice, search engines are usually implemented with many more auxiliary modules. For example, a duplication removal module is installed to filter duplicate contents, and a caching module is typically built into the retrieval pipeline to speed up the process for repeated popular queries. The indexes are usually layered: the indexes of popular or high-quality contents are often separated from the indexes of the remainder, optimizing the retrieval performance of more relevant contents.
1.3 SEARCH RELEVANCE
From a user’s perspective, search relevance is a critical factor to measure the quality of the search engine. Typically, users expect to find relevant information in the top-ranked search results, and more often than not they only look at the document snippets in the first one or two result pages [34] . On the other hand, highly-ranked documents have greater visibility, which usually translates into getting more attention and eventually leads to popularity [50] . Thus, search relevance ranking can potentially introduce a huge impact on the users’ perception of information on the Web.
Without loss of generality, the problem of relevance ranking can be defined as follows:
- Given a query q and a document d, we assign a relevance ranking score rel(q,d) ∈ [0,1] according to criteria C.
- Given a query q and two documents di and dj, rel(q,di) > rel(q,dj) if and only if document di is more relevant w.r.t. query q than document dj.
3
Figure 1.1. The typical architecture of a Web search engine consists of an injection pipeline (a crawler module and an indexer module) and a retrieval pipeline (a query parser module, a searcher component, and a ranking module).
Given the importance of search relevance as discussed above, there has been a surge of research interests in relevance ranking in the past decade. We’ll summarize in detail the state-of-art literature in Chapter 2. The focus of this thesis is on search relevance ranking algorithms, which applies to the ranking module in Figure 1.1.
1.4 A CHALLENGE: UNDERSPECIFIED QUERIES
What is a underspecified search query? Let us consider the following two scenarios:
- A user submits the query “hard disk case” despite the fact that a more accurate description of the user’s intent (i.e. generally accepted and more frequently used on the web) is “hard drive enclosure”. Because search engines usually rank the webpages based on their syntactic match with the query terms (i.e. considering the term frequency, proximity, etc.), the search results for this query could suffer in terms of relevance, even though some of the retrieved pages may actually contain the more accurate descriptive terms (such as “drive” and “enclosure”).
- A user wants to find information about the upcoming lunar eclipse by submitting a query “lunar eclipse”. Although we hypothesize that recently a considerable amount of queries containing both the phrases “lunar eclipse” and “2008” could have been repeatedly sent to popular search engines, these search engines may still not be able to rank the official 2008 lunar eclipse website as the top result for the query “lunar eclipse” without specifying the year “2008”.
In the first example, an underspecified query is an unarticulated query consists of naive search terms. In the second example, an underspecified query is a recency query (i.e. user implicitly favors more recent information). Both cases present a challenge to the search engine, and call for relevance ranking methods that take into account not only a webpage’s overall quality and relevance to the search query, but also the match with the users’ informational need, further referred to as their real search intents.
1.5 SCOPE AND STRUCTURE OF THESIS
In this thesis, we address the challenge posed by the underspecified queries to relevance ranking in Web search. We specifically exploit the following two perspectives to solve this problem:
- Given the collective expertise and recency information embedded in the query logs of a search engine, how do we unlock and utilize this information to improve search ranking for underspecified queries?
- How do we model the collective expertise in Web search, and derive an effective and efficient collaborative ranking algorithm?
The rest of this thesis is organized as follows. In Chapter 2, we summarize in detail the stateof-art literature of search relevance and ranking. In Chapter 3, we investigate the use of query log mining to improve the ranking of underspecified search queries. In Chapter 4, we propose a novel flow-based model of collaborative search ranking. We summarize this thesis study in chapter 5.
IMPROVING RELEVANCE RANKING FOR UNDERSPECIFIED QUERIES