6.1: The Need for Reformulation

Examination of search engine query logs suggests a high frequency of query reformulation. One study by Jansen et al., 2005 analyzed 3 million records from a 24 hour snapshot of Web logs taken in 2002 from the AltaVista search engine. (The search activity was partitioned into sessions separated by periods of inactivity, and no effort was made to determine if users searched for more than one topic during a session. 72% of the sessions were less than five minutes long, and so one-topic-per-session is a reasonable, if noisy, estimate.) The analysis found that the proportion of users who modified queries was 52%, with 32% issuing 3 or more queries within the session. Other studies show similar proportions of refinements, thus supporting the assertion that query reformulation is a common part of the search process.

Good tools are needed to aid in the query formulation process. At times, when a searcher chooses a way to express an information need that does not successfully match relevant documents, the searcher becomes reluctant to radically modify their original query and stays stuck on the original formulation. Hertzum and Frokjaer, 1996 note that at this point “the user is subject to what psychologists call anchoring, i.e., the tendency to make insufficient adjustments to initial values when judging under uncertainty”. This can lead to “thrashing” on small variations of the same query. Russell, 2006 remarks on this kind of behavior in Google query logs. For example, for a task of “Find out how many people have bought the new Harry Potter book so far”, he observes the following sequence of queries for one user session:

• Harry Potter and the Half-Blood Prince sales
• Harry Potter and the Half-Blood Prince amount sales
• Harry Potter and the Half-Blood Prince quantity sales
• Harry Potter and the Half-Blood Prince actual quantity sales
• Harry Potter and the Half-Blood Prince sales actual quantity
• Harry Potter and the Half-Blood Prince all sales actual quantity
• all sales Harry Potter and the Half-Blood Prince
• worldwide sales Harry Potter and the Half-Blood Prince

In order to show users helpful alternatives, researchers have developed several techniques to try to aid in the query reformulation process (although existing tools may not be sophisticated enough to aid the user with the information need shown above.) This chapter describes interface technologies to support query reformulation, and the ways in which users interact with them.

6.2: Spelling Suggestions and Corrections

Search logs suggest that from 10-15% of queries contain spelling or typographical errors (Cucerzan and Brill, 2004). Fittingly, one important query reformulation tool is spelling suggestions or corrections. Web search engines have developed highly effective algorithms for detecting potential spelling errors (Cucerzan and Brill, 2004, Li et al., 2006).

Before the web, spelling correction software was seen mainly in word processing programs. Most spelling correction software compared the author's words to those found in a pre-defined dictionary (Kukich, 1992), and did not allow for word substitution. With the enormous usage of Web search engines, it became clear that query spelling correction was a harder problem than traditional spelling correction, because of the prevalence of proper names, company names, neologisms, multi-word phrases, and very short contexts (some spelling correction algorithms make use of the sentential structure of text). Most dictionaries do not contain words like blog, shrek, and nsync.

But with the greater difficulty also came the benefit of huge amounts of user behavior data. Web spelling suggestions are produced with the realization that queries should be compared to other queries, because queries tend to have special characteristics, and there is a lot of commonality in the kinds of spelling errors that searchers make. A key insight for improving spelling suggestions on the Web was that query logs often show not only the misspelling, but also the corrections that users make in subsequent queries. For example, if a searcher first types schwartzeneger and then corrects this to schwartzenegger, if the latter spelling is correct, an algorithm can make use of this pair for guessing the intended word. Experiments on algorithms that derive spelling corrections from query logs achieve results in the range of 88-90% accuracy for coverage of about 50% of misspellings (Cucerzan and Brill, 2004, Li et al., 2006). For Web search engine interfaces, one alternative spelling is typically shown beneath the original query but above the retrieval results. The suggestion is also repeated at the bottom of the results page in case the user does not notice the error until they have scrolled through all of the suggested hits. As noted in Chapter 1, in most cases the interface offers the choice to the user without forcing an acceptance of an alternative spelling, in case the system's correction does not match the user's intent. But in the case of a blatantly incorrect typographical error, a user may prefer the correction to be made automatically to avoid the need for an extra click. To balance this tradeoff, some search engines show some hits with their guess of the correct spelling interwoven with others that contain the original, most likely incorrect spelling.

There are no published large-scale statistics on user uptake of spelling correction, but a presentation by Russell, 2006 shows that, for those queries that are reformulations, and for which the original query consisted of two words, 33% of the users making reformulations used the spelling correction facility. For three-word query reformulations, 5% of these users used the spelling suggestion.

In an in-person study conducted with a statistically representative subject pool of 100 people, Hargittai, 2006 studied the effects of typographical and spelling errors. (Here typographical means that the participant knows the correct spelling but made a typing mistake, whereas spelling error means the participant does not know the correct spelling.) Hargittai, 2006 found that 63% of the participants made a mistake of some kind, and among these, 35% made only one mistake, but 17% made four or more errors during their entire session. As might be predicted, lower education predicted higher number of spelling errors, but an interesting finding was that the higher the participant's income, the more likely they were to make a typographical error. Older participants were more also likely to make spelling errors. The most surprising result, however, was that of the 37 participants who made an error while using Google search, none of them clicked on the spelling corrections link. This would seem to contradict the statistics from Russell, 2006. It may be the case that in Hargittai's data, participants made errors on longer queries exclusively, or that those from a broader demographic do not regularly make use of this kind of search aid, or that the pool was too small to observe the full range of user behavior.

6.3: Automated Term Suggestions

The second important class of query reformulation aids are automatically suggested term refinements and expansions. Spelling correction suggestions are also query reformulation aids, but the phrase term expansion is usually applied to tools that suggest alternative words and phrases. In this usage, the suggested terms are used to either replace or augment the current query. Term suggestions that require no user input can be generated from characteristics of the collection itself (Schütze and Pedersen, 1994), from terms derived from the top-ranked results (Anick, 2003, Bruza and Dennis, 1997), a combination of both (Xu and Croft, 1996), from a hand-built thesaurus (Voorhees, 1994, Sihvonen and Vakkari, 2004), or from query logs (Cui et al., 2003, Cucerzan and Brill, 2005, Jones et al., 2006) or by combining query logs with navigation or other online behavior (Parikh and Sundaresan, 2008).

Usability studies are generally positive as to the efficacy of term suggestions when users are not required to make relevance judgements and do not have to choose among too many terms. Some studies have produced negative results, but they seem to stem from problems with the presentation interface. Generally it seems users do not wish to reformulate their queries by selecting multiple terms, but many researchers have presented study participants with multiple-term selection interfaces.

For example, in one study by Bruza et al., 2000, 54 participants were exposed to a standard Web search engine, a directory browser, and an experimental interface with query suggestions. This interface showed upwards of 40 suggested terms and hid results listing until after the participant selected terms. (The selected terms were conjoined to those in the original query.) The study found that automatically generated term suggestions resulted in higher average precision than using the Web search engine, but with a slower response time and the penalty of a higher cognitive load (as measured by performance on a distractor task). No subjective responses were recorded. Another study using a similar interface and technology found that users preferred not to use the refinements in favor of going straight to the search results (Dennis et al., 1998), underscoring the search interface design principle that search results should be shown immediately after the initial query, alongside additional search aids.

6.4: Suggesting Popular Destinations

White et al., 2007 suggested another kind of reformulation information: showing popular destination Web sites. They recorded search activity logs for hundreds of thousands of users over a period of five months in 2005--2006. These logs allowed them to reconstruct the series of actions that users made from going to a search engine page, entering a query, seeing results, following links, and reading web pages. They determined when such a session trail ended by looking for a stoppage, such as staying on a page for more than 30 minutes, or a change in activity, such as switching to email, or going to a bookmarked page. They distinguished session trails from query trails; the latter had the same stopping conditions as the former, but could also be ended by a return to a search engine page. Thus they were able to “follow” users along as they performed their information seeking tasks.

White et al., 2007 found that users generally browsed far from the search results page (around 5 steps), and that on average, users visited 2 unique domains during the course of a query trail, and just over 4 domains during a session trail. They decided to use the information about which page the users ended up at as a suggestion for a shortcut for a given query. Given a new query, its statistical similarity to previously seen query-destination pairs was computed, and popular final destinations for that query were then shown as a suggested choice (see Figure 6.4). They experimented with suggestions from both query trails and sessions trails.

In the same study of 36 participants, they compared these two experimental approaches against a standard search engine baseline and a query suggestions interface, testing on both known-item tasks and exploratory tasks. For exploratory tasks, the destination suggestions from the query trails scored better than the other four systems on perceptions of the search process (easy, restful, interesting, etc.) and usefulness (perceived as producing more useful and relevant results) for the exploratory tasks. The task completion time on exploratory tasks was approximately the same for all four interfaces; the destination suggestions were tied in terms of speed with query term suggestions in known-item tasks. In exploratory tasks, query trail destination suggestions were used more often (35.2% of the time) than query term suggestions and session trail destination suggestions.

Participants who preferred the destination suggestions commented that they provided potentially helpful new areas to look at, and allowed them to bypass the need to navigate to pages. They suggested that destinations were selected because they “grabbed their attention,” “represented new ideas,” or users “couldn't find what they were looking for.” Those who did not like the suggestions stated as a reason the vagueness of showing only a Web site; presumably augmenting the destination views with query-biased summaries would make them more useful. The destination suggestions produced from session trails were sometimes very good, but were inconsistent in their relevance, a characteristic which is usually perceived negatively by users. The participants did not find the graphical bars indicating site popularity to be useful, mirroring other results of this kind.

6.5: Relevance Feedback

Another major technique to support query reformulation is relevance feedback. In its original form, relevance feedback refers to an interaction cycle in which the user reads retrieved documents and marks those that appear to be relevant, and the system then uses features derived from these selected relevant documents to revise the original query (Ruthven and Lalmas, 2003). In one variation, the system uses information from the marked documents to recalculate the weights for the original query terms, and to introduce new terms. In another variation, the system suggests a list of new terms to the user, who then selects a subset of these to augment the query (Koenemann and Belkin, 1996). The revised query is then executed and a new set of documents is returned. Documents from the original set can appear in the new results list, although they are likely to appear in a different rank order. In some cases the relevance feedback interface displays an indicator such as a marked checkbox beside the documents that the user has already judged. For most relevance feedback techniques, a larger number of marked relevant documents yields a better result.

In a method known as pseudo-relevance feedback (also known as blind relevance feedback), rather than relying on the user to choose the top k relevant documents, the system simply assumes that its top-ranked documents are relevant, and uses these documents to augment the query with a relevance feedback ranking algorithm. This procedure has been found to be highly effective in some settings (Thompson et al., 1995, Kwok et al., 1995, Allan, 1995). However, it does not perform reliably when the top-ranked documents are not relevant (Mitra et al., 1998a).

Relevance feedback in its original form has been shown -- in artificial settings -- to be an effective mechanism for improving retrieval results (Salton and Buckley, 1990, Harman, 1992, Buckley et al., 1994, Mitra et al., 1998a). For instance, a study by Kelly et al., 2005 compared carefully elicited user-generated term expansion with relevance feedback based on documents that were pre-determined by an expert to be the most relevant. The results of relevance feedback using the top-ranked documents far outstripped user-generated term expansion. Kelly et al., 2005 used the highly relevant documents as an upper bound on performance, as it could not be expected that ordinary users would identify such documents.

This finding is echoed by another study for the TREC HARD track in which an expert was shown the documents pre-determined to be most relevant and spent three minutes per query choosing documents for relevance feedback purposes. The resulting improvements over the baseline run was 60% over the metric used to assess improvements from clarification dialogues (Allan, 2005). The results of using user-generated additional terms were that queries that were already performing well improved more than queries that were not performing well originally. This study also found that spending more time in the clarification dialogue did not correlate with improved final results.

Despite its strong showing in artificial or non-interactive search studies, the use of classic relevance feedback in search engine interfaces is still very rare (Croft et al., 2001, Ruthven and Lalmas, 2003), suggesting that in practice it is not a successful technique. There are several possible explanations for this. First, most of the earlier evaluations assumed that recall was important, and relevance feedback's strength mainly comes from its ability to improve recall. High recall is no longer the standard assumption when designing and assessing search results; in more recent studies, the ranking is often assessed on the first 10 search results. Second, relevance feedback results are not consistently beneficial; these techniques help in many cases but hurt results in other cases (Cronen-Townsend et al., 2004, Marchionini and Shneiderman, 1988, Mitra et al., 1998a). Users often respond negatively to techniques that do not produce results of consistent quality. Third, many of the early studies were conducted on small text collections. The enormous size of the Web makes it more likely that the user will find relevant results with fewer terms than is the case with small collections. And in fact there is evidence that relevance feedback results do not significantly improve over web search engine results (Teevan et al., 2005b).

But probably the most important reason for the lack of uptake of relevance feedback is that the method requires users to make relevance judgements, which is an effortful task (Croft et al., 2001, Ruthven and Lalmas, 2003). Evidence suggests that users often struggle to make relevance judgements (White et al., 2005), especially when they are unfamiliar with the domain (Vakkari, 2000b, Vakkari and Hakala, 2000, Spink et al., 1998). In addition, when many of the earlier studies were done, system response time was slow and the user was charged a fee for every query, so correct query formulation was much more important than for the rapid response cycle of today's search engines. (By contrast, a search engine designed for users in the developing world in which the round trip for retrieval results can be a day or more has renewed interest in accurate query formulation (Thies et al., 2002).) The evidence suggests it is more cognitively taxing to mark a series of relevance judgements than to scan a results listing and type in a reformulated query.

6.6: Showing Related Articles (More Like This)

To circumvent the need for multiple relevant document selection, Aalbersberg, 1992 introduced an incremental relevance feedback that requires the user to judge only one document at a time. Similarly, some Web-based search engines have adopted a “one-click” interaction method. In the early days of the Web, the link was usually labeled as “More like this”, but other terms have been used, such as “Similar pages” or “Related articles” at the biomedical search engine Pubmed. (This is not to be confused with “Show more results at this site” which typically re-issues the query within a subdomain.)

More recently in PubMed, after a user chooses to view an article, the titles of some related articles are shown along the right hand side (see Figure 6.5). Related articles are computed in terms of a probabilistic model of how well they match topics (Lin and Wilbur, 2007). These related articles are relatively heavily used by searchers. Lin et al., 2008 studied a week's worth of query logs from PubMed in June 2007, observing about 2M sessions that included at least one PubMed query and abstract view. Of these, 360,000 sessions (18.5%) included a click on a suggested related article, representing about one fifth of non-trivial search sessions. They also found that as session lengths increased, the likelihood of selecting a related article link grew, and once users started selecting related articles, they were likely to continue doing so, more than 40% of the time.

Thus, the evidence suggests that showing similar articles can be useful in literature search, but it is unclear what its utility is for other kinds of search. Related article links act as a “black box” to users, meaning they cannot see why it is that one set of articles is considered related and others are not. Furthermore, they do not have control over in what ways other articles are related. Interfaces which allow users to select a set of categories or dimensions along which documents are similar may be more effective for this, as discussed in Chapter 8 on integrating navigation and search.

6.7: Conclusions

When an initial query is unsuccessful, a searcher can have trouble thinking of alternative ways to formulate it. Query reformulation tools can be a highly effective part of the search user interface. Query reformulation is in fact a common search strategy, as evidenced by the statistics presented throughout this chapter -- roughly 50% of search sessions involve some kind of query reformulation.

Both spelling suggestions and term expansions are effective reformulation tools -- term suggestion tools are used roughly 35% of the time that they are offered to users. Additionally, showing popular destinations for common queries, and showing related articles for research-style queries have both been shown to be effective. However, relevance feedback as traditionally construed has not been proven successful in an interactive context.