Block-max postings: skip safe document-score regions

Last updated: 5 Oct 20269 min read

tutorial

A block-max posting index keeps an upper bound for each query term within each document-ID block. This example's document score is the sum of nonnegative weights for distinct query terms. Summing the term maxima yields an upper bound on every document in that block, even though different maxima may belong to different documents. Once K candidates are known, a block can be skipped when its upper bound is strictly below the current Kth score. The strict comparison preserves deterministic ties: an equal-score document with a smaller ID might replace the current last candidate. The example scans blocks in ID order and keeps a small sorted leader list. It illustrates exact block pruning, not the full iterator-pivot procedure of a production top-k engine.

Operational case

Five incident documents have breach and urgent weights. Asking for the best two returns document 21 with score ten and document 19 with score eight; three later low-bound blocks are skipped. A score bound is safe only if every term contribution is nonnegative and the stored maximum is at least every real contribution in its block. If a term weight changed without refreshing its block maximum, the index might skip a new winner. A document with no matching query term contributes zero and is omitted. Duplicate query terms are treated as one term by the set conversion; a ranking product that weights repeated query words must state a different scoring rule.

Working Python program

class BlockMaxIncidentScores:
    def __init__(self, document_terms, block_width=16):
        if block_width < 1:
            raise ValueError("block width must be positive")
        self.block_width = block_width
        self.documents = {}
        self.block_documents = {}
        self.block_maximum = {}
        for document_id, weights in document_terms.items():
            if document_id < 0 or any(weight < 0 for weight in weights.values()):
                raise ValueError("IDs and term weights must be nonnegative")
            self.documents[document_id] = dict(weights)
            block = document_id // block_width
            self.block_documents.setdefault(block, []).append(document_id)
            for term, weight in weights.items():
                key = (term, block)
                self.block_maximum[key] = max(self.block_maximum.get(key, 0), weight)

    def top_k(self, query_terms, count):
        if count < 1:
            raise ValueError("count must be positive")
        terms = set(query_terms)
        leaders = []
        skipped = 0
        for block in sorted(self.block_documents):
            upper_bound = sum(self.block_maximum.get((term, block), 0) for term in terms)
            if len(leaders) == count and upper_bound < leaders[-1][0]:
                skipped += 1
                continue
            for document_id in self.block_documents[block]:
                score = sum(self.documents[document_id].get(term, 0) for term in terms)
                if score:
                    leaders.append((score, document_id))
                    leaders.sort(key=lambda item: (-item[0], item[1]))
                    del leaders[count:]
        return leaders, skipped


if __name__ == "__main__":
    index = BlockMaxIncidentScores({
        19: {"breach": 8}, 21: {"breach": 7, "urgent": 3},
        47: {"breach": 1}, 61: {"urgent": 2}, 83: {"breach": 1, "urgent": 1},
    }, block_width=20)
    print("top two:", index.top_k(["breach", "urgent"], 2))

Output

top two: ([(10, 21), (8, 19)], 3)

Time, space, and tradeoff

Building term maxima visits each stored term weight once and uses O(P+B) space for P weights and B block records. A query touches every block summary for each distinct term, then scores documents only in blocks that survive the bound. In the worst case it scores all documents, so this Python implementation has no guaranteed sublinear query bound. Its leader-list maintenance sorts at most K+1 items per scored document, adding O(K log K) work there. A production index would use posting iterators, compressed blocks, and a heap; these are intentionally outside this exact-score teaching model.

Common Mistakes

Do not skip a block on a bound equal to the Kth score when ID ties matter.
Do not use stale or underestimated term maxima.
Do not apply a nonnegative-sum bound to scoring with negative contributions.
Do not label this block scan a complete WAND iterator implementation.

Connected lessons

Compare its update and query contract with FM-index backward search: narrow a suffix interval by character, Piecewise interpolation indexes: predict a bounded rank window, Euler-tour RMQ: answer static common ancestors in constant query time, then complete the structure audit and decision quiz.

data structures

hash-tables