Information Retrieval

Scalable Index Construction and Compression Foundations

Published: 2026-09-14

Level: undergraduate

Audience: Undergraduate students studying Information Retrieval

Prerequisite Knowledge

This lecture builds on the following concepts from earlier lectures. If any feel unfamiliar, review the linked notes before proceeding.

Previously Covered in This Subject

From raw document to ranked output — covered in Lecture 1 (From Raw Document to Ranked Output)
Stemming and text normalization — covered in Lecture 1 (From Raw Document to Ranked Output)
Inverted index with dictionary and postings — covered in Lecture 2 (The Inverted Index: From Words to Documents)
Merge algorithm for AND queries — covered in Lecture 2 (The Merge Algorithm: Answering AND With One Forward Pass)

6.1 Memory Hierarchy and Cost of Disk Access

6.1.1 Why Index Building Meets Hardware Limits

Why does a search engine need disks at all when disks are so slow?

An inverted index (a map from each term to the list of documents that hold it) can grow past what main memory can hold. A search engine may deal with hundreds of thousands or billions of documents. The bag of words built from such a collection is humongous. It cannot all sit in fast memory at once.

Think of a small desk next to a large storage room. The desk is fast to reach but holds only a few books. The storage room holds thousands of books but each trip takes time. Memory is the desk. Disk is the storage room. Index construction keeps active work on the desk and stores finished blocks in the storage room in large boxes.

Fast memory is small. Slow storage is large. Access to data held in CPU registers, cache, and RAM is much faster than access to data held on disks and tapes. As we move down the pyramid from registers to cache to RAM to disks to tapes, access time goes up. Cost per byte moves the other way. Registers are costly and tiny. Tapes are cheap and huge.

A server may hold a few gigabytes of main memory. Disk space on the same machine can be tens or thousands of times larger, often a terabyte or more. During index construction we decide with care what stays in RAM and what gets written to disk. We accept slower disk access because there is no other place to keep a web-scale collection. The task of this material is to make that disk use fast and well managed.

Picture the pyramid with numbers. A byte in memory can arrive in a few clock cycles, about $5 \times 1 0^{- 9}$ seconds. The same byte from disk needs about $2 \times 1 0^{- 8}$ seconds of transfer plus a possible seek of about $5 \times 1 0^{- 3}$ seconds. The seek part is about a million times larger than one memory access. That gap is why random small reads hurt and large sequential reads help.

Scope: The pyramid trade holds when the index is larger than RAM. If the full term and posting structure fits in RAM, disk tuning adds little. When it does not fit, every design choice must cut random seeks. Assumption: Blocks read or written together sit next to each other on disk. If files get split into many small parts, the math below breaks in the bad direction.

A common trap is to treat RAM and disk as equal and to index the full collection in one in-memory sort. That plan runs out of space and slows to a crawl on turnaround. A second trap is to read one posting at a time from disk. Each tiny read pays a full seek. Batch work into large blocks instead.

Web search keeps only hot structures in RAM and spills the rest to disk in large blocks. Hot postings for frequent query terms stay cached. Cold postings stay on disk until needed.

Exam note: Expect a short conceptual question on why disks are needed despite slower access, and on the trade between memory size and access time. Answer line: memory is fast but small, disk is slow but large, so large sequential blocks keep disk cost low.

6.1.2 Mathematical Formulation of Seek Time and Transfer Time

How do we put a number on slow?

We use two hardware numbers from system measures in 2007 that are still used as a teaching baseline. Let $S$ be the seek time (the time for the disk head to move to the correct position, in seconds per seek). Let $B$ be the transfer time per byte (the time to move one byte once the head is in place, in seconds per byte). Standard values are $S = 5 \times 1 0^{- 3}$ seconds and $B = 2 \times 1 0^{- 8}$ seconds. Let $n$ be the count of seeks, with no unit. Let size be the byte count moved.

Transfer time for a chunk is size times the per-byte cost:

$T_{t r an s f er} = size in bytes \times B$

Seek cost grows with the number of head moves. If the head must seek $n$ times:

$T_{see k, t o t a l} = n \times S$

Total read time is the sum:

$T_{t o t a l} = T_{see k, t o t a l} + T_{t r an s f er}$

Here $T_{t r an s f er}$ is in seconds, $T_{see k, t o t a l}$ is in seconds, $n$ is a plain count, $S$ is in seconds per seek, $B$ is in seconds per byte, and size is in bytes. A seek (head move with no data moved) is pure wait. A transfer (byte flow with head in place) is useful work.

In words: 10 megabytes stored continuously on disk means the head moves once and then reads the whole block in order, with $B$ equal to $2 \times 1 0^{- 8}$ . Each seek costs $S = 5 \times 1 0^{- 3}$ seconds. For 100 seeks the cost is $100 \times 5 \times 1 0^{- 3}$ . Total time is seek time plus transfer time.

Operating systems read and write whole blocks, often 8, 16, 32, or 64 kilobytes at a time. Reading a single byte can cost as much as reading the full block that holds it. That is one more reason to group small postings into large sequential runs.

6.1.3 Worked Computation With Ten Megabytes Continuous and Scattered

Case one: 10 megabytes stored continuously in one place on disk. The disk head moves to the correct position once and reads the whole block in order.

Given: size $= 10 \times 1 0^{6}$ bytes, $B = 2 \times 1 0^{- 8}$ seconds per byte, $S = 5 \times 1 0^{- 3}$ seconds per seek.

Step 1 — transfer part:

$T_{t r an s f er} = (10 \times 1 0^{6}) \times (2 \times 1 0^{- 8})$

Work the numbers: $10 \times 1 0^{6} = 10, 000, 000$ . Multiply by $2 \times 1 0^{- 8}$ to get $20 \times 1 0^{- 2}$ , which is $0.2$ seconds.

Step 2 — seek part for one move: $T_{see k, t o t a l} = 1 \times 5 \times 1 0^{- 3} =$ $0.005$ seconds.

Step 3 — total with full detail:

$T_{t o t a l} = T_{see k, t o t a l} + T_{t r an s f er} = 0.005 + 0.2 = 0.205 seconds$

Rounded talk often says about $0.2$ seconds because the single $0.005$ seek is tiny next to $0.2$ . The full sum with the seek kept is $0.205$ seconds. An audible slip that sounds like 0.2005 is just that slip. The arithmetic gives 0.205.

Sense-check: 10 megabytes at 50 megabytes per second takes 0.2 seconds. That matches modern disk rates, so the result feels right.

Case two: the same 10 megabytes broken into 100 different places on disk. Each chunk needs its own head move and read. Transfer time stays $0.2$ seconds. Be it one 10 megabyte chunk or tiny pieces of it, transfer is still $0.2$ seconds only. What changes is seek count.

Given: same size and $B$ , so $T_{t r an s f er} =$ $0.2$ seconds, but now $n = 100$ .

Step 1 — seek total:

$T_{see k, t o t a l} = n \times S = 100 \times (5 \times 1 0^{- 3}) = 500 \times 1 0^{- 3} = 0.5 seconds$

Step 2 — total:

$T_{t o t a l} = T_{see k, t o t a l} + T_{t r an s f er} = 0.5 + 0.2 = 0.7 seconds$

Final answer: $0.7$ seconds for the scattered layout against $0.205$ seconds for the continuous layout. The scattered form costs more than three times as much for the same bytes.

Sense-check: 100 seeks at 5 ms each is half a second by itself. That half second dominates, so 0.7 seconds total is in the right range.

Scattered small writes and reads pay seek cost again and again. Large sequential blocks pay it once. In large-scale index construction we process and write data in large sequential blocks rather than many scattered pieces. That choice trades a little batching effort for much lower total read time.

Recap: memory is fast and small, disk is slow and large. Seek plus transfer sets read cost. Memory hierarchy from registers and cache to disks frames the tradeoff where blocks stay managed for speed. Continuous 10 megabytes costs about 0.2 seconds, scattered across 100 spots costs 0.7 seconds. This leads straight to block-based indexing next, where each block is one large sequential write.

6.1.4 Student Questions and Answers

Q: Are we talking about indexing the entire corpus here, the full static collection?

A: Yes. A retrieval system such as a search engine cannot live with a few documents. It holds thousands and thousands of documents, so the bag of words is humongous. We need a strong way to create indexes for that full collection. Instead of using very costly fault-tolerant machines, we use many regular machines joined as a cluster. The full-corpus view is why memory limits bite and why disk blocks and later distributed methods matter.

6.2 Reuters Collection and Inverted Index Recap

6.2.1 Reuters RCV1 as a Running Scale Example

What collection lets us test indexing ideas at a real but workable size?

The running example is Reuters Corpus Volume 1, called RCV1. It holds about 800,000 news articles sent over the Reuters newswire during about one year, from August 1996 to August 1997. Each article is plain news text with labels added by hand for topic, region, product, and similar fields.

Think of RCV1 as a shared practice ground. Just as runners train on the same track so times can be compared, retrieval teams test ranking and classification on RCV1 so scores can be compared. Hand labels for topics and regions make that fair test possible.

Key facts in one place: $N = 800, 000$ documents, about $200$ tokens per document on average, about $400, 000$ distinct terms, and about $100, 000, 000$ tokens in rounded teaching numbers. Unrounded counts are $806, 791$ documents, $222$ tokens per document, $391, 523$ distinct terms, and $96, 969, 056$ tokens. Articles carry manually assigned labels for topics, regions, sports, and other categories. That manual labeling is why the set is trusted as a benchmark. It is publicly shared, so it can be reused for practice.

The point of the numbers is scale. With 800,000 articles, term identifier and document identifier pairs can overwhelm memory. Turnaround time suffers because not all of it fits in registers or RAM. At 4 bytes per term identifier plus 4 bytes per document identifier, 100 million pairs need about $0.8$ gigabytes before any sort workspace. That one fact forces external sorting and disk blocks. The same collection is reused when retrieval time is computed and when compression examples are shown.

Benchmark labels for topic and region let teams compare ranking and classification methods on shared ground. A Reuters science piece on Antarctic clouds, for one, tests both text search and topic tags at once.

Recap: RCV1 is the yardstick collection for this lecture, about 800,000 labeled news articles. Its size breaks in-memory sorting, so disk-based methods are needed. This bridge leads to blocked indexing next.

6.2.2 How an Inverted Index Is Sorted Twice

How do we turn a pile of pairs into an index that answers fast?

Start from documents. First create term and document identifier pairs. A pair says a given term appears in a given document. Then build the inverted form by grouping on term.

An inverted index (postings grouped by term) is sorted twice. Terms, also called the dictionary, sit in alphabetical order. Postings, the document identifier lists inside each term, sit in ascending document order. That double sort is what makes later merge and lookup steps fast. The ordering can be written compactly, where $t_{i}$ is the $i$ -th term in dictionary order and $d_{j}$ is the $j$ -th document identifier in a posting list:

$t_{1} < t_{2} < \dots < t_{n} and d_{1} < d_{2} < \dots < d_{m}$

In words: alphabetical order of the terms and ascending order of the documents. Here $n$ counts distinct terms and $m$ counts postings for one term.

Picture raw pairs arriving in document order: data with D1, science with D1, words with D2, data with D2. After the double sort, all data postings sit together as D1, D2, then mining, science, words each with their own ordered lists. A chart of this step would show unsorted pairs on the left and neat term blocks with rising document numbers on the right. The takeaway from the picture is one line: sort once by term to group, sort again by document to order inside each group.

Tiny trace with four pairs: (data, D2), (science, D1), (data, D1), (words, D2).

Step 1 — sort by term, then by document: (data, D1), (data, D2), (science, D1), (words, D2).

Step 2 — group into postings: data mapped to [D1, D2], science mapped to [D1], words mapped to [D2].

Final check: terms run data < science < words alphabetically, and data postings run D1 < D2 in ascending order. Both sorts hold. This is the same double sort used at block level in BSBI and at merge level in SPIMI.

Scope: The double sort pays when postings are stored by document identifier and merged by linear scan. If postings were stored by weight for ranked retrieval, insert order would differ and updates would cost more. For Boolean build steps here, document order is the right call.

Sorted postings allow fast intersection for multi-word queries and fast merging of partial indexes. Two ordered lists meet in one linear pass with no hash table and no re-sort.

6.2.3 Preprocessing Choice With Apostrophes and Term Identity

Do apostrophes or commas start a new word?

Q: In the example there is a word with an apostrophe. Do apostrophes or commas make a separate word, or do we treat them as part of the word?

A: It is purely domain and document dependent. If the corpus can hold French words, a form with an apostrophe may be a distinct version and must be treated as a different term. If the apostrophe is just punctuation in the target use, preprocessing drops it during token handling. For a French term in an English-focused index, one option is to map the French form to its English form during preprocessing and then build the inverted index. The choice belongs to preprocessing and to the kind of documents at hand. Several learners asked this in different words, so treat it as the canonical term-identity rule.

This exchange matters because token rules change term counts, dictionary size, and later compression. The same surface string can be one term in one setup and two terms in another. Keep l-apostrophe forms apart for French text retrieval. Fold them together for plain English news search where the mark adds no meaning.

A second plain case helps. A comma after a word never forms part of the term. It is stripped. An apostrophe inside a word may or may not survive, based on language and task. That split is why preprocessing must be fixed before term counts are trusted.

6.3 Blocked Sort-Based Indexing

6.3.1 Why In-Memory Construction Cannot Scale

What breaks when we try to sort the whole web on one desk?

In-memory index construction keeps the full term and posting structure in RAM while it sorts. That plan cannot scale once the corpus is humongous. RCV1 alone with 800,000 documents already breaks it.

Remember the small desk from 6.1? Sorting a huge pile of cards on that desk fails. You sort a handful at a time on the desk, stack each sorted handful on the floor, then merge the stacks on the floor. Blocked sort-based indexing, called BSBI, follows that pattern. The desk is RAM. The floor is disk. Each handful is a block.

A concrete size sketch makes the limit sharp. Suppose each posting record needs 12 bytes in the lecture count, made of 4 bytes for the term part, 4 bytes for the document identifier, and 4 bytes for frequency. In symbols, where $S_{p os t in g}$ is posting size in bytes, $S_{t er m}$ is term identifier size, $S_{d oc}$ is document identifier size, and $S_{f r e q}$ is frequency size:

$S_{p os t in g} = S_{t er m} + S_{d oc} + S_{f r e q} = 4 + 4 + 4 = 12$

Now imagine sorting 100 million such records. Total raw size is:

$S_{t o t a l} = 100, 000, 000 \times 12 = 1, 200, 000, 000 bytes \approx 1.2 gigabytes$

That is about 1.2 gigabytes before space for sorting buffers and dictionary structures. The product is plain arithmetic from the two stated inputs, 12 bytes and 100 million records, so no outside fact is needed. Holding all of that plus sort workspace in RAM is not workable on an ordinary machine. That limit calls for a method that sorts in pieces.

Standard form note: the reference text counts a term identifier plus document identifier pair as $4 + 4 = 8$ bytes with no frequency field, which gives $100, 000, 000 \times 8 = 0.8$ gigabytes. The lecture count adds a 4-byte frequency field and reaches 1.2 gigabytes. Both forms point the same way: the sort does not fit. Keep the lecture 12-byte form for exam math and know the 8-byte book form as the lean pair form.

Scope: BSBI pays when the pair file is near or past RAM size. If the whole pair file plus sort buffers fit with room to spare, plain in-memory sort is simpler and faster. BSBI also assumes a static collection that can be sliced into blocks and merged once at the end.

Do not try to hold the global term map plus all pairs plus merge buffers at once. That triple load is what overflows. Also do not skip the final merge. Each block is sorted only inside itself, so cross-block order is still wrong until the merge runs.

6.3.2 BSBI Procedure in Steps

BSBI, which expands to blocked sort-based indexing, is also called sort-based indexing. The basic idea is to divide the bigger chunk into smaller blocks. Process documents in parts, build partial indexes in memory, write them to disk, and merge them.

Purpose: build a full non-positional inverted index for a static collection that is too large to sort in RAM, while keeping disk reads sequential.

Inputs and outputs: in goes raw text split into fixed-size blocks, for one toy split 10 megabytes out of 100 megabytes to make 10 blocks. Out goes one merged index with terms in alphabetical order and postings in ascending document order. Working memory holds one block plus a term to identifier map plus small read and write buffers for the merge.

Steps in order, with the reason for each step:

While all documents have not been processed, start a new block and raise the block number. The block is a fixed-size slice of the collection. Fixed size keeps each in-memory sort fast and even.
Parse the next block. Parsing turns text into term identifier and document identifier pairs and gathers them in memory until the block is full. In plain words, parse-next-block simply piles up pairs until the block budget fills.
Maintain a term to term identifier map while parsing. When a term is seen, check the map. If it is new, add it and give the next sequential number. If it is known, reuse its identifier. This map lives in main memory and is consulted for every block. A term identifier (a numeric serial number for a term) replaces long strings during sorting to save time and space.
Invert the block. Sort the gathered pairs by term as the main key and by document identifier as the second key, then group pairs with the same term identifier into a postings list. This is sorting at block level. Inversion (turning pairs into postings grouped by term) is this group step.
Write that partial index to disk as file $f_{n}$ . Repeat for each block until all blocks are done. Each file is one sorted run on disk.
Merge all block indexes into one final index. Merging needs one more sorting pass because each block was sorted only with respect to its own slice. In plain words, these indexes are only sorted with the text seen in this block, not with all blocks together, so the merge must fix global order. Open all block files at once with small read buffers plus one write buffer. Pull the smallest unseen term identifier through a priority queue, merge its postings from all blocks, write the merged list, refill buffers as needed.

In short: block, parse, map terms to identifiers, sort inside the block, write, repeat, then merge with a final sort. The helper names mentioned, such as parse-next-block, invert-block, write-block-to-disk, and merge of files $f_{1}$ to $f_{n}$ , are just labels for those sub-steps.

Time cost is governed by sorting. Sorting $T$ pairs costs about $Θ (T lo g T)$ comparisons in theory, but wall time is often set by parsing text and by the final merge with its disk moves. Space cost is one block in RAM plus sequential files on disk.

When to use BSBI: static collections on one machine with disk backing, where the vocabulary map still fits in RAM. When to move on: vocabulary too large for the map, or need for term compression on raw strings. Those limits motivate SPIMI next, which drops the global map and writes terms as is.

Exam note: Be ready to list BSBI steps in order and to state where sorting happens, inside each block and again at merge. Two sorts shape each block by term and by document identifier, and one more pass shapes the merged result.

6.3.3 Worked Example With Small Vocabulary

For ease of understanding the example uses terms, not numeric term identifiers. In the real algorithm data would be term 001 for data and term 002 for science, but words are shown here to keep the sort visible.

Setup: document one holds data and science. Document two holds words, data, and mining. Initial pairs in document order are (data, D1), (science, D1), (words, D2), (data, D2), (mining, D2).

Step 1 — collect pairs: five pairs total, in arrival order as listed above.

Step 2 — sort pairs by term, then by document: (data, D1), (data, D2), (mining, D2), (science, D1), (words, D2). Note the short check on whether M or S comes first in alphabetical order. M comes before S, so mining sits before science.

Step 3 — group into postings: data mapped to [D1, D2], mining mapped to [D2], science mapped to [D1], words mapped to [D2].

Step 4 — write this block index out. When later blocks hold the same term data again, the final merge step combines the block postings and fixes document order across blocks. In plain words, when we go to block two and term data comes again, we extend the document list there, and the final merge toward the end combines them.

Sense-check: data is the only term in two documents, so it is the only list of length two. That matches the input where data appears in D1 and D2. End state is correct.

This small case shows the three sort touches in BSBI. Two sorts shape the block index by term and by document identifier, and one more sort shapes the merged result.

6.3.4 Student Questions and Answers

Q: What is a term identifier? Is it a separate lookup we use when we split postings into chunks?

A: Yes. A term identifier is a numeric identifier assigned to a term, used as a lookup when postings are split into chunks. As documents are processed, check if the term is already in the dictionary. If not, add it and give the next sequential number. While handling the first block all terms enter that special structure in main memory. While handling the second block, many terms reappear, so reuse their identifiers instead of creating new ones. The lookup is a separate dictionary for terms to identifiers and has nothing to do with block size. The block fills to its size, for example 10 megabytes, then an inverted index is built inside and work moves to the next block.

Q: Where does the idea of a block come in? What happens when we move to block two?

A: Collect pairs, sort, and create the inverted index for one block. Once the first block is full, sort it and build its inverted index. That gives block one. Repeat until all blocks, for example ten blocks, are full. Then merge blocks $f_{1}$ through $f_{n}$ into $f_{m er g e d}$ . The merge step combines postings for the same term across blocks. Sorting of the posting list by term and by document identifier happens while creating the inverted index inside the block, and the final merge fixes cross-block order.

Q: Do we sort by both term and document before building the inverted index? How are terms processed, one document at a time?

A: Yes to both. Sort by term and by document, then build the inverted index. Inverted form must be sorted because sorted order makes later merging and multi-term intersection fast. Document identifiers in order allow the most streamlined merge passes. Terms are parsed from a document in order. For the same term in a later document, the posting for that term gains a new document entry in order, for example D2 then D3 then D4. Sorting inside the block keeps that growth tidy. Several learners asked these two linked points, so they are merged here as one canonical rule: parse in document order, sort by term plus document, then invert.

Recap: BSBI slices the collection, sorts each slice in RAM with a shared term map, spills sorted runs to disk, and merges runs once. This sets up SPIMI, which keeps the same slice-and-merge shape but drops the shared map.

6.4 Single-Pass In-Memory Indexing

6.4.1 Core Idea and Difference From BSBI

What if the term map itself is too large to keep?

SPIMI expands to single-pass in-memory indexing. The key idea is to generate separate dictionaries for each block with no term to term identifier map and no block-level inversion sort. Each dictionary block is treated as an inverted index that keeps growing while space lasts. Once memory for the block is full, write it out and start a new block. Merge and sort at the end.

Think of BSBI as sorting index cards by code number with one master code book. SPIMI drops the master code book. Each tray of cards carries its own handwritten labels. You file each card the moment it arrives. At the end you line up the trays by label. Filing on arrival replaces sorting a pile at the end.

Differences from BSBI, side by side:

Side	BSBI	SPIMI
Term identifiers	Maps each term to a numeric identifier through a shared dictionary kept in memory	Uses terms directly as they are, with no global identifier map
Per-block sort	Sorts pairs inside each block and builds a sorted block index before writing	Gathers postings as they are found and skips block-level sorting
Final sort	Sorts inside blocks and again at merge	Sorts only terms at merge time because document identifiers are already in order under its ordering premise
Memory pressure	Can overflow on the shared term map	Avoids that map, at the cost of keeping per-block dictionaries that are merged later
Compression	Holds numeric identifiers, which blocks direct term compression	Holds terms as is, so index compression on terms and postings can be used later

Put simply, BSBI pays for a global term map and repeated sorting. SPIMI pays for a final merge and sort but avoids the global map. When to pick which: pick BSBI for mid-size static builds where the map fits. Pick SPIMI when the vocabulary map itself threatens to overflow.

SPIMI time cost is about $Θ (T)$ for $T$ tokens because no token sort runs inside blocks. All per-token steps are hash lookup plus list append. BSBI time cost is about $Θ (T lo g T)$ because each block sort dominates. The saving comes with one key premise covered next: documents must arrive in order.

6.4.2 SPIMI Procedure in Steps

Purpose: index any size batch on one machine without holding a global vocabulary map, by building postings on arrival.

Inputs and outputs: in goes a token stream of term plus document pairs in document order. Out goes a set of block dictionaries on disk plus one merged sorted dictionary. Memory holds one active block dictionary with dynamic postings lists.

The method rests on one strong premise. Documents arrive in sorted order, D1 then D2 then D3. In symbols, where $d_{i}$ is the $i$ -th document identifier processed:

$d_{1} < d_{2} < d_{3} < \dots$

In words, the greater premise is that documents always come in sorted order, D1, D2, D3. If that premise breaks, the claim that postings are already document-sorted breaks with it. This is the warning to carry: never feed shuffled documents to SPIMI and trust posting order.

Steps in order:

Get tokens from the next document in order. The plain rule is get the tokens, and if the token belongs to the dictionary then add to the posting, otherwise create a new dictionary entry and posting.
If the token is already in the block dictionary, fetch its posting list and append the current document identifier. Because documents arrive in order, the posting list stays sorted with no extra sort.
If the token is new, create a dictionary entry and start its posting list with the current document identifier. The dictionary is best built as a hash for fast lookup.
If the block or posting allocation is full, grow the posting storage. The step called doubling the posting list is optimization only, with no extra logic beyond making room. Start short, double when full, so small lists waste little and large lists need few regrows.
Repeat until the block budget is full, then sort terms for that block and write the block dictionary to disk. Start a fresh block dictionary.
After all blocks are written, merge blocks into a final dictionary. Sort by terms only at this stage. Document identifiers need no resort under the ordering premise.

A tiny shape helps. Suppose block one sees to in D1, be in D1, to in D2, be in D2, not in D2, not in D3, to in D3, be in D3. SPIMI does not wait to collect all pairs. The moment it reads to with D1 it creates or extends that posting. When to reappears in D2 it directly updates the posting. Growth continues until the block is full. No pair pile ever waits for a sort.

The final merge fixes term order. Terms gathered as data, science, mining in arrival order become data, mining, science after term sorting. Postings keep document order, for example data mapped to D1 and D2, mining mapped to D2, science mapped to D1.

Scope: SPIMI needs sorted document input and enough disk for many block dictionaries plus merge buffers. It fits single-machine builds where memory is tight but document order can be set before indexing. If input order cannot be fixed, sort document identifiers first or fall back to BSBI.

Exam note: State the sorted-document premise and why it lets SPIMI sort only terms at merge. Line to keep: appends stay ordered only because D1 comes before D2, so only term order is left to fix.

6.4.3 Worked Example on the Same Terms

Reuse document one with data and science and document two with words, data, and mining, with terms shown as words for readability.

SPIMI walk, arrival by arrival:

Read data with D1. Data is new, so create data mapped to [D1].
Read science with D1. Science is new, so create science mapped to [D1].
Read words with D2. Words is new, so create words mapped to [D2].
Read data with D2. Data is already present, so extend to data mapped to [D1, D2]. No new dictionary entry. No sort runs.
Read mining with D2. Mining is new, so create mining mapped to [D2].

Block state before merge, in arrival order: data to D1, D2; science to D1; words to D2; mining to D2. At final merge, term sorting puts the dictionary in alphabetical order, giving data mapped to [D1, D2], mining mapped to [D2], science mapped to [D1], words mapped to [D2]. Document lists need no fix because D1 came before D2. Arrival build matches the BSBI end state.

Sense-check: same input as the BSBI trace gives the same postings. Only the path differs. BSBI collects then sorts. SPIMI files on arrival then sorts terms once.

Contrast with BSBI on the same input. BSBI would first collect all pairs, sort pairs by term and document, then build postings. SPIMI builds postings on arrival and sorts terms once at the end. The end state matches, but the path and memory use differ. SPIMI also keeps the term string with each list, so the term identifier field needs no room and blocks can run larger.

6.4.4 Student Questions and Answers

Q: We avoid a term identifier dictionary, but must we still store unique words to know if data already appeared in document two?

A: Yes. A dictionary for unique words in the block is still needed. When data from document two arrives, that per-block dictionary tells us data is already present, so we update its posting instead of creating a new term. The saving is that no global term to identifier map is kept across all blocks. Each block carries its own dictionary, and merging later reconciles them. Think tray labels, not a master code book.

Q: What is the need to double the posting list size when a block fills? Does it change block counts?

A: It is only an optimization for growing posting storage. It does not change block count logic. Doubling avoids repeated small reallocations while a block is still open. Whether we hold ten blocks of 10 megabytes or twenty blocks of 5 megabytes, the final merge must still be called. Blocks are common to both BSBI and SPIMI. Start small, double on full, waste little, copy rarely.

Q: Is the flow to write chunks and dictionaries first without caring about order, then merge, sort, and write to disk?

A: Partly. SPIMI writes per-block dictionaries as they fill, without block-level term sorting. After merging all blocks, sort terms and write the final block to disk. In the toy case that turns arrival order such as data, science, mining into sorted order such as data, mining, science. The per-block postings were already document-ordered under the sorted-input premise, so only term sorting remains at the end.

Recap: SPIMI files postings on arrival with per-block dictionaries, doubles lists to grow cheaply, and sorts only terms at merge. Document order in gives document order out. This single-machine win still hits a wall at web size, which is why distribution comes next.

6.5 Distributed Indexing With MapReduce

6.5.1 Why One Machine Is Not Enough

When does one good server stop being enough?

So far the view was single-machine indexing. One machine cannot build an index well once the collection reaches web size with billions of documents and many more term and document pairs, plus limits on memory and disk. The answer is distributed indexing on a large cluster.

Why split exam papers across evaluators? Questions 1 to 5 go to one evaluator, questions 6 to 10 go to another, then marks are combined for a final total. No single evaluator reads all papers. Here documents are split, parsed in parallel, partitioned by terms, then inverted into posting lists. Split work, then combine. That is the whole parallel idea in one familiar picture.

A cluster (a group of many ordinary machines joined to solve a large computing task) uses cheap commodity machines as nodes. A node is one machine tied to the cluster. Ordinary machines are cheap, so many can be joined. The trade accepted here is lower fault tolerance on any single box, handled at system level by reassigning work when a box fails or lags.

Resource needs come in three parts. Parsing and sorting need CPU. Temporary dictionaries and postings need memory. Intermediate and final indexes need disk. Large collections need all three at once. A single box runs out of at least one of the three, so the load must spread.

Data-center scale sets context. Google data centers circa 2014 are cited to give a sense of scale, with very large quarterly server installs and yearly data-center spend described as a share of world computing capacity. Yahoo M45 cluster is cited as another older scale marker. Exact install counts, spend figures, and node counts sounded noisy in the source, so treat them as order-of-size stories, not exact exam numbers. The durable point is simple: web indexing needs hundreds to thousands of boxes.

Exam note: Be ready to name CPU, memory, and disk roles in index construction and why a cluster is needed for web size. Line to keep: CPU parses and sorts, memory holds temp maps, disk holds runs and the final index.

6.5.2 Map Phase Splits Parsers and Term Partitions

MapReduce is presented as a design for parallel processing and distributed computing, with a map phase and a reduce phase. A master node hands out work. Worker nodes do parsing or inversion. Failed or slow work gets handed to another worker.

Map-side quantities use two equalities. Let $N_{s pl i t s}$ be the number of input splits and $N_{p a r ser s}$ the number of parser workers. Let $J$ be the number of term partitions and $N_{in v er t er s}$ the number of inverter workers. Then:

$N_{s pl i t s} = N_{p a r ser s}$

$J = N_{in v er t er s}$

In words, number of splits is equal to number of parsers, and partitions are equal to number of inverters. Here a split is a slice of input documents, a parser is a worker that turns a split into segment files, a partition is a term range assigned to one reducer path, and an inverter is a worker that builds postings for its term range. A segment file (one parser output for one term range) is the handoff unit between phases.

Concrete toy setting: 800,000 documents split into eight splits of 100,000, or into smaller splits of 10,000 when finer balance is wanted. Each parser takes its split and builds segment files. Segment files are then partitioned by term range. With $J = 3$ , ranges are A to F in one partition, G to P in a second, and Q to Z in a third. In plain words, parsers produce segment files and these segment files are partitioned by term range. Good split size in practice is tens of megabytes, often 16 or 64 megabytes, small enough to spread well but large enough to keep bookkeeping low.

The master decides split count and partition count. Split count must fit parser capacity. Partition count must fit inverter capacity, and key ranges need not be equal letters. They must give each inverter a similar load. While parsing, inverters are idle machines, so the master may reuse inverters as parsers. Likewise, once terms are ready in segment files and parsers turn idle, the master may reuse parsers as inverters. Nothing in this phase is sequential. It is parallel throughout. Parsers write segment files to local disk to cut network moves before the reduce step.

Splitting by size keeps work even across workers and keeps each worker inside memory limits. If a worker dies, its split is simply given to another worker.

6.5.3 Reduce Phase Inverters and Final Postings

Each inverter receives all term and document pairs for its term range, collects entries for the same term, sorts them, converts them into posting lists, and writes them to disk. In plain words, each inverter receives all term document pairs for its range, collects all entries from the same term, sorts them and converts them into posting list.

Toy run with $J = 3$ ranges A to F, G to P, Q to Z and 8 splits.

Step 1 — map: 8 parsers each read one split and emit three segment files, one per range. That gives 24 segment files in total, 8 for A to F, 8 for G to P, 8 for Q to Z.

Step 2 — group: the first inverter pulls all 8 A to F segments. The second pulls all 8 G to P segments. The third pulls all 8 Q to Z segments. Each segment needs only one sequential read on its parser box.

Step 3 — invert: each inverter groups by term, sorts document identifiers, and writes final postings. A query for information, which starts with I in G to P, is then directed to the second store, which holds documents holding that term. Map splits to parsers and partitions to inverters both hold: 8 splits to 8 parsers, 3 partitions to 3 inverters.

Index construction in words is two phases. First, parse documents and generate term and document pairs. Second, group all pairs for the same term and create posting lists. Input data is split into N splits sized so work spreads well and with low overhead. The map phase maps splits into key and value pairs of form (term identifier, document identifier). The reduce phase groups, sorts, and writes postings. In the small book demo with two documents, map emits (C, D2), (died, D2), (C, D1), (came, D1), (C, D1) for a Caesar text, and reduce groups C to D1, D1, D2 with counts, then writes postings with frequencies.

Q: Where does shuffling fit, is it in the inverter region before reduce?

A: Shuffling in the usual MapReduce sense happens right before the reduce step, when segment files move to their inverters. The response given is that exact placement in this setup needs a read-back, but the working idea is the same. Once segment terms are ready, idle parsers can be reassigned as inverters, and idle inverters can serve as parsers, because all of these are machines under master control. The master can reassign either way to keep parallel workers busy.

Scope: The term-partitioned build described here assumes each range plus its segments fits on one inverter and that all nodes share one term to identifier map. Very frequent terms with huge postings can break that premise. The fix is to split hot terms further or to convert the term-partitioned result into a document-partitioned layout for serving.

6.5.4 Term Partitioning Against Document Partitioning

There are two common ways to spread the final index. The MapReduce walk above used term partitioning. Document partitioning is the common choice in most search engines because it balances load better.

Term partitioning keeps one range of terms on each machine. The toy final state is A to F postings on disk one, G to P on disk two, Q to Z on disk three. A one-term query is easy. A two-term query can split. The stock example is apple and pi. Apple with A falls on the first disk, pi with P falls on the second disk in G to P. Exact spelling of the second term sounded noisy, but the disk split stands: first-range term plus second-range term forces two disks. The query information retrieval behaves the same way. Information with I sits on the G to P disk, retrieval with R sits on the Q to Z disk. The system must search more than one disk, fetch both posting lists, intersect documents, rank, and then retrieve. That is extra merge work and load imbalance across machines.

Document partitioning gives each machine a subset of documents with all terms for those documents. The same query information retrieval is sent to all document partitions, to disk one, disk two, and disk three in parallel. Matches come back from wherever the terms co-occur. Because related terms have a high chance of co-occurring in the same documents, most real queries find their answer set without cross-disk posting merges. That parallel fan-out balances load and avoids extra sort and merge on one box.

Rules carry over. Document count per partition must fit inverter and disk capacity, just as term range per inverter had to fit before. The only change is the partition key, documents instead of terms. Most large engines favor document partitioning for serving, even when the build used term ranges inside MapReduce.

Q: In document partitioning do we search across all disks, and is that slower?

A: Yes, the query is sent to all disks in parallel. Matches return from the disks that hold them, and in most real uses the usable set comes back without extra merge and extra sort. Because the fan-out is parallel, it is not slower in the sense of waiting disk by disk. It balances load across machines and cuts overhead on any single machine.

Exam note: Be ready to contrast term partitioning with document partitioning and to explain the apple pi and information retrieval imbalance cases. Line to keep: term split sends one query to many term disks and merges, document split sends one query to all document disks at once and merges little.

6.5.5 Student Questions and Answers

Q: How do we decide that A to F goes to the first segment and G to P to the second? How do term ranges link to inverters?

A: The master decides based on usable inverters and domain guidance. If only three inverters are free, terms are cut into three ranges such as A to F, G to P, and Q to Z. The count of ranges must match the count of inverters because all first-range segments combine in inverter one, all second-range segments in inverter two, and all third-range segments in inverter three. Idle inverters can also serve as parsers during parsing, and idle parsers can serve as inverters later, to keep the cluster busy. For even load, ranges must hold similar posting mass, not just similar letter counts.

Q: Is the index built continuously every second at Google scale, with new words added at once?

A: It is continuous in effect but split by resource. Part of memory and resources stays reserved for fresh indexes, for example fast-changing scores and rates during a tournament season. In that reserved area, insert, delete, and replace run as a continuous process while the main corpus stays searchable. New words and new documents enter through that path and are reconciled with the existing index. Failures add more issues, since ten distributed machines cannot be assumed to talk without fault, and job allocation plus parallel coordination must handle faults. MapReduce is the retrieval-side answer shown here for spreading parsing and inversion.

6.6 Dynamic Indexing and Logarithmic Merge

6.6.1 Main Index Plus Auxiliary Index

Static methods assume a fixed collection such as a one-year set. Real collections are dynamic. Scores, prices, conflict updates, fresh site articles, news feeds, sports news, weather reports, and article streams change every minute, hour, or week. Dynamic indexing updates the index without rebuilding everything from scratch each time. A news site may publish hundreds of articles per hour, and those must become searchable quickly or users leave.

How do you keep a shop open while restocking shelves? Keep the main shelves as they are for shoppers. Restock new goods on a small side table first. Shoppers look at both shelves and side table. At night you move the side table goods onto the main shelves. The main index is the shelves. The auxiliary index is the side table.

The simplest approach keeps two indexes by splitting resources. Keep a large main index and a small auxiliary index. New documents go to the auxiliary index. In plain words, new documents are added to auxiliary index, and whenever the query comes we search in both main index and auxiliary index. The auxiliary index stays in memory for speed. Searches run across both indexes and results merge.

Invalidation handles removals and replacements. For deletions, keep an invalidation bit vector that marks documents no longer valid. Search filters those marked documents away. Insert, delete, and replace run in the reserved area while queries read both indexes.

Think of workloads by change rate. Very hot items change by the minute. Warm items change by the hour. Cool items change by the week. The auxiliary path absorbs the hot flow. Periodic rebuilds still happen for the full index. Once the new full index is ready, query processing switches to it. Until then queries read both main and auxiliary structures.

Tournament scores where last-over figures turn stale within minutes, petrol prices, and newswire homepages all need the auxiliary path. Without it, fresh pages stay invisible until the next full rebuild.

Exam note: State the two-index rule, where new documents go, and that queries must read both indexes until a rebuild completes. Line to keep: new to auxiliary, search both, merge on full.

6.6.2 Deletion With Invalidation and Merge Tradeoffs

Deletion is logical first, physical later. Let $v [d]$ be the validity bit for document $d$ , with $v [d] = 1$ meaning live and $v [d] = 0$ meaning invalidated. In words, for deletions we use invalidation bit vector, we delete documents that are no more valid and filter them away from search. In symbols, retrieval keeps $d$ only if:

$v [d] = 1$

An update is delete plus insert: mark the old version $v [d] = 0$ , then add the new version as a fresh document in the auxiliary index.

Merging the auxiliary index into the main index is cheap only with the right file layout. If each posting list kept its own separate file, merge would be a simple append of the auxiliary list onto the main list. But millions of tiny files strain the operating system, which does not handle that many small files well. So real systems use a middle path. Some postings may be split. Very small postings may be grouped. Large postings may be handled on their own. The literature holds many more options beyond this sketch.

Simple merge math shows the pain. If the auxiliary holds $n$ postings and the total is $T$ , each posting gets touched about $T / n$ times across merges. Total merge work is about $Θ (T^{2} / n)$ . Small $n$ means many merges of a huge main index. That cost curve is why a flat two-index design alone does not scale for heavy update flows.

A classroom-scale fix for merging postings is logarithmic merge, described next. It bounds merge work by growing index sizes geometrically rather than merging a tiny auxiliary store into a huge main store on every update.

Scope: The bit-vector trick fits logical deletes with deferred cleanup. It assumes the vector fits in memory and that filtered search stays fast. If deletes pile up, live lists fill with dead entries and query time sags until a real merge or rebuild runs.

6.6.3 Logarithmic Merge With Doubling Sizes

The heart of the fix is to keep a series of indexes where each level is twice the size of the prior level. Think binary powers $2^{0}, 2^{1}, 2^{2}$ , and so on. Each time memory at one level fills, move and merge upward. That is exponential growth in level capacity, which keeps total merge cost low. Build time drops to about $Θ (T lo g (T / n))$ because each posting moves once per level, while queries now fan out to about $lo g (T / n)$ indexes.

In a kindergarten room where kids often drop paper, do not clean after every sheet. Keep small trays near groups. When a tray fills, empty it into the room bin. When the room bin fills, empty it into the floor bin. When that fills, move to the school bin. Small stores absorb fast arrivals. Larger stores absorb merged smaller stores only when needed. That tray chain is logarithmic merge in daily form.

Now the index version. Call the intake $Z_{0}$ and the levels $I_{0}, I_{1}, I_{2}, I_{3}$ . The intake $Z_{0}$ is the auxiliary memory. The moment $Z_{0}$ fills, move it to $I_{0}$ . Keep doubling each auxiliary level. In plain words, each time we use memory twice as large as the previous one.

Worked sizing with tiny token counts to show the pattern. Let $n$ set intake capacity. Here $Z_{0}$ can handle only two tokens. Top tokens in the toy problem are 30. Level capacities are 2, 4, 8, and 16. In symbols:

$2 + 4 + 8 + 16 = 30$

In words, this is two, four, eight, 16, sum of this is 30, so to solve this problem four different memories are needed. Powers are named as two power zero, two power one, two power two and two power three. The naming means $2^{0} \times n$ , $2^{1} \times n$ , $2^{2} \times n$ , $2^{3} \times n$ with $n = 2$ , which gives $1 \times 2 = 2$ , $2 \times 2 = 4$ , $4 \times 2 = 8$ , $8 \times 2 = 16$ . That resolves the wording slip where 2 power zero sounds like 1 against stated size 2. Times $n$ it is 2.

Step walk with those numbers:

First two tokens stay in $Z_{0}$ . $Z_{0}$ is full, so move those two to $I_{0}$ . Size of $I_{0}$ is two.
Next two tokens enter $Z_{0}$ . Now total is four, with two in $Z_{0}$ and two in $I_{0}$ . $Z_{0}$ is full again but $I_{0}$ is also full, so merge $Z_{0}$ plus $I_{0}$ and push four tokens to $I_{1}$ , whose size is four. This frees both $Z_{0}$ and $I_{0}$ .
Next two tokens enter $Z_{0}$ . Total is six, with four in $I_{1}$ and two in $Z_{0}$ . Move $Z_{0}$ to free $I_{0}$ , since $I_{0}$ is free. State is $I_{1} = 4$ , $I_{0} = 2$ .
At eight tokens, $Z_{0}$ plus $I_{0}$ plus $I_{1}$ fill in a way that needs $I_{2}$ . Merge two plus two plus four and move eight tokens to $I_{2}$ , whose size is eight.
The process goes on until the top of 30 tokens, with at most one index per level live at any time, like binary counting.

In compact form, where $C (Z_{0})$ is intake size and $C (I_{k})$ is size of level $k$ :

$C (I_{k}) = 2 \times C (I_{k - 1})$

with $C (Z_{0}) = 2$ , $C (I_{0}) = 2$ , $C (I_{1}) = 4$ , $C (I_{2}) = 8$ in this toy setting. The base pair of 2 for both $Z_{0}$ and $I_{0}$ follows the spoken numbers and matches $C (I_{0}) = 2^{0} \times n = n$ . Doubling chain holds: 2, 4, 8, 16 sum to 30.

Sense-check: 30 in binary is 11110, which uses 16 + 8 + 4 + 2. That matches four live levels at the end, so the tray count is right.

Large engines use this pattern because the web changes all the time, from news logs to article archives to sports and weather feeds. Even with dynamic indexing, engines may periodically rebuild the full index from scratch and then switch queries to the fresh index. Until that switch, queries read intake plus all live levels.

Do not merge the small intake straight into a huge main level on every fill. That flat merge repeats huge work. Also do not forget to query all live levels. A fresh document may live only in $Z_{0}$ and would be missed by a main-only search.

Fresh news and live scores stay visible through small levels while deep levels merge in the background.

6.6.4 Student Questions and Answers

Q: What is the role of auxiliary and main memory, and how does movement across memories work in the tray analogy?

A: The small tray near the group is the intake. Kids put each fallen sheet in the nearest tray. When small trays fill, their contents move into a larger tray, and the small trays become free for new sheets. Likewise $Z_{0}$ takes arrivals until full, then moves to $I_{0}$ . If $I_{0}$ is also full, merge $Z_{0}$ plus $I_{0}$ into $I_{1}$ . If later $I_{0}$ and $I_{1}$ plus $Z_{0}$ are full together, merge all into $I_{2}$ . Movement is always from smaller full levels into the next larger free level, doubling each time. Queries read across intake plus all live levels until a full rebuild replaces them.

Recap: dynamic search keeps a hot auxiliary plus a large main, deletes by bit filter, and bounds merge cost by doubling levels. This live-update story leads to compression next, which shrinks whatever levels and postings we must keep and move.

6.7 Index Compression Foundations

6.7.1 Why Compression Speeds Up Retrieval

Why shrink an index that already works?

An inverted index has two parts. The dictionary holds terms. Postings hold document identifiers and related payloads. We want the dictionary small enough to keep in main memory so every query first looks up the term there. If compression works well, some frequent posting lists can also stay in main memory. At that point the goal is retrieval speed, not just saving disk.

Think of packing for a trip. A vacuum bag shrinks bulky clothes so more fits in the cabin bag. You pay a minute to pack and unpack, but you skip the slow checked-baggage line. Compression is the vacuum bag. Decompression is the minute to unpack. Skipping big disk reads is skipping the slow line.

Size sketch from the lecture: uncompressed posting files need about 100 megabytes. After compression they need about 30 megabytes.

Step 1 — read cost without compression: move 100 megabytes from disk at the disk rate.

Step 2 — read cost with compression: move 30 megabytes, then run fast in-memory decode. Even with decode time added, 30 megabytes plus decode is much cheaper than 100 megabytes of raw reads. Reduced disk read dominates.

Final answer: compressed path wins on speed despite decode cost. This is why compression is a speed tool first and a space tool second. Smaller postings mean fewer disk seeks and transfers per query, which lifts query throughput on ordinary disks.

Two quiet wins add to the story. One is caching. With compression, more postings and more dictionary entries fit in RAM, so frequent terms like the can be answered from memory with no seek. The other is bus use. The processor stays free during disk moves, and modern decode runs so fast that move-plus-decode still beats a large raw move.

Exam note: Be ready to explain why compression helps speed even though decompression costs time, using the 100 megabytes to 30 megabytes case. Line to keep: small read plus fast decode beats large raw read.

6.7.2 Collection Statistics and What Drives Index Size

How large is a real index before we shrink it?

RCV1 numbers fix ideas. The collection holds about 800,000 documents. Each document holds about 200 tokens on average. Total token occurrences are:

$N_{t o k e n s} \approx N_{d ocs} \times average tokens per doc = 800, 000 \times 200 = 160, 000, 000$

Here $N_{d ocs}$ is document count, $N_{t o k e n s}$ is total token occurrences, and average is tokens per document. The spoken line that sounds like 800 times 2000 is a slip for 800,000 times 200. The intent and product are 160 million tokens in lecture-rounded math. Reference tables round the same collection to about 100 million tokens after case folding with unrounded counts near $96, 969, 056$ , so expect both 160 million lecture math and 100 million table math in the wild.

Vocabulary size, meaning distinct terms, is around 400,000. Non-positional postings are about 100 million. A non-positional posting (term mapped to document identifier list without word positions) is the baseline. A positional posting (term mapped to document identifier plus frequency plus word positions) is larger still, near 179 million position entries after case folding in the table. The lecture asks the listener to picture how much larger the positional case must be. Answer: much larger, because each occurrence adds position payload.

RCV1 scale check: $N = 800, 000$ documents, $200$ tokens each, $400, 000$ distinct terms, about $100, 000, 000$ non-positional postings.

Step 1 — tokens: $800, 000 \times 200 =$ $160, 000, 000$ by lecture rounding.

Step 2 — pairs at 8 bytes per pair: $100, 000, 000 \times 8 =$ $800$ megabytes raw, before sort space.

Step 3 — lesson: index size is not set by document count alone. It rests on how many unique terms exist and on how many documents each term appears in. Two collections with the same document count can have very different index sizes if one has richer vocabulary or denser term overlap. Scale story holds.

A table of sizes after preprocessing steps is shown for the same corpus. Dictionary unfiltered count is 484,494 distinct terms, often shortened in speech to 484 thousand. With numbers removed it is 473,723, shortened to 474 thousand. After stemming it is 322,383, shortened to 322 thousand. Units are counts of distinct terms for the dictionary side, with matching drops in non-positional postings from about 110 million to about 64 million and in positional entries from about 198 million to about 95 million across the full pipeline. Non-positional index size drops further down the steps. Positional index size stays high, as expected, because positions add payload. The table is used to show how each processing choice changes stored size.

Scope: Rounded counts shift with preprocessing. Case folding, numbers handling, stop removal, and stemming each reset the baseline. Always state which row you quote. Mixing an unfiltered term count with a stemmed posting count gives a false ratio.

6.7.3 Preprocessing Effects Lossless Against Lossy

When does shrinking the dictionary hurt meaning?

Case folding shows a large drop. Case folding (mapping upper case to lower case) turns Apple, APPLE, and apple into one form. That merge cuts dictionary size a lot, by about 17 percent in the table, so it can look tempting to apply everywhere. Care is needed. United States mapped to lower case and the pronoun us mapped to lower case both become us, which merges totally different meanings. A noun treated as a pronoun after folding is the same hazard. That United States against us clash is the stock warning to keep.

Stop-word removal trims postings but less than newcomers expect. The top 30 words take about 30 percent of tokens, and 150 stop words cut non-positional postings by about 25 to 30 percent, yet the compressed index shrinks far less because frequent postings already compress to a few bits each. Stemming (stripping affixes to a stem) always cuts size, for one table cut of about 17 percent of terms, with computing, computer, and computes all becoming compute. The nuance lost is sense detail. Lemmatization (mapping to the base dictionary form) is the gentler alternative named for that reason. Whether to stem, lemmatize, fold case, or drop stop words is a decision per use, not a default.

There are two ways to compress. Lossless compression (exact recovery after decompression) is what most retrieval uses for postings and dictionary codes. Lossy compression (some detail is discarded) is avoided for core postings. Case folding of distinct meanings into one token is lossy in effect, as are stemming and stop removal. So compression choice must not be aggressive for its own sake. Preprocessing steps that look like wins on size can harm meaning. Use lossless codes for storage, and weigh each lossy text rule by task quality.

A forward pointer helps. Vocabulary size has no safe fixed cap that stops growth with the corpus. We cannot assume an upper limit from current knowledge. Dictionary compression matters, but size keeps growing with new text. The next step estimates growth with Heaps law, using two constants $K$ and $b$ tied to observed tokens to predict vocabulary growth. In symbols, where $V$ is vocabulary size and $n$ is tokens seen:

$V = K \times n^{b}$

Typical fits use $30 \leq K \leq 100$ and $b \approx 0.5$ . For RCV1 the fit is about $K = 44$ and $b = 0.49$ , which predicts near $38, 300$ terms at one million tokens against $38, 365$ true. On RCV1 the predicted terms come close to actual terms, and full detail with Zipf modeling follows next time. The lecture preview names $K$ and $B$ in speech for $K$ and $b$ in symbols.

Folding and stemming choices change both index size and result quality in production search. French-rich text is one place where a lemmatizer cuts far more than an English stemmer, so domain sets the rule.

Do not fold case blindly on mixed-case collections with names, places, or pronouns. Do not stem when endings carry task meaning. Keep a lossy rule only when its lost detail is rarely used by your queries.

6.7.4 Student Questions and Answers

Q: Between non-positional and positional indexing the number went up. Is non-positional just term against posting list, and positional term against posting list plus positions?

A: Yes. Non-positional form is term against posting list of document identifiers. Positional form is term against posting list with frequency plus document plus position. The numbers compared are sizes, so the positional size is larger. That is why the increase makes sense. Expect positional payload to dominate once positions are stored.

Recap: compression buys speed by shrinking reads and growing cache fit. RCV1 at 800,000 documents and 200 tokens each frames all size math. Lossless codes keep postings exact, lossy text rules need task care, and Heaps law previews vocabulary growth. This closes scalable build and opens scoring models next.

Exam Guidance Summary

Syllabus path: Boolean retrieval, preprocessing, dictionary and tolerant retrieval are done. Index construction and index compression span this session and the next. Vector-based models close the midterm portion. Evaluation joins the midterm set only if covered before the cutoff, including any delayed session that falls inside the window.

Exam note: Hardware trade of RAM against disk and why large blocks beat scattered writes. BSBI steps and where its two plus one sorts occur. SPIMI premise of sorted document order and term-only final sort. MapReduce equalities of splits to parsers and partitions to inverters with A to F, G to P, Q to Z ranges. Term partitioning load imbalance with apple pi and information retrieval cases and why document partitioning is preferred. Dynamic two-index rule with search across main plus auxiliary plus invalidation bit vector. Logarithmic merge doubling with 2, 4, 8, 16 summing to 30. Compression win from 100 megabytes to 30 megabytes despite decode cost. RCV1 scale of 800,000 documents with about 200 tokens each giving about 160 million tokens and about 400,000 distinct terms with about 100 million non-positional postings. Case folding hazard of United States against us. Stemming merge of computing and computer into compute. Lossless preference. Heaps law preview with constants $K$ and $b$ .

Study advice given: start early with group members on the assignment, treat it as practice for exams, dissertation work, and workplace tasks, and record contribution shares with care. Participation share can be set lower when a member does not take part, which helps the group more than silent cover.

Key Industry Applications

RCV1 benchmark with topic, region, and sports labels supports retrieval and language tests on shared ground.

Web search on commodity clusters uses term ranges A to F, G to P, Q to Z across inverters for the build phase, then serves most queries from document partitions to balance multi-term queries such as information retrieval.

Dynamic auxiliary indexes keep fast-changing feeds fresh, from tournament scores, petrol prices, conflict updates, news homepages, weather reports, and article streams. Fresh writes land in small levels while deep levels merge in the background.

Dictionary kept in main memory plus hot posting lists cached after compression lifts lookup speed and query throughput.

Case folding, stop-word handling, stemming, and lemmatization choices are tuned per domain, with French apostrophe forms mapped or kept based on corpus needs. Folding United States to us shows why blind rules fail.

Data-center scale circa 2014 with large server installs and shared cluster designs marks the textbook scale point for web indexing.

IR Lecture 6 notes · Scalable Index Construction and Compression Foundations

Information Retrieval· undergraduate· 2026-09-14

Sections Breakdown

1Memory Hierarchy and Cost of Disk Access

Memory pyramid forces disk use; seek plus transfer math shows large sequential blocks win

2Reuters Collection and Inverted Index Recap

RCV1 scale forces disk methods; double sort groups by term and orders postings

3Blocked Sort-Based Indexing

BSBI slices collection into blocks, sorts each in RAM, spills runs, merges once

4Single-Pass In-Memory Indexing

SPIMI drops global map, builds postings on arrival, sorts terms once at merge

5Distributed Indexing With MapReduce

MapReduce splits docs to parsers and term ranges to inverters; document partitioning serves better

6Dynamic Indexing and Logarithmic Merge

Two-index live updates with bit-vector deletes and doubling merge levels

7Index Compression Foundations

Compression speeds reads and cache fit; RCV1 stats frame size; lossy rules need care; Heaps previews growth

Undergraduate students studying Information Retrieval

Exam Revision Notes

Below is the distilled, exam-ready core. Every entry comes from the full explanation above. Use this section for rapid review; return to the main notes when a point needs more context.

Memory Hierarchy and Cost of Disk Access

Must-know: Memory fast-small, disk slow-large; 10 MB continuous ~0.205s, scattered in 100 parts 0.7s

$T_{t o t a l} = n \times S + size \times B$

Top pitfall: Indexing one posting at a time from disk pays a full seek per item

Self-check: Why does 10 MB in 100 chunks cost 0.7s while one chunk costs ~0.2s?

Connects to: 6.3, 6.7

Reuters Collection and Inverted Index Recap

Must-know: RCV1 ~800k docs; index sorted by alphabetical terms and ascending documents

$t_{1} < t_{2} < \dots < t_{n} and d_{1} < d_{2} < \dots < d_{m}$

Top pitfall: Counting terms before fixing apostrophe and case rules

Self-check: What are the two sort orders in an inverted index?

Connects to: 6.1, 6.3

Blocked Sort-Based Indexing

Must-know: BSBI: block, parse, map, sort in block, write, repeat, merge with final sort

$S_{p os t in g} = 4 + 4 + 4 = 12, S_{t o t a l} = 100, 000, 000 \times 12 \approx 1.2 GB$

Top pitfall: Skipping final merge; blocks sorted only inside themselves

Self-check: Where does sorting happen in BSBI?

Connects to: 6.1, 6.4

Single-Pass In-Memory Indexing

Must-know: SPIMI files on arrival with per-block dicts, doubles lists, sorts only terms at merge

$d_{1} < d_{2} < d_{3} < \dots$

Top pitfall: Feeding shuffled documents and trusting posting order

Self-check: Why does SPIMI need documents in sorted order?

Connects to: 6.3, 6.5

Distributed Indexing With MapReduce

Must-know: Splits match parsers, partitions match inverters; document split beats term split for serving

$N_{s pl i t s} = N_{p a r ser s}, J = N_{in v er t er s}$

Top pitfall: Assuming one-term ease means two-term ease under term split

Self-check: Why does information retrieval hit two disks under term partitioning?

Connects to: 6.3, 6.6

Dynamic Indexing and Logarithmic Merge

Must-know: New docs to auxiliary, search both, delete by bit filter, merge by doubling levels

$C (I_{k}) = 2 \times C (I_{k - 1}), 2 + 4 + 8 + 16 = 30$

Top pitfall: Merging small intake into huge main on every fill; searching main only

Self-check: Why do level sizes double in logarithmic merge?

Connects to: 6.5, 6.7

Index Compression Foundations

Must-know: Compression buys speed: 100 MB to 30 MB; RCV1 800k docs, 400k terms; Heaps V=K n^b

$N_{t o k e n s} \approx 800, 000 \times 200 = 160, 000, 000, V = K \times n^{b}$

Top pitfall: Folding United States and us into one token; stemming away task meaning

Self-check: Why does 30 MB plus decode beat 100 MB raw?

Connects to: 6.2, 6.6

Previous LectureLecture 05 · Tolerant Retrieval: Wildcard Queries and Spelling Correction

Next LectureLecture 07 · Index Compression and Ranked Retrieval

Was this lecture useful?

Loading comments…

🤖

BitsNotes AI Assistant

Subject Notes Assistant

Configure AI Chat

Choose how to access the chatbot

Have your own API key?

Switch to "Bring Your Own Key" tab above for unlimited access with any OpenAI-compatible provider.

AI Provider Preset

API Endpoint URL (OpenAI-Compatible)

API Key

Model Name

🔑 Enter API key above to fetch live models from provider, or enter model name manually.

Remember key for this session (until tab closes)

OpenAI-Compatible API Support

Choose any provider preset (Gemini, DeepSeek, Kimi, GLM, MiniMax, Qwen, OpenAI, Groq, Ollama, etc.) or enter a custom endpoint URL.

Security & Privacy First

Your API key is sent directly from your browser to your specified provider. BitsNotes servers never store or see your key.