Boolean Retrieval — Mini Lesson & Interactive Demo

Try it

Use operators AND, OR, NOT, and parentheses ( ). Terms are case-insensitive; operators are case-insensitive too.

Example queries: information AND retrieval (web OR internet) AND crawling ranking AND NOT pagerank "inverted index"

What is Boolean retrieval?

Boolean retrieval answers exact match queries using set logic over documents. A query is built from terms (tokens) and logical operators:

A AND B — documents containing both A and B
A OR B — documents containing A or B (or both)
NOT A — documents that do not contain A
Parentheses control precedence: A AND (B OR C)

Under the hood, an inverted index maps each term to the set (or sorted list) of document IDs that contain it. Query processing combines these posting lists with fast set operations.

Evaluation quick take

Metric	Meaning
Precision	Of the docs retrieved, how many are relevant?
Recall	Of the relevant docs, how many did we retrieve?

Strengths & limits

Transparent logic; easy to explain
Fast with compressed posting lists
No ranking by default (results are sets)
Queries can be brittle; vocabulary mismatch

How the demo works

Tokenize each document into terms (lowercased, stripped of punctuation).
Build an inverted index: term → {docIDs}.
Parse the query to a syntax tree (supports quotes for phrases).
Evaluate the tree using set operations over posting lists.
Highlight matched terms/phrases and list matching documents.

Study cheatsheet

Core concepts

Tokenization & normalization
Dictionary & postings lists
Conjunctive vs disjunctive queries
Skip pointers & efficient merging

Operator precedence

NOT > AND > OR (unless parentheses override)

Phrases in "double quotes" are treated as exact sequences.

Complexity intuition

Conjunctive queries cost ~ the sum of traversed posting lengths; ordering terms by increasing df can reduce work.