Does SPIMI assign one permanent term identifier before processing everything?

Its classic formulation uses terms in each block's dictionary rather than requiring a complete global term-to-identifier map in memory.

Can it store positions?

A practical postings design can include them, but they increase storage and require appropriate merging.

Is it a distributed algorithm?

The basic method is a block-based indexing approach; distributing indexing across machines introduces additional design choices.

AI Glossary / Retrieval and knowledge systems / Intermediate

Single-pass in-memory indexing

Definition

Single-pass in-memory indexing, usually abbreviated SPIMI, builds an inverted index by accumulating a block of term postings in memory, writing that block to disk and repeating as needed. The block indexes are then merged. It avoids first sorting a large stream of term-identifier and document-identifier pairs.

What it means

An inverted index maps a term to the documents containing it. Building one for a large collection requires controlling memory use, because neither all documents nor the full vocabulary may fit in memory at once.

SPIMI creates a dictionary for the current block. As each term arrives, the algorithm immediately appends or updates its information in that term's postings list. When the block reaches its memory budget, it is written out and a fresh dictionary is started.

Single-pass does not mean that the entire index remains in memory or that there is no later disk work. The original token stream is processed incrementally, while final merging reads and combines the intermediate block files.

How it works

A document-processing stage produces terms associated with document identifiers. For each term in the current block, a dictionary lookup finds its postings list or creates one. The list grows as more occurrences arrive.

When memory is exhausted, the dictionary terms are sorted and their postings are written in a consistent order. This term ordering makes the later merge manageable. SPIMI avoids sorting every token pair, but it does not eliminate all sorting from the construction process.

A merge combines entries for the same term across blocks into the final postings list. Practical implementations must define how repeated occurrences, term frequencies and positions are stored. Processing documents in identifier order can keep postings naturally ordered within a block, while the merge reconciles the block streams. Compression can reduce intermediate storage and transfer costs.

Three practical examples

An archive builds a searchable index from a collection larger than its available memory.
A desktop search prototype constructs block indexes incrementally rather than collecting every term-document pair before inversion.
A teaching implementation compares SPIMI with blocked sort-based indexing to examine different memory and sorting requirements.

Think of it this way

Think of sorting incoming correspondence into labeled trays until the desk is full. You pack the labeled trays in a consistent order, clear the desk and continue. Later, you combine trays carrying the same label.

The analogy does not imply that all papers fit on the desk at once. It also highlights the later consolidation step: finishing each deskful is not the same as finishing the complete filing system.

Worked example

Two blocks become one index

Use an invented document-presence index, where each document identifier appears at most once in a term's postings list. D1 contains red blue red; D2 contains blue green; D3 contains red green.

Suppose the memory policy flushes a block after D2. Block one contains blue → [D1, D2], green → [D2] and red → [D1], written in term order. The second occurrence of red in D1 does not create another document-presence posting; a frequency-aware version could separately store its count of two.

Block two contains green → [D3] and red → [D3]. Merging yields blue → [D1, D2], green → [D2, D3] and red → [D1, D3]. There were seven input token occurrences but six final term-document presence pairs. The example's block boundary is stipulated for clarity, not derived from a real byte-level memory measurement.

Illustrative case study

The fictional MapleArchive team builds search for a growing set of reports. Its first prototype collects every token pair before sorting and runs out of memory on larger imports. The team experiments with block-based SPIMI construction.

The new design writes partial indexes as memory fills. Reviewers then discover that the disk-space plan includes only the final index, omitting intermediate blocks and merge output. They revise the construction workflow and test interrupted runs as well as successful ones.

This case illustrates resource planning around the algorithm. It reports no actual throughput improvement or claim that SPIMI removes all operational limits.

Common misconceptions and mistakes

Single-pass means there is no merge. Multiple block indexes still need consolidation.
SPIMI never sorts anything. It avoids sorting the full token-pair stream, while sorting dictionary terms before writing a block.
In-memory means the whole collection must fit in RAM. Memory holds the current block; disk stores completed blocks and the final index.

Business use

SPIMI is useful when building an inverted index for a large, primarily static collection on limited memory. Its design makes the current block's dictionary and postings the main in-memory structures.

Estimate memory for dictionary entries, dynamically allocated lists and occurrence information, not just raw text. Plan for temporary disk files and merge work. Confirm that tokenization and document identifiers remain consistent across blocks, and check the merged index against small known examples. Frequently changing collections need additional update and deletion mechanisms; SPIMI construction by itself is not a complete design for continuous index maintenance.

Check your understanding

A SPIMI implementation avoids sorting token pairs but sorts the dictionary before writing each block. Is that a contradiction?

Answer: No. Those are different operations. Directly accumulating postings avoids the token-pair sort, while ordered dictionary output supports the final merge.

Related terms

Inverted index
Dictionary
Blocked sort-based indexing
Positional index
postings list
index construction
external merge
index compression

Learn next

Read inverted indexes and blocked sort-based indexing. Trace a small token stream through two memory blocks and verify that merging preserves each term's document identifiers, frequencies and any stored positions.

Blocked sort-based indexing

Sources

Christopher Manning, Prabhakar Raghavan and Hinrich Schutze, Introduction to Information Retrieval, Single-pass in-memory indexing: https://nlp.stanford.edu/IR-book/html/htmledition/single-pass-in-memory-indexing-1.html

The authors' original description of block dictionaries, direct postings accumulation, term sorting and merging was reviewed. The three-document example is original and explicitly uses document-presence postings. No implementation benchmark or literal unlimited-capacity claim is made.

Previous: Single instruction, multiple threads Next: Single program / multiple data