TAOCP 6.5 Retrieval on Secondary Keys: reading guide

Searching on attributes other than the primary key: inverted files, multi-attribute queries, range and partial-match queries, and superimposed coding (the idea behind Bloom filters).

Time About 7 hours this week

Why it matters

Inverted indexes power every search engine, and Bloom filters are everywhere from databases to network caches.

Before you start

6.4 Hashing

How to approach it

Build a tiny inverted index for a folder of text files and answer AND queries. Implement a Bloom filter and measure its false positive rate.

Exercises

Work every exercise rated 10 to 20; most are about tracing the algorithm by hand or tweaking one step, which is exactly the skill you want. Pick one or two rated 20 to 25 that involve modifying the algorithm and implement your modification in a real language with tests. Skip HM exercises unless you enjoy calculus, and treat anything rated 40+ as a research problem, not homework.

Traps

Picking the number of Bloom filter hash functions without doing the math.