3.5.1: Strategies as Sequences of Tactics

Bates, 1979 suggests that a searcher's behavior can be characterized by search strategies which in turn are made up of sequences of search tactics. Tactics are the immediate choices or actions taken in the light of the current focus of attention and state of the search. Strategies refer to combinations of tactics used in order to accomplish information access tasks. Thus strategies are sequences of tactics which, viewed together, help achieve some aspect or subgoal of the user's main goals. Bates enumerates a set of search tactics which she groups into four categories, which are paraphrased slightly below.

• Term tactics: refer to tactics for adjusting words and phrases within the current query. These include making use of term suggestions provided by the search system and selecting terms from an online thesaurus.

• Information structure tactics: are techniques for moving through information or link structures to find sources or information within sources. An example of an information structure tactic for an academic researcher is looking at the research articles that cite a given paper, and following the citation chain. Another example is, when searching within an online collection or Web site, following promising hyperlinks or searching within a category of information, e.g., searching only within the technology section of a news Web site.

• Query reformulation tactics: examples include narrowing a given query specification by using more specific terms or gaining more control over the structure of the query by using Boolean operators.

• Monitoring tactics: monitoring refers to keeping track of a situation as it unfolds. Bates discusses several high-level monitoring tactics, including making a cost-benefit analysis of current or anticipated actions (weighing), continuously comparing the current state with the original goal (checking; note the similarity to Norman, 1988's gulf of evaluation), recognizing patterns across common strategies, and recording incomplete paths to enable returning at a later time. Bates also notes that one of the fundamental issues in search strategies is determining when to stop; monitoring tactics can help with this determination.

A question arises as to how a searcher who is monitoring their search knows to stop following one strategy and take up another. O'Day and Jeffries, 1993 defined a number of triggers that motivate a seeker to switch from one search strategy to another. These triggers include:

• The completion of one step and beginning of the next logical step in a plan,
• Encountering something interesting that provides a new way of thinking about a topic of interest, or a new, interesting angle to explain a topic or problem,
• Encountering a change or violation of previous expectations that requires further investigation, and
• Encountering inconsistencies with or gaps in previous understanding that requires further investigation.

O'Day and Jeffries also attempted to identify stop conditions -- circumstances under which people decided to stop searching. These were fuzzier than the triggers for changing strategies, but they did find that people stopped searching when:

• There were no more compelling triggers,
• An “appropriate” amount of material had been found, or
• There was a specific inhibiting factor (such as discovering a market was too small to be worth researching).

These stop conditions can be cast in terms of a cost-benefit analysis (see discussion below); for example, the second point might be interpreted as a drop below a threshold for continuing the current line of inquiry.

Bates, 1979 notes that some search tasks are straightforward enough that a strategy per se is not required. Simple fact-searching on the Web is an example of this; the searcher opens a Web browser, navigates to a search engine entry form, types in their information need, and scans the retrieval results to find the answer or a link to a page that contains the answer.

3.5.2: Cost Structure Analyses and Information Foraging Theory

As mentioned above, Bates, 1979 discusses the importance of monitoring the progress of the current search and weighing the costs and benefits of continuing with the current strategy or trying something else. Russell et al., 1993 also cast the activity of monitoring the progress of a search strategy relative to a goal or subgoal in terms of a cost structure analysis, or an analysis of diminishing returns. This account assumes that at any point in the search process, the user is pursuing the strategy that has the highest expected utility. If, as a consequence of some local tactical choices, another strategy presents itself as being of higher utility than the current one, the current one is (temporarily or permanently) abandoned in favor of the new strategy.

This cost structure analysis method was subsequently expanded into information foraging theory by Pirolli and Card, 1999. This theoretical framework contains several ideas relevant to understanding the search process. It takes an evolutionary stance, noting that humans' ancestors evolved perceptual and cognitive structures that were well-adapted for exploring the environment in the task of finding food. The theory assumes that, in the modern world, awash with information of our own creation, humans transfer food-finding cognitive mechanisms over to the task of exploring, finding, and ultimately “consuming” information (Pirolli, 2007).

Information foraging theory attempts to model and make predictions about peoples' strategies for navigating within information structures. One important concept is a cost-benefit analysis for navigation, in which searchers make tradeoffs between two questions. Nielsen, 2003a formulates this as:

• (i) What gain can I expect from a specific information nugget (such as a Web page)?
• (ii) What is the likely cost in terms of time and effort of discovering and consuming that information?

Thus, an information consumer compares the cost of evaluation and immediate “consumption” of information with the cost of additional search. This model can account for the decreasing returns on, say, reading information from a search results list: after some number of documents on a topic have been read, the tradeoff between finding new information versus reading information already seen or of lower quality begins to tip in favor of ending the information consumption session. That is, the theory assumes that search strategies evolve toward those that maximize the ratio of valuable information gained to unit of cost for searching and reading.

When foraging, information can appear in “patches”; it might make sense to read a few pieces of information from one Web site, and then move to another Web site to get more variety in the “diet”; however, one must consider the payoff in finding new kinds of information versus the cost of getting to a new good patch of information. Nielsen, 2003a points out that in the early days of the Web, search quality was poor and there was not very much content available, so it made more sense to focus all one's attention on an information-rich Web site once it was found. But as the content increased and search results improved in the late 1990s, the cost of finding high-quality additional sources of information fell, and so it often became more cost-effective and advantageous to forage briefly on each of a variety of different sites.

3.5.3: Browsing vs. Search as an Information Seeking Strategy

A bedrock psychological result from cognitive science is recognition over recall; that is, it is usually easier for a person to recognize something by looking for it than it is to think up how to describe that thing. A familiar example is experienced by learners of a foreign language; it is usually easier to read a sentence in that language than to generate a sentence oneself. This principle applies to information seeking as well. Rather than requiring the searcher to issue keyword queries and scan retrieval results, the system can provide the searcher with structure that characterizes the available information.

There are a number of theories and frameworks that contrast querying/searching and browsing/navigating, along several dimensions (Belkin et al., 1993, Chang and Rice, 1993, Marchionini, 1995, Waterworth and Chignell, 1991). One way to distinguish searching versus browsing is to note that search queries tend to produce new, ad hoc collections of information that have not been gathered together before, whereas navigation/browsing refers to selecting links or categories that produce pre-defined groups of information items. Browsing also involves following a chain of links, switching from one view to another, in a sequence of scan and select operations. Browsing can also refer to the casual, mainly undirected exploration of navigation structures. Hertzum and Frokjaer, 1996 word the contrast as follows:

“Browsing is a retrieval process where the users navigate through the text database by following links from one piece of text to the next, aiming to utilize two human capabilities ... the greater ability to recognize what is wanted over being able to describe it and ... the ability to skim or perceive at a glance. This allows users to evaluate rapidly rather large amounts of text and determine what is useful.”

Aula, 2005 writes:

“Considered in cognitive terms, searching is a more analytical and demanding method for locating information than browsing, as it involves several phases, such as planning and executing queries, evaluating the results, and refining the queries, whereas browsing only requires the user to recognize promising-looking links.”

Thus, in principle, in many situations it is less mental work to scan a list of hyperlinks and choose the one that is of interest than it is to think up the appropriate query terms to describe the information need. But there are diminishing returns to scanning links if it takes too long to find the label of interest, and there is always the possibility that the desired information is not visible. That is, browsing works only so long as appropriate links are available, and they have meaningful cues about the underlying information.

In a comparative study with 96 student participants finding information in online software manuals, Hertzum and Frokjaer, 1996 found that browsing a hierarchical table of contents produced the best mean performance (compared to Boolean queries) but did not provide stable good performance, presumably because for some tasks the information structure used for the browsing was not suitable for the information need. They concluded that browsing is well-suited for some tasks, but unsuited for others. A study of the SuperBook system (Landauer et al., 1993) found similar results: when the queries were well-represented by hits on a table-of-contents representation, browsing worked better than keyword search, but did not improve results when the information structure did not match the information need.

The field of information architecture makes a distinction between information structure and navigation structure. Information structure defines the organization, textual labels, and controlled vocabulary terms for the content items of the site (Morville and Rosenfeld, 2006). Navigation structure determines the paths that can be taken through the information structure, via the hyperlinked user interface (Newman and Landay, 2000). Thus the success of a browsing interface depends in part on how well the presented information matches searchers' information needs and expectations. Another important property of browsing interfaces is that they should seamlessly integrate keyword querying with navigation of the underlying information structure. Many Web sites use dynamically generated metadata to provide a flexible, browsable information structure. Chapter 8 discusses information and navigation structures that aid in navigation and discovery within information collections.

3.5.4: Information Scent for Navigating Information Structures

When navigating within information structures, in order to make decisions about which information “patches” are promising to pursue, searchers must examine clues about where to find useful information. One part of Pirolli and Card, 2005's information foraging theory discusses the notion of information scent: cues that provide searchers with concise information about content that is not immediately perceptible. Pirolli, 2007 notes that small pertubations in the accuracy of information scent can cause qualitative shifts in the cost of browsing; improvements in information scent are related to more efficient foraging. The detection of diminishing information scent is involved in decisions to leave an information patch.

Furnas, 1997 also discusses the idea of information scent, stating that a target has scent at a link if the associated outlink information would lead an information navigator to take that link in pursuit of the given target. Furnas puts forward the navigability proposition that states that in order for a target to be findable by navigation from anywhere in the information structure, the path to that target must have good scent at every link.

Search results listings must provide the user with clues about which results to click; the notion of information scent can be applied to this problem. Spool, 2007 suggests operationalizing the idea of information scent in Web site design by showing users informative hints about what kind of information will be found one hop away from the current Web page. One example suggestion is to augment links to product categories with a short list of the types of items to be found in that category. Nielsen, 2003a suggests, for the design of Web site home pages, showcasing sample content and prominently displaying navigation and search features, so searchers have the “scent” for what can be found by exploring further on the web site. Nielsen, 2004a also points out that misleadingly strong scent can cause information browsers to overlook the best location to find their object of interest. Figure 3.4b shows the home page of the U.S. government's Bureau of Labor Statistics Web site, which has been carefully designed to have good information scent. Its design was refined via several iterations of evaluation and redesign, progressively adding more information as the information needs of the users of the site became clear (Marchionini and Levi, 2003). An early version of the interface is shown in Figure 3.4a. In the earlier design, a graphical display of the main categories provided few cues about the rich information sources that lay behind them.

3.5.5: Orienteering and other Incremental Strategies

A commonly-observed search strategy is one in which the information seeker issues a quick, imprecise query in the hopes of getting into approximately the right part of the information space, and then doing a series of local navigation operations to get closer to the information of interest (Marchionini, 1995, Bates, 1990). O'Day and Jeffries, 1993 use the term orienteering to describe search strategies in which searchers use information from their current situation to help determine where to go next, as opposed to trying to find the answer in one jump by writing a long complex query indicating the full information need.

A number of studies have shown that searchers tend to start out with short or general queries, inspect the results, and then modify those queries in an incremental feedback cycle (Bates, 1989, Waterworth and Chignell, 1991, Anick, 1994, Teevan et al., 2004, Eysenbach and Kohler, 2002). Bates, 1979 also notes that a good tactic is to “break complex search queries down into subproblems and work on one problem at a time. This tactic is a well-established and productive technique in general problem solving.”

Hertzum and Frokjaer, 1996 noted this kind of behavior in a search interface usability study, finding that participants issue a sequence of queries rather than one all-inclusive query, enabling them to exploit information obtained earlier in the query sequence. This strategy is not without its drawbacks, as people can become too fixed on the their starting strategy. Hertzum and Frokjaer, 1996 write:

“When a subject starts on a task, the first query expresses his initial, incomplete attempt to reach a solution. If this query does not provide the subject with the information needed, another must be formulated. 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 ... Thus, the subjects may tend to refrain from abandoning the initial query terms or from adjusting them very far, making the subsequent queries biased toward the initial one.”

Russell, 2006 also observed this kind of “thrashing” behavior in Google search engine logs.

Teevan et al., 2004 studied the information seeking behavior of 15 computer science graduate students over a period of one week. They observed extensive use of orienteering behavior, even when a more direct search might be more efficient. In most of these cases, participants began with an information resource that they were already familiar with, and followed links from that resource. For example, one student wanted to find the office number for a particular professor. As he had seen that professor's Web page previously, rather than search for it via a query on a search engine, he first navigated to the mathematics department Web page for the university, and from there to a link for faculty Web pages, and from there to the desired page. It might have required fewer steps to simply type in a query containing the professor's name and the phrase “office number” to find the same result, but this approach requires the searcher to spell the professor's name correctly, rely on the word “office” appearing on her Web page, and make other guesses about the behavior of the search engine that may not hold true. In other examples, searchers took conceptually large steps followed by smaller ones. Teevan et al. use the term teleporting to distinguish orienteering from a more directed behavior in which a long, precise query is typed. In a large study with 714 participants, Bergman et al., 2008 found that, when looking for files on their desktop computer, desktop search was used only 10-15% of the time, with navigation of file structure strongly preferred.

Thus, in many cases, searchers followed known paths that require small steps that move them closer to their goal, potentially reducing the likelihood of error. Teevan et al., 2004 speculated that this approach is cognitively less taxing than fully specifying a query, as searchers do not have to articulate exactly what they are looking for precisely. Teevan et al., 2004 also noted that this kind of behavior allows the searcher to retain information about the context in which the information occurs.

The typical use of a Web search engine is often incremental in the fashion described above. This may be in part because today Web search engines are very fast; a typical query returns results within a fraction of a second. This makes natural a strategy that relies on “testing the water” with general queries followed by rapidly narrowing the results with reformulation. It is well-known from search engine query logs that a large proportion of search sessions contain query reformulations (Jansen et al., 2005, Jansen et al., 2007a). It is furthermore known that searchers tend to look at only the top-ranked retrieved results (Joachims et al., 2005, Granka et al., 2004). This suggests that the orienteering strategy is a common one for web search: users issue general queries, get information about the results, reformulate based on information seen in the results, and then navigate to promising-looking links or else give up.

Some of today's Web search engines support longer queries well, and there is evidence that expert searchers tend to issue longer queries. If this trend continues, and/or if Web search engines begin to support full natural language queries reliably, searchers may begin to use more teleporting in their queries.

3.7.1: Web Log-based Query Taxonomies

Prior to the Web, search engine designers could safely assume that searchers had an informational goal in mind (Broder, 2002, Rose and Levinson, 2004). This was due in part to the limited population of searchers (primarily students, legal analysts, scientific researchers, business analysts) and to the kind of data that could be searched (newswire, legal cases, journal article abstracts). The queries to these systems were often long, or contained Boolean operators. Users had to carefully craft their queries, because they often paid by the minute, and careless query formulation was expensive.

As the Web developed, it became the case that not only were queries shorter and simpler, but the types of information available were quite different. As opposed to legal cases or academic papers, the Web included information about organizations (where they are located, what their phone numbers are, what their business is), products, and individuals. Correspondingly, the underlying goals of user queries were often quite different than in the older systems. In an attempt to demonstrate how information needs for Web search differ from the assumptions of pre-web information retrieval systems, Broder, 2002 created a taxonomy of Web search goals. He then estimated the frequency of such goals by a combination of an online survey (3,200 responses, 10% response rate) and a manual analysis of 1,000 query from the AltaVista query logs. The three types of “need behind the query” that he identified were:

• Navigational : The immediate intent is to reach a particular site (24.5% survey, 20% query log).
• Informational : The intent is to acquire some information assumed to be present on one or more Web pages (39% survey, 48% query log).
• Transactional : The intent is to perform some web-mediated activity (36% survey, 30% query log).

This taxonomy has been heavily influential in discussions of query types on the Web.

Rose and Levinson, 2004 followed up on Broder, 2002's work, again using Web query logs, but developing a taxonomy that differed somewhat from Broder, 2002 's. They retained the navigational and informational categories, but noted that much of what happens on the Web is the acquisition and consumption of online resources, such as song lyrics, knitting patterns, and software downloads. Thus they replace Broder, 2002's transactions category with a broader category of resources, meaning information artifacts that users consume in some manner other than simply reading for information (although they somewhat confusingly categorize shopping queries under the informational category). They also introduced subcategories for the three main categories, including the interesting subcategory of advice seeking (which has become popular on human question answering sites; see Chapter 12).

Rose and Levinson, 2004 manually classified a set of 1,500 AltaVista search engine log queries. For two sets of 500 queries, the labeler saw just the query and the retrieved documents; for the third set the labeler also saw which item(s) the searcher clicked on. They found that the classifications that used the extra information about clickthrough did not significantly change the proportions of assignments to each category. However, because they did not directly compare judgements with and without click information on the same queries, this is only weak evidence that query plus retrieved documents is sufficient to classify query intent. (To bolster their claim, a similar result was found by Shen et al., 2005a, who developed an algorithm to effectively classify queries into subject-matter topics without using clickthrough data.)

Rose and Levinson, 2004 found a smaller proportion of navigational queries than did Broder, 2002 (an average of 13% compared to his average of 22%), but this difference may have to do with differences in sampling and search engine user bases for the two studies. They also found that informational queries were about 61% of the information needs, a much higher proportion than Broder, 2002's average of 45%.

3.7.2: Web Log-based Query Topic Classification

Queries from Web query logs can be classified according to the topic of the query, independent of the type of information need. For example, a search involving the topic of weather can consist of the simple information need of looking at today's forecast, or the rich and complex information need of studying meteorology.

Over many years, Spink and Jansen et al. (Jansen and Spink, 2006, Jansen et al., 2005, Jansen et al., 2007b, Spink et al., 2002) have manually analyzed samples of query logs to track a number of different trends. One of the most notable is the change in topic mix. In one article, they compared a manual analysis on AltaVista logs from 1997 with queries from the Dogpile metasearch engine in 2005 (Jansen et al., 2007b). They found that queries relating to sex and pornography declined from 16.8% in 1997 to just 3.6% in 2005. Commerce-related queries now dominate the query logs, claiming 30.4% in this study, up from 13.3% in 1997 (Spink et al., 2002) (see Table 3.1).

As an alternative to manual classification of query topics, Shen et al., 2005a described an algorithm for automatically classifying Web queries into a set of pre-defined topics. The main idea is to use a Web search engine to retrieve the top n results for a query, and then look at the categories that have been manually associated with those results in the past (using the Open Directory Project, ODP). They used a voting method to combine evidence from several measures, and returned the top scoring categories (up to five per query). Their results were quite strong, (an F-score of about 0.45 on 63 categories). Table 3.2 shows the results for five arbitrarily chosen queries. Another approach to this problem is described by Pu et al., 2002.

More recently, Broder et al., 2007 presented a highly accurate method (around 0.7 F-score) for classifying short, rare queries into a taxonomy of 6,000 categories. Because rare or infrequent queries are approximately half of all queries, this is an important advance. Using a commercial taxonomy which contained many documents assigned to each category, they trained a set of text classifiers. Given a query, they retrieved the top k documents using a search engine, classified documents according to the text classifier, and then used a voting algorithm to determine which class(es) best categorize the query. Gauch, 2003 found that a similar approach worked well for creating profiles of user interests based on which documents they visited (see Chapter 9).

3.7.3: Web Log-based Analysis of Query Ambiguity

Ambiguous queries are those queries that can be understood as corresponding to two or more distinct meanings: a query on apple may refer to the fruit or the computer manufacturer or the record label. A number of search interface ideas that are discussed in this book, although intended to be useful in a general way, turn out to be effective mainly for ambiguous queries (see Chapters 8 and 9). For this reason, some researchers have tried to estimate what proportion of queries truly are ambiguous.

One way to predict query ambiguity is to see what the diversity of clicks is for a given query. The thinking is that if users tend to click on the same set of links for a given query, that query indicates a single set of intentions, but if there is great diversity in the links clicked on, then the query is likely to be ambiguous either in meaning or in what user intentions it reflects.

Wen et al., 2002 did a clickthrough analysis of queries to an online encyclopedia, and found that identical query terms produced nearly identical clicks. They speculated that users were self-disambiguating by their choice of terms. Song et al., 2007 described an algorithm for estimating how many queries in a query log are ambiguous. They had 5 judges label 60 queries as either ambiguous or not, achieving 90% agreement. They then used a search engine to retrieve the top n documents for each query, and categorized those documents into a pre-defined ontology using the technique of Shen et al., 2005a. If the documents returned for a query fell into multiple categories, they considered that query to be ambiguous. Using this approach, they achieved 87% accuracy on a test set of 253 queries (using cross-validation). Applying this algorithm to a larger sample, they estimated that that sample contained only 16% ambiguous queries.

3.7.4: Web Log-based Analysis of Re-access Patterns

Many searches are characterized by people re-accessing information that they have seen in the past (Jones et al., 2001, Jones et al., 2002, Aula et al., 2005a). This can be accomplished by saving previously visited information via Web browser bookmarks or using bookmarking Web sites such as delicious.com. The observations of Teevan et al., 2004 suggested that searchers often navigate to Web pages they have visited in the past rather than issuing a search engine query. However, there is also ample evidence that people use search engines as re-finding instruments. In another study, Teevan et al., 2007 examined 13,000 queries and 22,000 search result clicks from a query log, and found that 40% of the queries led to a click on a result that the same user had clicked on in a past search session.

As is discussed in Chapter 9, researchers have made use of query log behavior to try to improve ranking algorithms, as well as to attempt to predict individual user's behavior and preferences based on past actions.

3.7.5: Classifying Observed Search Behavior

The previous section describes the classification of information needs based on query log analysis. Another approach is to observe people more directly and classify their search activities more broadly.

Kellar et al., 2006a collected statistics for self-reported task type frequency for Web browser users. Twenty-one university student participants used an instrumented Web browser that recorded their actions for one week, resulting in 1,192 task sessions (13,500 web pages). Participants were asked to label every Web page access with a task type from the taxonomy. The authors carefully developed a task type taxonomy to remove confusion about their meaning and ensured that the study participants would be able to consistently assign labels. The five main categories were:

• Fact Finding: Looking for specific facts or pieces of information; usually short lived tasks, completed over a single session. Examples were looking, searching or checking for tomorrow's weather, a recipe, a file (for download), a research paper, definitions, help with a game, java documentation, song lyrics, the average mass of a bullet.

• Information Gathering: A task that involves the collection of information, often from multiple sources. Can take place over multiple days. It is not always clear when the task is completed and there is not always one specific answer. Examples were looking for or researching information on a new laptop, conferences, new wireless card, making a resume, papers on policy-based network, renting a car, risk analysis, summer school courses.

• Browsing: A serendipitous task where Web pages are visited with no particular goal other than entertainment or to “see what's new.” Sometimes this is done as part of a daily routine. Examples were looking for or reading blogs, browsing a Web site, the news, listening to music, movie trailers, updates on movie Web site, comics, wasting time.

• Transactions: Online actions. Examples were checking or acting on email, banking, applying for a credit card, blogging, logging diet and exercise information, online shopping, sending a greeting, taking part in a survey.

• Other: Other activities, such as Web page maintenance.

Table 3.3 shows the frequency of activities according to the taxonomy. Nearly half the Web usages were attributable to online transactions, primarily email usage. Fact finding constituted about 18% of the tasks, and more than 55% of these were repeat activities. Repeated fact finding often had a monitoring aspect, such as checking the weather forecast daily. Information gathering was about 13% of the activities; many stretched over several days including one that lasted six days (researching graduate schools to apply to). Browsing constituted 19% of the tasks and included news reading, reading blogs, visiting gaming-related sites, and reading entertainment-related Web pages. There was evidence that monitoring occurs with different frequencies across different tasks.

Unfortunately, there are problems with attempting to compare these results to the query log studies described above. These are broader task classifications, so a subgoal like find the home page of an e-commerce site would be subsumed into online shopping. Thus, statistics of the more fine-grained activities seen at the query level (e.g., navigational queries) are not categorized as such. The tasks described correspond to all Web pages viewed, as opposed to only those examined in response to a search. And finally, many of the categorizations differ from both Broder, 2002's and Rose and Levinson, 2004 's. For example, in Kellar et al., 2006a accessing information about iPod prices is classified as information gathering, while the online shopping part of the process (potentially including the price comparison component) is categorized as transactional. Rose and Levinson, 2004 would list the search for the shopping information under informational and Broder, 2002 would classify it as transactional.