4.1.1: Search Over Surrogates vs. Full Text

In older bibliographic search systems, users could only search over metadata that hinted at the underlying contents. To look for a book on a topic in an online library catalog, the searcher was restricted to the text in the title or the few subject labels that the librarian who had catalogued the book had used to describe it (Borgman, 1996b). A book that mentions an interesting idea, but only in a secondary manner, would most likely not be indexed with that term (Cousins, 1992). Using a standard library catalog, a searcher who was interested in discussions of narwhales in literature would not have been able to discover that Moby Dick contains several discussions of these unicorn-like fish. Search over full text gives users direct access to the words used by the author, rather than being restricted to matching against a document surrogate. Full-text search has become the norm for most kinds of search over textual content.

4.1.2: Keyword Queries

With the rise of the Web came the dominance of keywords as the primary query input type. Keyword queries consist of a list of one or more words or phrases -- rather than full natural language statements -- whose intention is to find documents containing those words that are likely to be relevant to the user's information need. Example English keyword queries (from Google Trends and Dogpile SearchSpy, November 1, 2008) include flip cam, fresh chilli paste recipes, and video game addiction. Some keyword queries consist of lists of different words and phrases, which together suggest a topic (e.g., early voting florida). Many others are noun compounds and proper nouns ( thanksgiving wallpaper, jedi mind tricks, sherlock holmes, and daylight savings time change). Less frequently, keyword queries contain syntactic fragments including prepositions ( tots to teens, matron of honor speech) and verbs ( watch pokeman), and in some cases, full syntactic phrases ( history of fish farming in nigeria, construction plans for a trebuchet).

Statistics on query length and composition have been recorded since early in the Web's existence. These measures have shown that the average query length has grown over time, and the percentage of one-word queries has shrunk. Average query lengths were approximately 2.4 in 1997 and 1998 (Silverstein et al., 1999, Jansen et al., 1998). One-word queries occupied 31% of the queries in a study using data from 1997 (Jansen et al., 1998) and 26% from a study using data from 1998 (Silverstein et al., 1999). Jansen and Spink, 2006 found inconclusive evidence for a slight trend toward the shrinking of the percentage of one-word queries. By contrast, another study by Jansen et al., 2005 found the percentage of three word queries increasing from nearly 28% in 1998 to 49% in 2002. More recently, Jansen et al., 2007b conducted a study using 1.5M queries gathered in May 2005, from the Dogpile.com search engine. This study found that the mean length of the queries was 2.8 terms, with only 18.5% as one-word queries. Table 4.1 shows the distribution of query lengths for this dataset.

In the early days of the Web, search engines used statistical ranking functions, but these did not work well with the short keyword queries that Web searchers were writing. Furthermore, searchers were not usually interested in high recall for the kinds of information available on the Web. Searchers also found statistical ranking on short queries to be confusing, not understanding why, say, the highest ranked documents might contain only one query term out of three (Lake, 1998).

The meaning of search term conjunction is more easily understood than statistical ranking (Muramatsu and Pratt, 2001). However, when only a small collection of documents is available, a ranking algorithm that automatically requires all terms in a query to be present in the retrieved documents will end up with empty results sets (and very frustrated users) much of the time. With a larger document pool, a query on any combination of three or fewer terms is likely to return a result, even if all the terms are conjoined. Because the number of (English) pages on the Web is so enormous, conjoining query terms is likely to return many results, and because they are more transparent to the user than a weighted term score, conjunction-based queries became the default for Web search.

Conjunction-based queries, combined with giving higher priority to results in which keywords occur close together, displaying of query keywords in context in the document summary (Clarke et al., 2007), and giving higher ranking to pages from higher quality Web sites, combined to make search engine ranking of keyword queries more successful and more understandable than in its early days.

As discussed above, in Web search engines, keyword specification and matching has become the norm. An alternative to keyword queries is to allow users to enter full sentence questions or search statements, and have the system attempt to find relevant information and/or supply answers to questions. Evidence from the literature suggests that asking questions using natural language is a more intuitive input method, and that people who are new to using search engines tend to assume that asking a question is the right way to start. This is not surprising, since asking questions is how we seek information from other people.

In an early study from 1997, Pollock and Hockley, 1997 found that some novices try to enter natural language queries to Web search engines. Studies of the behavior of children who have not yet learned the limitations of search engines show that for many their natural inclination is to simply ask the search system a question. Bilal, 2000 found, in a study of 22 seventh-grade children searching for factual information, 35% attempted to begin with a natural language question. The search engine under study produced empty results sets with this kind of query, and so the children had to unlearn the question-asking approach. In another study by Schacter et al., 1998, 63% of 32 fifth and sixth-grade children used full-sentence queries on Web search engines. In a pre-web study using an electronic encyclopedia, Marchionini, 1989 found that many younger searchers entered full sentence questions into the system. Finally, in the early days of the Web, the search engine AskJeeves (now Ask) purported to allow people to ask natural language questions. Although it never really supported this functionality in a robust and scalable way, many people were attracted to the engine because they thought it would be able to answer questions.

Pollock and Hockley, 1997 also found that, for novice searchers, the notion of iterative searching was unfamiliar. They assumed that if their first attempt failed then either they were incapable of searching or the system did not contain information relevant to their interest. Thus, novice searchers must learn to expect that they must scan a search results list, navigate through Web sites, and read through Web pages to try to find the information they seek. A novice searcher who starts with a question like “For NFL players who have suffered depression after sustaining multiple concussions, which positions did they play?” quickly learns that the search engine does not respond by answering this question. Searchers must learn that search engines work by finding articles that match the words that they typed in, and that they must guess which combinations of words are likely to be found in documents that contain relevant information, e.g., NFL depression concussions.

Aula et al., 2005a note one expert explicitly articulating a strategy to reflect the unnatural nature of keyword querying, stating “I choose search terms based not specifically on the information I want, but rather on how I could imagine someone wording a site that contains that information.” Reflecting on the disconnect between keyword search and what might be a more natural search strategy, a lead engineer for ranking at Google was recently quoted as saying “Search over the last few years has moved from `Give me what I typed' to `Give me what I want.”' (Hansell, 2007).

4.1.3: Automated Question Answering

The most natural use of natural language queries is in the asking of questions. The main reason search engines did not originally support automated question answering is that the technology did not exist to do so in a robust, scalable manner. (There were also early efforts to supply natural language interfaces to database systems, which did not catch on for similar reasons (Androutsopoulos et al., 1995).)

There has recently been an upsurge of research in full-sentence question answering, propelled in large part by an increase in government funding and by a TREC-based question answering task and competition (Voorhees, 1999, Voorhees, 2003). For several years starting in 1999, the track focused on factoid questions: fact-based short-answer questions such as What Spanish explorer discovered the Mississippi? and When did World War I end? Subsequent competitions added the tasks of finding a list of answers to the question, e.g., Who were the members of the Oakland A's starting lineup in 1976?, definition questions such as What is a golden parachute?, and general biographical questions such as Who is Marilyn Monroe? that require systems to combine information from multiple documents, and to synthesize a more general answer. In 2005 the task was made still harder, requiring systems to provide answers for a series of cascading questions. For example, When was Amway founded?, Where is it headquartered?, Name the officials of the company., and What is the name `AMWAY' short for? The corresponding research has resulted in systems that, for factoid-type questions especially, can enjoy great success.

Rather than generating an answer from scratch, question answering systems attempt to link a natural language query to the most pertinent sentence, paragraph, or page of information that has already been written. They differ from standard search engines in that they make use of the structure of the question and of the text from which the answers are drawn. An early example of an automated general-topic question answering system was the Murax system (Kupiec, 1993), which determined from the syntax of a question if the user was asking for a person, place, or date. It then attempted to find sentences within encyclopedia articles that contain noun phrases that appear in the question, since these sentences are likely to contain the answer to the question. For example, given the question “Who was the Pulitzer Prize-winning novelist that ran for mayor of New York City?”, the system extracted the noun phrases “Pulitzer Prize”, “winning novelist”, “mayor”, and “New York City”. It then looked for proper nouns representing people's names (since this is a “who” question) and found, among others, the following sentences:

The Armies of the Night (1968), a personal narrative of the 1967 peace march on the Pentagon, won Mailer the Pulitzer Prize and the National Book Award. In 1969 Mailer ran unsuccessfully as an independent candidate for mayor of New York City.

Thus the two sentences link together the relevant noun phrases and the system hypothesized (correctly) from the title of the article in which the sentences appear that Norman Mailer was the answer.

Another early approach to automated question-answering was the FAQ Finder system (Burke et al., 1997) which matched question-style queries against question-answer pairs on various topics. The system used a standard IR search to find the most likely FAQ (frequently asked questions) files for the question and then matched the terms in the question against the question portion of the question-answer pairs.

Numerous more recent approaches use variations of the Murax approach, adding statistics that utilize the vast collection of the Web to successfully answer many kinds of questions (Dumais et al., 2002, Harabagiu et al., 2000, Ittycheriah et al., 2001, Ramakrishnan and Paranjpe, 2004, Ravichandran and Hovy, 2001). There are a number of startup companies that build on this research and attempt to support natural language querying and question answering using scalable natural parsing and other computional linguistics technologies. For example, the startup Powerset (recently acquired by Microsoft) successfully responds to questions like What did Steve Jobs say about the iPod? with sentences like Steve Jobs has stated that Apple makes little profit from song sales, although Apple uses the store to promote iPod sales. and Steve Jobs has argued that the iPod nano was a necessary risk ... and questions such as origins of the word Halloween? with sentences like The term Halloween is shortened from All Hallows' Even. This works in part by expanding words like “say” to “has argued” and “word” to “term”.

Major Web search engines currently do not support full-sentence queries or question answering, most likely because the technology still is not reliable enough to present in mature products. However, as discussed in Chapter 1, some are becoming more adept at responding to long queries. Natural language queries are also likely to become an important supplement for organizations' web sites and for software products, to more effectively handle customer questions.

An interesting aspect of question answering that differentiates it from standard information retrieval is that the answer of interest contains words that are not in the query. Thus boldfacing the query terms in answer to a question is not the right thing to do -- rather, it is the answer that should be highlighted. A question also arises as to what kind of and how much context to show surrounding the answer. An advantage of question answering is that the user can receive a simple, terse answer, such as 30 feet to the question How deep is it safe to dive without worrying about getting the bends? But a contextless answer from a machine-based source is not necessarily the best interface, as a reasonable user would want the system to justify, explain, or at least show the context supporting the answer. Lin et al., 2003 conducted a usability study with 32 computer science graduate students comparing four types of answer context: exact answer, answer-in-sentence, answer-in-paragraph, and answer-in-document. To remove effects of incorrect answers, they used a system that produced only correct answers, drawn from an online encyclopedia. They found that most participants (53%) preferred paragraph-sized chunks, noting that a sentence did not supply much more information beyond the exact answer, and a full document was oftentimes too long. That said, 23% preferred full documents, 20% preferred sentences, and one participant preferred exact answer. Kaisser et al., 2008 performed a followup-study which showed that for many queries, the ideal answer length and type can be predicted by a person by seeing only the query. They also found that people judging relevance prefer results of different lengths, depending on the type of query. For a fact-based query, phrase or sentence-length results were preferred. For queries seeking advice or general information about a topic, longer answers were preferred.

4.1.4: Paragraph-length Textual Queries

Another form of text-based querying is one in which the user requests that the system find documents that are substantially similar to a very long query or a user-supplied document. This kind of query was much studied in the information retrieval research literature in the 1980s-1990s. The emphasis was on producing retrieval results with high recall, since finding all relevant documents can be quite useful for scholars trying to do thorough literature reviews, legal professionals trying to find all information about a case (Blair and Maron, 1985), and intelligence analysts trying to assess a situation.

This desiderata of high recall was embodied in the TREC competition ad hoc ranking task (TREC is discussed in Chapter 2), where the goal was to retrieve 1000 relevant documents for every query. In the TREC scoring, what mattered was whether or not a document had been judged relevant, not how relevant it was, nor how much new information it brought beyond what had already been seen. (A system would not be penalized if the first k retrieved documents all contained redundant information.) It was found that long (paragraph-length) queries produced higher recall than short queries.

For long queries, it is unlikely that every term will be found in one document within a collection, and so are best served by statistical ranking algorithms which apply empirically determined weights to each query term, and combine them statistically to provide a ranking.

It is unclear how realistic it is to expect people to search for documents that are similar to other documents. (A startup company named DeepDyve is currently promoting search using large paragraphs of text as the query, and research documents as the collection, to improve search as a research tool.) However, text similarity measures are very useful for specialized tasks, such as automatic text categorization (Sebastiani, 2002), matching reviewers to submitted manuscripts (Dumais and Nielsen, 1992), and clustering similar news articles for news aggregation services (Das et al., 2007).

4.1.5: Automated Transformations of Textual Queries

Search engines may manipulate or transform textual queries in several ways. Some systems automatically normalize morphological variants of words, that is, convert a query on dogs to one on (dog OR dogs) or convert building to (build OR building) (the latter may lead to poor results, because the noun form of build is conflated with the verb form derived from building). This practice is sometimes known as stemming. Other transformations include ignoring common function words ( stopwords), and expanding terms with synonyms or related forms (e.g., converting mold to mould).

Search engine ranking algorithms must walk a fine line between making transformations that are hidden but helpful and making the user feel that the system is inscrutable. As mentioned in Chapter 1, Muramatsu and Pratt, 2001 studied users' understanding of the transformations that search engines apply to query terms. Fourteen participants were asked to issue one pre-specified query across two search engines for each of four transformation types: Boolean operators, stopword removal, suffix expansion, and term order variation. Queries and search engines were carefully chosen to exaggerate and highlight the effect of the query transformation, and participants were asked to first state what they thought would happen before seeing the results. In detail, the transformations investigated and the participants' responses to them were:

• Application of Boolean operators, comparing a search engine that automatically OR'd all terms versus one that AND'd terms. The query was scuba snorkel arooba ; the misspelling of “aruba” was used to force the AND'ed engine to produce an empty results listing. Eight out of 14 participants expected the system to return many results related to both scuba and snorkeling but few if any mentions of Aruba. After seeing the results, 5 participants could not come up with a meaningful explanation of the results; 6 were close to accurately describing the difference, but 3 required the side-by-side comparison to do so. The last 3 participants could explain the behavior for the AND query but not the OR.

• Stopword removal, comparing a system that removed stopwords versus one that did not, on the query to be or not to be (all stopwords). Before the query was issued, 10 out of 14 expected to see results related to Shakespeare and/or Hamlet. After seeing the empty results for one engine, 3 participants assumed the search engine did not contain literature in its collection or had a different collection, 6 expressed low expectations for good results because of the commonality of the words, but only 3 expressed the notion of the search engine dropping the results. 9 out of 14 were unable to explain the results in a way that remotely resembled removal of stopwords.

• Suffix term expansion, comparing a search engine that does the expansion versus one that does not (in this case the query was run which would be expanded to running and runner). Participants were surprised at the lack of results pertaining to athletics for the engine that did not do term expansion, and only 3 participants were able to explain the results in a manner related to suffix expansion.

• Term order sensitivity, comparing a search engine that changes results based on term order and proximity versus one that does not consider either property. In this case, two queries were compared: fire boat and boat fire. Only 5 out of 14 participants expected the results for the two queries to differ, and only 5 participants had a vaguely accurate explanation for the difference, with one person stating that one engine “separates the two words and searches for the meaning” while the other “understands the meaning of the phrase”. In scanning the bolded query term hits in the document surrogates, some participants noticed the difference in proximity for ranking.

These results suggest that stemming is useful, but removing stopwords can be hazardous from a usability perspective. It also suggests that certain features, such as taking order and proximity into account, can be used to improve the results without confusing users despite the fact that they may not be aware of or understand those transformations. Other studies suggest that it is better to show potential transformations to users and let them decide whether or not to use them than to do them explicitly; however, if automatic transformations are unlikely to lead to misconceptions, they can be beneficial.

Another way search systems use query transformations is to show them as suggestions for revising the query. This topic is discussed extensively in Chapter 6.

4.4.1: Term Proximity in Boolean Queries

In general, proximity information can be quite effective at improving precision of searches (Hearst, 1996, Clarke et al., 1996, Tao and Zhai, 2007). The most commonly used operator on the Web is the double-quote operator "", used to surround adjacent words, as in "San Francisco", which signifies that the enclosed terms must be found directly adjacent in the retrieved text. The disadvantage of exact match of phrases is that it is often the case (in English) that one or a few words fall between the terms of interest (as in big black dog when searching on big dog). Another consideration is whether or not stemming is performed on the terms included in the phrase. The AOL adjacency operator is similar to double quotes except that it allows for morphological variants, and can be combined with other operators, e.g., (abraham OR abe) ADJ lincoln will find matches for both abe lincoln and abraham lincoln. The AOL search engine also supports proximity queries in the form of a NEAR operator, e.g., dogs NEAR/3 cats means find the word dogs within 3 words of cats, in either order. In some cases the best solution is to allow users to specify exact phrases but treat them as if they indicated small proximity ranges, with perhaps an exponential fall-off in weight according to the distance between the terms. This has been shown to be a successful strategy in non-interactive ranking algorithms (Clarke et al., 1996). Some web search engines provide behavior related to this in select circumstances. For example, Google often ignores middle initials when doing matches against people's names, even when those names are enclosed in double quotes.

4.4.2: Post-Coordinate and Faceted Boolean Queries

One technique for imposing an ordering on the results of Boolean queries is post-coordinate or quorum-level ranking [Ch. 8]{salton89}. In this approach, documents are ranked according to the size of the subset of the query terms they contain. So given a query consisting of cats dogs fish mice, the system would rank a document with at least one instance of cats, dogs, or fish higher than a document containing 30 occurrences of cats but no occurrences of the other terms. eBay introduced an interesting way of expressing search results according to coordinate or quorum-level ranking. When no results are found for a query such as gap ultra low rise 8r, the searcher is shown a view indicating how many results would be brought back if only k out of n terms were included in the query, as illustrated in Figure 4.8.

Another approach to improving results with Boolean queries is to have the searcher break their query up into different facets, that is, different topics, and specify each facet with a set of terms combined into a disjunction. The entire query is then combined into one conjunction, in effect indicating that at least one term from each concept should be present in the retrieved documents (Meadow et al., 1989a). Combining faceted queries with quorum ranking yields a situation intermediate between full Boolean syntax and free-form natural language queries.

An interface for specifying this kind of interaction can consist of a list of entry lines. The user enters one topic per entry line, where each topic consists of a list of semantically related terms that are combined in a disjunct. (This sort of query works naturally with the interface shown in Figure 4.9.) Documents that contain at least one term from each facet are ranked higher than documents containing terms only from one or a few facets. Hearst, 1996 showed that when at least one representative term from each facet is required to be in close proximity with one another, the resulting precision is very high. However, this kind of querying specification is not commonly used in practice. Instead, facets are now widely used in navigation interfaces for collections (see Chapter 8).

4.4.3: Web-based Improvements to Boolean Query Specification

In command-line based interfaces, Boolean operators and their operands are typically typed on one line, and combined using parentheses (see Figure 4.10a). Although Web search engines support use of operators directly in the query box, they usually also supply a graphical form-based method for using filters and restrictions. Figure 4.9 from the Education Resources Information Center (ERIC) shows an example.

By serving a massive audience possessing little query-specification experience, the designers of Web search engines devised what were intended to be more intuitive approaches to Boolean query specification. Early versions of Web search interfaces used drop-down menus and Web forms that allowed users to choose from a selection of simple ways of combining query terms, including “all the words” (place all terms in a conjunction) and “any of the words” (place all terms in a disjunction). These kinds of options are still available in the “Advanced Search” option of many Web search engines (see Figure 4.11).

Another early web-based solution was to allow syntactically based query specification, but to provide a simpler or more intuitive syntax. In the mid-1990s, the AltaVista Web search engine introduced the mandatory operator, meaning that the results retrieved must include the query term, indicated with a + as a prefix before the required word. At that time, Web search results were ranked using statistical algorithms, and so the top results for a three-keyword query might not contain all of the query terms (if, for example, the algorithm chose to rank a document with 100 occurrences of the first keyword ahead of a document with one occurrence of all three keywords). The mandatory operator gave users more control over how the search engine treated their keywords. Unfortunately, users sometimes mistakenly thought the + acted as an infix AND rather than a prefix mandatory operator, thus assuming that cat + dog will only retrieve articles containing both terms (where in fact this query requires dog but allows cat to be optional). The need for this operator became obviated after search engines began returning only those documents that contain every keyword.

Researchers have developed many clever interface designs to improve Boolean query specification via visual interfaces. These attempts at visualizing Boolean queries are discussed in Chapter 10, but have not been widely adopted in practice. The one exception is for database query specification, an area in which graphical command building applications have become popular. However, searching over structured information is inherently different than searching over unstructured text.

4.4.4: Query Operator Usage Statistics

As discussed above, the major search engines offer a number of operators that can be applied to queries to make them more focused and exact. However, Web log statistics show that only a small fraction of queries take advantage of these operators. It is difficult to obtain accurate statistics from current Web search engines, so below are reported a set of statistics that have been gleaned by researchers using the few available open Web log resources. The actual numbers most likely fall somewhere in the middle of the reported ranges.

A meta-analysis by Jansen and Spink, 2006, which analyzed seven query log studies between 1997 and 2002, found that the percentage of search operator use has remained steady over time. Spink et al., 2002 showed a Boolean usage rate of about 10% for Excite users. Jansen et al., 2005 reported a Boolean usage of about 6% and a usage of other query operators at approximately 15%. The most recent study by Jansen et al., 2007b, conducted over 1.5M queries, found that 2.1% contained Boolean operators and 7.6% contained other query syntax, primarily double-quotation marks for phrases. White and Morris, 2007 studied interaction logs of nearly 600,000 users issuing millions of queries over a period of 13 weeks in 2006. They found that 1.1% of the queries contained at least one of the four main Web operators (double quotes, +, -, and site:) and 8.7% of the users used an operator at least one time.

Hargittai, 2004's study showed that even among the small fraction of users who did attempt to use operators, several completely misunderstood their meaning. None of the participants used the negation operator -, although at least one put a space before the hyphen in what was intended to be a hyphenated term: lactose intolerant -recipes, thus ensuring that no relevant results were returned. 16% of the participants used double quotation marks, but a few of them used them incorrectly or superfluously. One participant put quotation marks around almost every individual word, and another, apparently having misunderstood some advice from a friend on how to improve her results, put them around all terms in her query, thus often yielding empty result sets.

It may be the case that operators are only used by advanced searchers. For the White and Morris, 2007 study described above, they partitioned users into experts and non-experts based on whether or not they had used operators in their queries. They found significant differences in search behaviors between these two groups; the experts had different behavior when navigating search results, and they were more successful at eliciting and clicking on relevant documents. Aula and Siirtola, 2005 also found evidence that expert searchers were those more likely to use operators, based on questionnaire data filled out by 236 experienced Web users. Those with information seeking professions were more likely to say they use Boolean and other operators.

There is evidence that Web search engine ranking algorithms have been successful at compensating for the fact that their users do not use query operators. Eastman and Jansen, 2003 studied the effects of removing search operators from 100 queries selected from query logs and compared the resulting documents to those retrieved by the advanced query. They found the use of most query operators had no significant effect on coverage, relative precision, or ranking, although the impact did vary depending on the search engine.