The Boolean model is the oldest retrieval model still in everyday use, and the simplest. A query is a logical expression of terms joined by AND, OR, and NOT, and a document is retrieved if and only if it satisfies the expression. There are no scores and no ranking, only a set of matching documents. That simplicity made Boolean retrieval the basis of the first large commercial search services, and its precision and predictability keep it in use today wherever searchers need to control exactly what is retrieved. Legal research, patent searching, systematic reviews, and the filters on nearly every product search page all rely on it.
This topic is also where the inverted index built in text processing and indexing is first put to work. Answering a Boolean query is a matter of combining postings lists, and the algorithms for doing that efficiently are used by every retrieval model that follows. These algorithms include the linear merge, skip pointers that jump over parts of long lists, and query plans that process the rarest terms first. Ranked retrieval finds its candidate documents with the same operations, intersecting postings for conjunctive queries and merging them for disjunctive ones. Positional indexes, introduced here for phrase queries, support the proximity features that later ranking functions use.
The topic ends with the model's limits. A Boolean query tends to retrieve either too many documents to read or too few to be useful, and the searcher can only adjust the query by trial and error. The vector space model, the next topic, replaces the yes-or-no decision with a graded score.
Articles
The model
- The Boolean retrieval model: queries as logical expressions, documents as sets of terms, evaluation with the incidence matrix worked row by row, queries as regions of a Venn diagram, normal forms and their exponential blow-up, and the strengths and weaknesses of exact matching.
Processing queries
- Intersecting postings lists: the linear merge for AND, the corresponding algorithms for OR and AND NOT, their costs, and intersection by binary or galloping search when one list is much shorter, measured against the merge.
- Skip pointers: shortcuts within postings lists that let an intersection jump over entries that cannot match, the square-root rule for placing them derived as a cost trade-off and tested by experiment, and when they help.
- Optimizing Boolean queries: processing terms in order of increasing document frequency, estimating the size of OR clauses, where to apply NOT, rewriting queries with Boolean identities, and adaptive intersection, with every plan for a three-term query measured.
- Phrase and proximity queries: biword indexes, positional indexes, the positional merge and window algorithms traced on positions, and proximity operators.
- Parsing and evaluating Boolean queries: a grammar with operator precedence, a recursive-descent parser traced call by call, query trees, the parser behind this site's search box, and lessons from my course assignment.
In practice
- Boolean search in practice: professional query languages, the comparison of Boolean and ranked search, extended Boolean models, and how web search treats a query as an implicit AND.
Related topics
- The inverted index and index compression describe the structures these algorithms operate on.
- Search in professional domains explains why lawyers, patent examiners, and systematic reviewers continue to prefer Boolean queries.
- The vector space model introduces ranked retrieval.
Course materials
My Boolean query processor for the course is HW02 on GitHub. It parses queries with AND, OR, NOT, and parentheses, evaluates them against an extended version of the HW01 inverted index, and orders the matching documents by TF-IDF.
References
- Croft, W. B., Metzler, D., and Strohman, T. (2010). Search Engines: Information Retrieval in Practice, section 7.1. Addison-Wesley.
- Manning, C. D., Raghavan, P., and Schütze, H. (2008). Introduction to Information Retrieval, chapter 1 and sections 2.3–2.4. Cambridge University Press.