Effective and Efficient Retrieval

For a given query, a page is said to be relevant if the sender of the query finds the page useful. For a given query submitted by a user against a fixed set of pages, the set of relevant pages is also fixed. A good retrieval system should return a high percentage of relevant pages to the user and rank them high in the search result for each query.

Traditionally, the effectiveness of a text retrieval system is measured using two quantities known as recall and precision. For a given query and a set of documents, recall is the percentage of the relevant documents that are retrieved and precision is the percentage of the retrieved documents that are relevant. To evaluate the effectiveness of a text retrieval system, a set of test queries is often used. For each query, the set of relevant documents is identified in advance. For each test query, a precision value at a different recall point is obtained.

When the precision values at different recall values are averaged over all test queries, an average recall-precision curve is obtained, which is used as the measure of the effectiveness of the system. A system is considered to be more effective than another system if the recall-precision curve of the former is above that of the latter. A perfect text retrieval system should have both recall and precision equal to 1 at the same time.

In other words, such a system retrieves exactly the set of relevant documents for each query. In practice, perfect performance is not achievable for many reasons, for example, a user’s information needs usually cannot be precisely specified by the used query and the contents of documents and queries cannot be completely represented by weighted terms.

Using both recall and precision to measure the effectiveness of traditional text retrieval systems requires knowing all the relevant documents for each test query in advance. This requirement, however, is not practical for independently evaluating large search engines because it is impossible to know the number of relevant pages in a search engine for a query unless all the pages are retrieved and manually examined.

Without knowing the number of relevant pages for each test query, the recall measure cannot be computed. As a result of this practical constraint, search engines are often evaluated using the average precision based on the top k retrieved pages for a set of test queries, for some small integer k, say 20, or based on the average position of the first relevant page among the returned results for each test query.

A large search engine may index hundreds of millions or even billions of pages, and process millions of queries on a daily basis. For example, by the end of 2005, the Google search engine has indexed about 10 billion pages and processed over 200 million queries every day. To accommodate the high computation demand, a large search engine often employs a large number of computers and efficient query processing techniques.

When a user query is received by a search engine, the inverted file structure of the pre-processed pages, not the pages themselves, are used to find matching pages. Computing the similarity between a query and every page directly is very inefficient because the vast majority of the pages likely do not share any term with the query and computing the similarities of these pages with the query is a waste of resources.

To process a query, a hash table is first used to locate the storage location of the inverted file list of each query term. Based on the inverted file lists of all the terms in the query, the similarities of all the pages that contain at least one term in common with the query can be computed efficiently.

Result Organization. Most search engines display search results in descending order of their matching scores with respect to a given query. Some search engines, such as the Vivisimo search engine (www.vivisimo.com), organize their results into groups such that pages that have certain common features are placed into the same group. Clustering/categorizing search results is known to be effective in helping users identify relevant results in two situations.

One is when the number of results returned for a query is large, which is mostly true for large search engines, and the other is when a query submitted by a user is short, which is also mostly true as the average number of terms in a search engine query is slightly over two. When the number of results is large, clustering allows the searcher to focus the attention on a small number of promising groups.

When a query is short, the query may be interpreted in different ways, in this case, clustering can group results based on different interpretations that allow the searcher to focus on the group with desired interpretation. For example, when query ‘‘apple’’ is submitted to the Vivisimo search engine, results related to Apple computer (Macintosh) forms one group and results related to fruit forms another group, which makes it easy for a user to focus on the results he/she wants.