Boolean Search in Practice

A lawyer looking for cases about whether a host is liable for injuries caused by a drunk guest might type, into a legal research service,

host! /p (responsib! liab!) /p (intoxicat! drunk!) /p guest

This is a Boolean query in the language of Westlaw's "terms and connectors" search (Manning, Raghavan, and Schütze, 2008, §1.4). The ! truncates a word, so liab! matches liable and liability. A space between words means OR, not AND. /p requires its operands to appear in the same paragraph, and /s in the same sentence. Read piece by piece:

Without the paragraph conditions, the query is a conjunction of four concepts, each written as an OR of variants, host* AND (responsib* OR liab*) AND (intoxicat* OR drunk*) AND guest. That is the conjunctive normal form expert searchers favour. The /p connectors then tighten each AND to co-occurrence within a paragraph, which requires a positional index that records paragraph boundaries. Every part of the query is under the searcher's control, and every retrieved case can be explained by the terms it matched. Such queries are written by trained professionals, often over many iterations, and they remain in heavy use decades after ranked retrieval became the default elsewhere.

This article surveys how the Boolean model is used and extended in practice: in professional query languages, in the long comparison between Boolean and ranked retrieval, in models that give Boolean queries graded scores, and in the query handling of modern search engines.

Professional query languages

Commercial search services for law, medicine, patents, and news developed query languages that extend AND, OR, and NOT with operators suited to expert searching:

• Truncation and wildcards. employe! matches employee, employer, and employment. The searcher controls the conflation explicitly, instead of relying on a stemmer.
• Proximity. /3 (within three words), /s (same sentence), and /p (same paragraph) are stronger than AND and weaker than an exact phrase. All of them require a positional index, and the sentence and paragraph operators also require it to record sentence and paragraph boundaries.
• Field restrictions. Searches can be limited to a case's title, its headnotes, the judge, or the date, or to a medical article's subject headings.
• Phrases. Quotation marks require an exact sequence: "trade secret".

Two further queries from the same source show the style. For the need "requirements for disabled people to be able to access a workplace":

disab! /p access! /s work-site work-place (employment /3 place)

and for "legal theories involved in preventing the disclosure of trade secrets by employees formerly employed by a competing company":

"trade secret" /s disclos! /s prevent /s employe!

Queries like these take skill to write. A searcher who knows the vocabulary of the field and the operators of the system can retrieve a focused set of documents, and can document exactly what was searched. That is why, as search in professional domains describes, legal researchers, patent examiners, and systematic reviewers continue to prefer them.

Boolean or ranked?

Whether expert Boolean queries retrieve better results than ranked retrieval was debated for decades, and the evidence mostly favors ranking, with qualifications.

Turtle (1994) compared the two on legal collections. Experienced searchers wrote Boolean queries for a set of research problems, and the same problems were expressed as natural-language descriptions and run through a ranked retrieval system. The ranked natural-language queries retrieved more relevant documents near the top of their rankings than the expert Boolean queries did. Blair and Maron's earlier study (1985) of a full-text litigation support system had shown that its Boolean searchers greatly overestimated their own recall: they believed their searches had found at least 75 percent of the relevant documents, when about 20 percent had been found. The experimental literature since TREC has generally found ranked retrieval more effective, on average, than unranked Boolean retrieval for typical information needs.

The qualifications explain why Boolean search persists. Averages hide tasks where control and reproducibility matter more than average effectiveness, such as a systematic review that must report its search exactly. Experts often use Boolean queries iteratively, inspecting results and refining the query, which a single-query comparison does not capture. And many professional systems now combine the two, allowing a Boolean query to define the set of documents and ranking the documents within it.

Grading Boolean matches

Several models keep the structure of a Boolean query but replace its yes-or-no answer with a score, so that results can be ranked.

Fuzzy-set retrieval assigns each document a membership weight between 0 and 1 for each term, rather than simply 0 or 1, and evaluates AND as the minimum of its operands' weights and OR as the maximum (Kraft and Buell, 1983). A document strongly associated with every term of a conjunction scores high, and one weakly associated with any term scores low.

The extended Boolean model of Salton, Fox, and Wu (1983) interpolates between strict Boolean logic and the averaging of the vector space model. For term weights $w_1, \dots, w_n$ in $[0, 1]$ and a parameter $p \ge 1$, the p-norm scores are

$$\mathrm{sim}_{\mathrm{OR}} = \left(\frac{w_1^p + \dots + w_n^p}{n}\right)^{1/p}, \qquad \mathrm{sim}_{\mathrm{AND}} = 1 - \left(\frac{(1 - w_1)^p + \dots + (1 - w_n)^p}{n}\right)^{1/p}.$$

The parameter $p$ controls how strict the operators are. For a document containing one of two ANDed terms fully ($w_1 = 1$) and the other not at all ($w_2 = 0$):

At $p = 1$, AND and OR are the same, both equal to the average of the weights, as in a vector space model. As $p$ grows, AND approaches the strict Boolean answer of 0 for a document missing a term, and OR approaches 1 for a document containing any term. In the limit $p \to \infty$, the p-norm operators become exactly the minimum and maximum of the fuzzy-set model. Intermediate values give partial credit: a document missing one term of a conjunction is ranked below one that has both, but above one that has neither.

The limit follows from a short argument. Let $w_{\max}$ be the largest weight. Every term of the OR sum is at most $w_{\max}^p$, and at least one equals it, so

$$\frac{w_{\max}^p}{n} \le \frac{w_1^p + \dots + w_n^p}{n} \le w_{\max}^p, \qquad\text{hence}\qquad \frac{w_{\max}}{n^{1/p}} \le \mathrm{sim}_{\mathrm{OR}} \le w_{\max}.$$

As $p \to \infty$, $n^{1/p} \to 1$, so $\mathrm{sim}_{\mathrm{OR}} \to w_{\max}$. The AND formula applies the same mean to the complements $1 - w_i$, whose largest value is $1 - w_{\min}$, so $\mathrm{sim}_{\mathrm{AND}} \to 1 - (1 - w_{\min}) = w_{\min}$. Large $p$ makes the mean attend only to the extreme weight, which for AND is the worst-matched term.

Ranking five documents

The effect on a ranking shows best with several documents. Take a query t1 AND t2 and five documents with these term weights:

Strict Boolean retrieval returns A, B, D, and E as an unordered set and drops C, which lacks $t_2$ entirely. The p-norm ranks all five. At $p = 1$, C ties with D: a perfect match on one term and none on the other averages to the same 0.5 as a half match on both. At $p = 2$, C falls below D, and from $p = 5$ on it falls below E, a weak match on both terms. Throughout, D scores exactly 0.5, because a document with equal weights has the same mean for every $p$. The parameter thus sets how heavily a missing term is penalized, from not at all ($p = 1$) to completely ($p = \infty$). For t1 OR t2 the movement is reversed: C rises from 0.500 at $p = 1$ to 0.871 at $p = 5$ and passes B, since one strong match is what OR rewards.

Points above and to the right of a curve score more than 0.5. The figure makes the geometry of the model visible: p-norm AND rewards balance across terms, and OR rewards the single best term, with $p$ controlling how strongly. All the scores in this section come from tools/experiments/boolean/pnorm.py. The model performed well in experiments but was rarely adopted in commercial systems, which tended to keep strict Boolean semantics for filtering and use separate functions for ranking.

Required and optional clauses

Modern search libraries expose a practical descendant of these ideas. In Lucene and the engines built on it, a query is a combination of clauses, each marked as required (must match), prohibited (must not match), or optional (should match). Required and prohibited clauses act as Boolean AND and AND NOT, defining which documents qualify. When a query has at least one required clause, optional clauses do not restrict the set, unless a minimum number of them is required to match, but each one that matches adds to the document's score. A query made only of optional clauses behaves like an OR: a document must match at least one of them. A query can therefore combine an exact Boolean filter with a ranked preference, for example requiring a product category, excluding out-of-stock items, and ranking the rest by text relevance. The Boolean model survives as the filter, and ranking operates within it.

The implicit AND of web search

Web search engines present a single box, but a Boolean model has traditionally operated behind it. By default, a query of several words was treated as an AND, and the engine first looked for pages containing every word. That default was then relaxed in several ways:

• A page can match a word it does not contain if the word appears in the anchor text of links pointing to it.
• Query words are expanded with variants: other inflections, spelling corrections, and synonyms (see how a web search engine answers a query).
• If too few pages contain all the words, the engine relaxes the conjunction, accepting pages that contain most of them.

Most importantly, the matching pages are ranked, so the size of the result set no longer matters. The searcher reads the top results, not the whole set. That removes the feast-or-famine problem described in the Boolean retrieval model, which was the main difficulty of using Boolean systems. Explicit operators remain for those who want them: quotation marks for phrases, a minus sign for NOT, and restrictions such as site:. Few searchers use them (Manning, Raghavan, and Schütze, 2008, §1.4). In effect, web search turned Boolean retrieval from the interface into an internal step. It selects candidates, and ranking decides what the user sees.

From exact match to ranking

The history of Boolean search follows the course's direction. Exact matching gave way to graded matching, first in experimental models such as p-norms and then in the ranked models that dominate today. The next topic, the vector space model, develops the graded alternative from first principles: represent documents and queries as weighted vectors, and rank documents by their similarity to the query.

References

• Blair, D. C., and Maron, M. E. (1985). An evaluation of retrieval effectiveness for a full-text document-retrieval system. Communications of the ACM, 28(3), 289–299.
• Kraft, D. H., and Buell, D. A. (1983). Fuzzy sets and generalized Boolean retrieval systems. International Journal of Man-Machine Studies, 19(1), 45–56.
• Manning, C. D., Raghavan, P., and Schütze, H. (2008). Introduction to Information Retrieval, section 1.4. Cambridge University Press.
• Salton, G., Fox, E. A., and Wu, H. (1983). Extended Boolean information retrieval. Communications of the ACM, 26(11), 1022–1036.
• Turtle, H. (1994). Natural language vs. Boolean query evaluation: A comparison of retrieval performance. In Proceedings of SIGIR 1994, 212–220.