Skip to content
Tutorials Center
My learning

Topics

Lesson 42 of 47 ยท Projects, Practice and Review

Project: Search Index over Documents

Build an inverted index and TF-IDF ranking with chained MapReduce jobs, then split the index build into partitions the way a cluster would.

Search engines answer "which documents contain these words?" in milliseconds, even over billions of pages. The trick is an inverted index: instead of storing each document's words, you store, for each word, the list of documents that contain it. Building that index from raw text was one of the original reasons MapReduce was invented, because the work splits perfectly by document.

In this project you build the index, add TF-IDF scores so results are ranked by relevance, answer queries, and finally partition the index so each "reducer" owns a slice of the vocabulary.

A real build would run as Hadoop jobs reading documents from HDFS and writing index files. Here a Python simulator stands in for the framework, and a handful of short documents stand in for the web. The map and reduce functions are the real logic. Tools such as Lucene, Solr and Elasticsearch use a far more compact on-disk format, but the idea is the same.

The idea

Forward versus inverted

Forward Document 7 contains cat, sat, mat.
Inverted The word cat appears in documents 3, 7, 9.

Queries start from words, so index by word.

1 / 2

The mapper reads one document and emits (word, (doc_id, 1)). The shuffle brings every posting for one word to one reducer, which assembles the posting list. This is the "inverted index" pattern from MapReduce Design Patterns.

Step 1: Tokenize and build postings

Before indexing, text must be normalized: lowercase it, split on non-letters, and drop stop words such as "the" and "of" that appear everywhere and carry little meaning. Real systems also stem words (running becomes run); we skip that for clarity.

Python Inverted index with postings

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Each posting list contains (doc_id, term frequency) pairs. Because the framework sorts keys, the vocabulary comes out alphabetical, and sorting each list by document id makes later merging and intersections cheap.

Step 2: Why raw counts are not enough: TF-IDF

Searching for quick dog should not rank a document highly just because it repeats a very common word. TF-IDF weighs a word's frequency in a document (TF) against how rare the word is across the whole collection (IDF):

  • TF (term frequency): how often the word appears in this document, often divided by the document length.
  • IDF (inverse document frequency): log(N / df), where N is the number of documents and df is the number of documents containing the word. A word in every document gets IDF 0; a rare word gets a large IDF.
  • Score for a word in a document: TF x IDF.

Computing it needs chained jobs, because IDF requires a global number (df) that is only known after the first pass: job 1 produces term frequencies per document, job 2 computes df from the posting lists, and job 3 (or a map-side join using df as a small lookup, see MapReduce Design Patterns) combines them. Each job's output is the next job's input in HDFS.

Python TF-IDF ranking and a search query

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Read the output: dog appears in three of four documents, so its IDF is low, while quick appears in two and scores higher where it occurs. For the query quick dog, document 2 wins because it has quick twice and dog once. A word that appears in a single document, such as hadoop, gets the highest IDF.

Step 3: A partitioned index build

On a cluster the index is far too big for one reducer. The partitioner splits the vocabulary into ranges or hash buckets, and each reducer writes one index shard. Two common choices:

  • Hash partitioning of terms: words are spread evenly, but a query touching many words visits many shards.
  • Document partitioning: each shard indexes a subset of documents and holds the complete posting lists for them. Queries go to every shard, which answers in parallel, and results are merged. This is how most large search engines scale, because shards stay independent when documents are added.

The stand-in below builds a term-partitioned index in two shards, as a MapReduce job with a partitioner would, and then routes a query word to the shard that owns it. Skew shows up here too: a few frequent words create very long posting lists, which is one reason stop-word removal helps.

Python Partition the index by term

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The AND query is an intersection of sorted posting lists. With sorted lists it is a linear merge, which is why index builders keep postings sorted by document id.

What a production build adds

  • Positions in each posting so phrase queries ("big data") can check that words are adjacent.
  • Compression of posting lists, storing gaps between document ids instead of the ids.
  • Incremental updates: new documents go to a small new segment that is merged into bigger ones later (the same idea as the LSM tree in HBase: Wide-Column Storage).
  • Deletes and updates handled by marking documents deleted and dropping them when segments merge.
  • Scoring improvements such as BM25, which refines TF-IDF with document length normalization and saturating term frequency.

Extensions to try

  1. Add stemming (strip a trailing s) and watch how postings merge.
  2. Store term positions and implement a phrase query.
  3. Normalize TF-IDF vectors and rank by cosine similarity.
  4. Switch to document partitioning and compare the shard sizes.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does an inverted index map?

    Searches start from words, so the index stores for every word a posting list of documents.
  2. 2. A word occurs in every document of the collection. What is its IDF, log(N / df)?

    N / df equals 1 and log(1) is 0, so a word that appears everywhere carries no weight for ranking.
  3. 3. Why does TF-IDF need chained jobs?

    Document frequency requires seeing all documents, so one job computes term counts and df, and a later job combines them into scores.
  4. 4. In a document-partitioned index, how is a query answered?

    Each shard holds complete posting lists for a subset of documents, so all shards work in parallel and a merge step picks the best results.

Summary

  • An inverted index maps each word to a sorted posting list of document ids and term frequencies.
  • Map emits (word, posting); the shuffle brings all postings of a word together; reduce builds the list.
  • TF-IDF rewards words that are frequent in a document but rare in the collection; computing it takes chained jobs.
  • Large indexes are partitioned, by term or (more commonly) by document, with a merge step for queries.
  • Production indexes add positions, compression, segment merging and better scoring like BM25.

Next: Project: Co-purchase Recommendations.