advanced practice · coding problem
Skip documents that cannot reach the top k
Implement prune(docs, upperBounds, k) where docs is [{id, terms:[termName], score}] and upperBounds maps term -> max possible contribution. Walk docs in order maintaining a top-k heap; BEFORE scoring a document, skip it when the sum of its terms' upper bounds is <= the current k-th best score. Return { top: ids of the top k by score descending, scored: how many documents you actually scored }.
The mechanism
Scoring every posting is wasted work when you only need the top k: once the heap holds k results, any document whose best possible score cannot exceed the current threshold can be skipped without computing it. WAND does this by keeping a per-term upper bound and advancing pointers past documents whose summed bounds fall short; block-max sharpens it by storing a maximum per block rather than per term, so the bound is tight enough to skip far more. This is safe pruning — the top k is identical to the exhaustive answer, only faster.
Expected evidence
Pruning must not change the top k — only how many documents were scored.
Try this drill in the practice workspace →
Hints when you need them
- The threshold is the k-th best score so far, and it is 0 (skip nothing) until the heap holds k documents.
- Use <= so a document that can only tie is skipped; ties do not displace an existing result.
Watch for these mistakes
- Confusing safe pruning with approximate retrieval; WAND returns exactly the same top k
- Using a global per-term upper bound when block-level maxima would prune an order of magnitude more
- Assuming pruning helps for a query needing deep result sets — the win shrinks as k grows
- Forgetting the threshold only rises once the heap is full, so early postings are still scored