Information Storage and Retrieval: Inverted Indexes and Posting Lists

Lesson overview

Build the core indexing structure used by text retrieval systems: the inverted index, including terms, posting lists, document frequency and positional information.

CourseInformation Storage and Retrieval

Topic strandIndexing

Assessment styleWorked scenario, applied task and digital exam practice

EvidenceDefinitions, representation, method, result and interpretation

Starter

Write down the user need, the data being stored or searched, and the decision the system has to support. Then predict which representation, index, query method or governance control will matter most in this lesson.

Learning objectives

Construct a small inverted index by hand.
Explain posting lists, document frequency and term positions.
Use an index to answer Boolean and phrase queries efficiently.

Learning outcomes

Students can construct a small inverted index by hand.
Students can explain posting lists, document frequency and term positions.
Students can use an index to answer Boolean and phrase queries efficiently.

Key vocabulary, acronyms and terminology

inverted index: A mapping from terms to the documents or positions where they occur.
posting list: The list of documents, counts or positions associated with one term.
document frequency: The number of documents containing a term.
positional index: An index storing term positions for phrase or proximity queries.
dictionary: The term vocabulary stored by the index.
merge: Combining posting lists to answer compound queries.

Detailed teaching notes

Core concept

An inverted index reverses the document view. Instead of scanning every document for a word, the system looks up the word and immediately sees candidate documents.

Representation choice

For each term, the index may store document ids, term frequencies, positions and field information. More detail increases storage cost but enables better ranking, phrase search and snippets.

Method and reasoning

To build a small index, tokenise each document, normalise terms, assign document ids and append each occurrence to the term's posting list. To answer AND queries, intersect posting lists.

Risk and limitation

A non-positional index can answer whether terms occur, but it cannot prove that terms occur as a phrase or near each other.

Degree-level deep dive

The index reverses the lookup

An inverted index maps a term to the documents that contain it. Posting lists may also store frequency, positions, fields and payloads, which determine whether the system can support ranking, snippets and phrase queries.

Efficiency depends on representation

Intersecting posting lists can answer multi-term queries efficiently, but only if the lists are sorted and compressed sensibly. Positional indexes cost more storage but enable phrase and proximity evidence.

What excellent work shows

A strong answer can build a tiny inverted index by hand, show a posting list lookup, and explain which extra information is needed for ranking or phrase search. It should distinguish index structure from document storage.

Concrete example to study

Three-document index

D1: database search systems
D2: search index design
D3: database design
Postings:
database -> [D1, D3]
search -> [D1, D2]
design -> [D2, D3]

Reasoning

A query for 'database search' intersects [D1, D3] with [D1, D2], giving D1.
A ranked system may also keep term frequency and field information.
A positional index would be needed to answer phrase queries such as 'index design'.

Reveal takeaway

The inverted index is the central structure that makes term lookup efficient, and the extra data stored in postings determines which retrieval features the system can support.

Worked example

Scenario

D1='web search', D2='web crawler', D3='search index' are indexed.

Worked solution

Tokenise and normalise the three documents.
Create postings: web -> D1,D2; search -> D1,D3; crawler -> D2; index -> D3.
For query web AND search, intersect postings for web and search.
The intersection is D1, so only D1 contains both terms.

Reveal model result

The inverted index avoids scanning D1 to D3 at query time. In a real system the saving is much larger because collections contain millions or billions of documents.

\text{Define the data, choose the representation, apply the method, interpret the result.}

Applied retrieval task

Build an inverted index for five short document titles.

Deliverables

Show the dictionary terms.
Write posting lists with document ids.
Answer one AND query and one phrase-query question.

Success checks

The answer uses posting-list operations.
Phrase search mentions positions if needed.

Common misconception

An inverted index is not the same as a database table scan. It is a specialised access structure built so retrieval can start from terms.

Quick checks

1. In this lesson, why does inverted index matter?

It replaces the need to understand user tasks or data representation.It is only a presentational label and has no effect on retrieval quality.A mapping from terms to the documents or positions where they occur.

2. Which answer best shows degree-level understanding of inverted indexes and posting lists?

Give a final recommendation without showing how the data or query was represented.Define posting list, apply it to the scenario, then explain the trade-off or risk.Name as many technologies as possible without explaining the scenario.

Digital exam practice

Example exam task

Given three short documents about web crawling and indexing, construct an inverted index and use it to answer the query 'crawler AND index'. In your answer, define the relevant objects or data structures, use course-specific vocabulary, show the method rather than only the result, and finish with a decision about the storage or retrieval system.

Notation and technical toolkit

index[t] = [(d_1,p_1),...]posting list for term t Use to show where a term occurs.

df(t)document frequency Use to count how many documents contain t.

AND = intersectionBoolean query operation Use when merging posting lists.

What a good answer is expected to show

A strong answer for Inverted Indexes and Posting Lists the answer should show tokenisation, posting lists, document frequency and the posting-list merge used to answer the Boolean query. It should connect the formal or technical representation to the user's information need instead of listing terms without using them.

How to solve it

Assign document ids and tokenise each document.
Build the inverted index term by term.
Record document frequency for relevant terms.
Intersect posting lists to answer the AND query.

Model answer

Reveal model answer

I would first normalise the document terms, then create a dictionary where each term points to a posting list. If crawler appears in D2 and D3, and index appears in D1 and D3, then query crawler AND index is answered by intersecting those posting lists. The result is D3. Document frequency is the length of each distinct document posting list and can later support ranking weights such as IDF.

Practise next

Add positions to a posting list and explain how it supports phrase search.
Show why OR queries use union rather than intersection.

Self-marking criteria

Defines the scenario objects, data forms or system components before solving.
Uses the lesson vocabulary accurately and in context.
Shows a clear method with enough working for a marker to follow.
Connects the result back to retrieval, storage, analytics or governance.
States a limitation, trade-off or quality risk rather than presenting the answer as absolute.

Extension

Estimate how posting-list compression would matter for a million-document collection.

Study route

Save a short worked answer from this lesson using this pattern: define the need or data, choose the representation, show the method, state the result and interpret the implication for the system.

Next lesson: Precision, Recall, F-Measure and Evaluation.