Project: audit compact alert and document indexes

Acceptance trace

For Elias–Fano, use IDs 13, 19, 47, 61, 83, and 129 below 256; rank three and lower bound 50 both return 61. Intersect an active chunked set with a reviewed set and obtain 47, 515, 516, and 517, with the active 512-series chunk promoted to a bitmap. Encode postings 47, 61, 83, 129, and 515; seek at least 80 and 200 to find 83 and 515. In the term trie, alert is an exact key, al is a prefix but not an exact key, and an absent term fails both lookups.

Expected review record

lower-bound-50=61
shared=[47, 515, 516, 517]
seek-200=515
al-prefix=True
al-key=False

Boundary and cost review

Generate sorted integer samples with large gaps, empty lists, a first ID of zero, and targets before or after the list. Toggle enough chunk entries across the promotion and demotion thresholds, then compare every membership and intersection with exact sets. Decode the full posting stream and test targets on either side of checkpoints; corrupt a final continuation byte to confirm a truncated code is rejected. Compare term and prefix lookup with direct string tests, including an empty term. State the work required to rebuild each static layout and identify every auxiliary list excluded from a printed byte or bit count.

Common Mistakes

• Do not present a conceptual encoding length as the process heap footprint.
• Do not lose an absolute document ID at a seek checkpoint.
• Do not count a trie prefix as a complete term without its terminal flag.
• Do not toggle sparse and dense chunk types at one shared cutoff.

Connected lessons

• Elias–Fano: split sorted IDs into low parts and high bits
• Chunked integer sets: switch sparse arrays to dense bitmaps
• Gap-encoded postings: add checkpoints to bytewise seeks
• Level-order unary degree tries: encode child runs as bits
• Projects
• Quizzes
• Data Structures