Bag-of-Words Retrieval

The defining characteristic of BoW is the disregard for grammar and word order. A document is represented solely by the multiset (bag) of its words.

• The sentences 'The dog bit the man' and 'The man bit the dog' produce identical BoW representations.
• This simplification enables efficient indexing but loses all syntactic and relational meaning.
• The model relies entirely on lexical overlap between query and document terms.

Documents are converted into sparse vectors where each dimension corresponds to a unique term in the vocabulary.

• The value in each dimension is typically the term frequency (TF) — the raw count of occurrences.
• This creates a document-term matrix that is mostly zeros, enabling highly compressed storage via inverted indices.
• Example: 'to be or not to be' becomes a vector with non-zero entries for 'to' (2), 'be' (2), 'or' (1), and 'not' (1).

Unlike a simple set of words, the BoW model preserves term multiplicity, which serves as a primary signal for relevance.

• A document containing 'AI' five times is considered more relevant to an 'AI' query than one containing it once.
• This is the basis for term frequency saturation in ranking functions like BM25.
• The raw count is stored but often transformed via sublinear scaling (e.g., log(1 + TF)) to prevent term spamming from dominating scores.

The BoW representation is entirely dependent on a predefined vocabulary derived from the document collection.

• The vocabulary size directly determines the dimensionality of the vector space, which can reach millions of terms for large corpora.
• Out-of-vocabulary (OOV) terms in a query cannot be matched, causing retrieval failures.
• Preprocessing steps like tokenization, stop word removal, and stemming critically shape the vocabulary and downstream matching behavior.

The core weakness of BoW is the vocabulary mismatch problem, where relevant documents use different words than the query.

• A query for 'automobile' will completely miss documents using only the term 'car'.
• This limitation is addressed by query expansion techniques like synonym filters and pseudo-relevance feedback.
• Modern systems overcome this by combining BoW-based sparse retrieval with dense semantic retrieval in hybrid search architectures.

The BoW model maps directly to the inverted index data structure, enabling sub-linear query evaluation.

• Only the postings lists for query terms need to be accessed, avoiding a full scan of all documents.
• This makes BoW retrieval extremely fast and scalable to billions of documents.
• The index stores, for each term, a list of document IDs and associated term frequency counts needed for BM25 scoring.

A numerical statistic that reflects the importance of a word to a document in a collection. It is calculated by multiplying Term Frequency (how often a word appears) by Inverse Document Frequency (how rare the word is across the corpus). This weighting scheme is the direct precursor to BM25 and provides the foundational scoring mechanism for the Bag-of-Words model.

A database index data structure that maps each unique term to a postings list of documents containing it. This is the physical implementation that makes Bag-of-Words retrieval computationally feasible. Instead of scanning every document for a query term, the engine directly accesses only the relevant postings lists, enabling sub-second search across billions of documents.

A search engine component that processes raw text into a stream of tokens. It applies a chain of filters including:

• Tokenizer: Segments text into discrete tokens
• Lowercase Filter: Normalizes case for matching
• Stemmer: Reduces words to their root form (e.g., 'running' → 'run')
• Stop Words Filter: Removes high-frequency noise words like 'the' and 'is'

The analyzer's configuration directly determines the vocabulary of the Bag-of-Words model.

The fundamental retrieval problem where a relevant document uses different words to describe a concept than the words used in the query. For example, a query for 'physician' will miss documents containing only 'doctor'. This is the primary limitation of pure Bag-of-Words retrieval and motivates techniques like query expansion, synonym filters, and the shift toward semantic search using dense embeddings.