= Postings list
A <postings list> is the collection of records associated with one term in an <inverted index>. Each record identifies a document containing the term; optional fields include its <term frequency> in that document and, for a <positional index>, occurrence positions. The number of distinct document records is the <document frequency>, which differs from the total number of occurrences.<Introduction to Information Retrieval by Christopher D. Manning and others>[§1.2, inverted-index construction and document frequency; §2.4.2, positional postings]{ref}
For documents 1 `red red boat`, 2 `blue boat`, and 3 `red train`, the document identifiers in the `red` <postings list> are $1,3$. Its <document frequency> is two, although `red` occurs three times. The `boat` <postings list> contains $1,2$. Their intersection is $1$, answering `red AND boat`.
With identifiers in increasing order, compare the current identifiers and advance whichever is smaller; when equal, emit that identifier and advance both. Each advancement consumes a record, so intersecting lists of lengths $m,n$ costs $O(m+n)$ comparisons in this simple merge algorithm. Ordering gives a direct route from stored evidence to a query result without reading every document's text.<Introduction to Information Retrieval by Christopher D. Manning and others>[§1.3, Processing Boolean queries, Figure 1.6 and the linear intersection bound]{ref}
Back to article page
