AI Glossary / Retrieval and knowledge systems / Intermediate
Document-at-a-time
Definition
Document-at-a-time is a search-query evaluation strategy that combines the contributions of query terms for one document before moving to another document. It commonly traverses several postings lists in a shared document order. The contrasting term-at-a-time strategy processes one term's list and accumulates partial scores across many documents. These are execution strategies; they do not inherently define different relevance formulas.
What it means
A query containing several terms can receive evidence from several index lists. The system must bring together the contributions that belong to the same document. Document-at-a-time evaluation organizes this work around document identifiers, completing each encountered document's score before advancing.
The phrase does not mean that the engine reads every original document from beginning to end. It can operate on compact index postings. It also does not imply that only one document in the entire system is processed at once; parallel partitions or queries can perform their own evaluation concurrently.
How it works
Maintain an iterator for each query term's postings list. When lists share a document ordering, compare their current identifiers, collect contributions for the selected document, advance the corresponding iterators, and update the result set.
A disjunctive query can consider documents containing any query term; a conjunctive query requires all of them. The matching condition and scoring formula determine which contributions are needed. More advanced document-at-a-time algorithms can skip work using valid score bounds, but the basic traversal alone does not justify stopping before all potentially competitive documents are considered.
Three practical examples
- A search engine can evaluate a multiword query by merging term postings and maintaining a small set of its best-scoring documents.
- A developer can compare document-at-a-time and term-at-a-time implementations while keeping the same scoring formula to verify equivalent exact results.
- A retrieval researcher can investigate safe skipping rules without confusing the traversal order with a change in relevance scoring.
Think of it this way
Think of assembling each customer's complete order by consulting several product lists, finishing one customer's total before moving to the next. The analogy is limited because a search engine may skip some candidates under proven conditions and can process different queries in parallel. The organizing principle is which record's contributions are combined together, not a universal ban on concurrent work.
Worked example
Consider an original query with terms red and blue. Assume an additive score using already-computed term contributions. Red's postings, ordered by document identifier, are (D1,2), (D3,1), and (D4,4). Blue's are (D2,3), (D3,5), and (D4,1). A missing term contributes zero. These numbers are stipulated scores rather than raw word counts or a particular named ranking formula.
For an OR-style candidate condition, begin with D1 at the red iterator and D2 at the blue iterator. D1 comes first, so its score is 2. Advance red to D3. D2 is now the smallest identifier, giving score 3, and blue advances to D3. Both iterators now point to D3, so combine its contributions: 1 + 5 = 6. Advance both to D4, whose score is 4 + 1 = 5. The exact ranking is therefore D3, D4, D2, D1.
If only the top two results are needed, maintain a two-item result structure while traversing. After D1 and D2 it contains scores 2 and 3. D3's score 6 replaces 2, and D4's score 5 replaces 3. The final pair is D3 and D4. Completing early documents did not mean they were the best; identifier order is not score order.
For an AND-style condition, only D3 and D4 contain both terms, so D1 and D2 are excluded rather than merely assigned lower scores. The shared traversal idea remains useful, but the match condition changes the candidate set.
A term-at-a-time implementation could first add all red contributions into per-document accumulators and then add all blue contributions. With complete evaluation and the same arithmetic, it obtains the same final scores. The difference lies in the organization of intermediate work, not in a new definition of relevance. No runtime comparison follows from this tiny trace.
Illustrative case study
Fictional case: a website team rewrites its query evaluator to reduce intermediate score storage. The new version completes documents through concurrent postings traversal, but an early prototype stops after finding the requested number of results.
A test query exposes the mistake: later document identifiers have higher scores. The team removes the unsupported stopping rule and compares full rankings with the earlier exact evaluator. Any later skipping optimization must use a valid bound or be clearly evaluated as an approximation.
Common misconceptions and mistakes
Do not assume the first K documents encountered are the top K results. A common document order supports merging, but it generally does not rank documents by query score. Do not describe every early-termination rule as exact without checking its assumptions.
Also distinguish disjunctive matching from conjunctive matching. Adding zero for a missing term is appropriate for the stated additive OR example; it does not make a document satisfy an all-terms requirement. Floating-point implementation details can affect ties or tiny score differences, so comparison tests should specify tie handling and numerical expectations.
Business use
Document-at-a-time evaluation is an implementation choice that can affect latency, memory use, and compatibility with skipping methods. Its value depends on postings lengths, query patterns, compression, scoring functions, and available hardware.
Validate correctness with small traces and representative queries before measuring performance. Keep ranking semantics fixed when comparing execution strategies. Record whether results are exact or approximate and how any bounds are computed. Test missing terms, repeated terms, tied scores, empty lists, and documents matching only one query term. These cases help separate traversal bugs from deliberate product behavior.
People also ask
Does document-at-a-time mean scanning every document's text?
No. It typically combines evidence from postings lists.
Does it necessarily produce different rankings from term-at-a-time?
No. Exact implementations using the same scoring formula can produce the same scores and ranking.
Can it support efficient top-K retrieval?
Yes, but safe pruning or early termination requires additional algorithmic conditions beyond document order alone.
Check your understanding
Why can the worked traversal not stop after scoring D1 and D2 for a top-two request?
Answer: Later documents may score higher. Here D3 scores 6 and D4 scores 5, exceeding both earlier scores.
Related terms
- Term-at-a-time
- Postings list
- Query evaluation
- Top-k retrieval
- Additive scoring
- Iterator
- Conjunctive query
- Disjunctive query
- Score bounds
Learn next
Add D5 with a red contribution of 10 and no blue contribution. Recompute the OR ranking and the AND result set. Explain why the same high contribution makes D5 competitive in one query interpretation but cannot satisfy the other interpretation's missing-term requirement.
More in Retrieval and knowledge systems
- Divergence-from-randomness model - A divergence-from-randomness model is an information-retrieval model that weights query terms according to how their occurrence in a document departs from a...
- Document clustering - Document clustering is the process of grouping documents according to patterns of similarity in their representations.
- Document partitioning - Document partitioning divides a search collection into subsets of documents and maintains a local index for each subset.
- Double moving average - A double moving average is a moving average applied to a series that has already been smoothed by a moving average.
- Embedding - An embedding is a numerical representation that places an item in a vector space where relationships can be useful for a machine-learning task.
- Embedding matrix - An embedding matrix is a table of numerical vectors, typically with one row for each token or category and one column for each embedding dimension.
Sources
Primary textbook source: Manning, Raghavan, and Schuetze, Introduction to Information Retrieval, Impact ordering and its discussion of document-at-a-time versus term-at-a-time evaluation: https://nlp.stanford.edu/IR-book/html/htmledition/impact-ordering-1.html . Postings, score traces, and examples here are original.
Previous: DOACROSS parallelism Next: Document classification