Piecewise interpolation indexes: predict a bounded rank window

Last updated: 4 Oct 20269 min read

tutorial

A piecewise interpolation index divides one sorted unique integer catalog into fixed-size blocks. Each block stores its first and last key, starting rank, count, and the largest training-key error of a line between endpoints. A query first finds the block whose last key is at least the target. It predicts a rank with integer arithmetic, then binary-searches only a window expanded by the certified error plus a small boundary allowance. That allowance also covers values between stored keys, where a lower bound jumps even though the line is continuous. The algorithm still compares actual keys, so the model is a hint with a checked correction step, not an authority on membership or order.

Operational case

Case IDs 19, 29, 47, 61, 83, 103, 127, 149, and 173 form one immutable catalog. The lower-bound rank for 60 is three, for 103 it is five, and a target beyond the maximum returns nine. Nonuniform gaps make interpolation imperfect, but the local error window contains the exact lower bound. A missing target can have a valid insertion rank without being a member. A writer that inserts a new key between 47 and 61 changes later ranks and potentially every model boundary; the index must be rebuilt. The fixed block width is a design choice, not a claim of an optimal learned segmentation.

Working Python program

from bisect import bisect_left


class PiecewiseCaseRank:
    def __init__(self, sorted_case_ids, block_width=4):
        if block_width < 2 or any(left >= right for left, right in zip(sorted_case_ids, sorted_case_ids[1:])):
            raise ValueError("need strictly increasing IDs and block width at least two")
        self.keys = list(sorted_case_ids)
        self.blocks = []
        for start in range(0, len(self.keys), block_width):
            values = self.keys[start:start + block_width]
            first, last = values[0], values[-1]

            def predict(target):
                return 0 if first == last else (target - first) * (len(values) - 1) // (last - first)

            max_error = max(abs(predict(key) - offset) for offset, key in enumerate(values))
            self.blocks.append((first, last, start, len(values), max_error))
        self.ends = [block[1] for block in self.blocks]

    def lower_bound(self, target):
        if not self.blocks:
            return 0
        block_id = bisect_left(self.ends, target)
        if block_id == len(self.blocks):
            return len(self.keys)
        first, last, start, count, error = self.blocks[block_id]
        local_prediction = (0 if first == last or target <= first else
                            (target - first) * (count - 1) // (last - first))
        prediction = start + local_prediction
        low = max(start, prediction - error - 2)
        high = min(start + count, prediction + error + 3)
        return low + bisect_left(self.keys, target, low, high) - low


if __name__ == "__main__":
    catalog = PiecewiseCaseRank([19, 29, 47, 61, 83, 103, 127, 149, 173], block_width=4)
    print("rank for 60:", catalog.lower_bound(60))
    print("rank for 103:", catalog.lower_bound(103))
    print("rank for 200:", catalog.lower_bound(200))

Output

rank for 60: 3
rank for 103: 5
rank for 200: 9

Time, space, and tradeoff

Given already sorted keys, this direct constructor scans N keys once and stores O(N divided by block width) model records plus the original O(N) key array. A query binary-searches the block ends and then a local window, costing O(log B+log(E+1)) comparisons for B blocks and that block's certified error E, with the fixed allowance folded in. In the worst case E can approach the block width, so the method may offer no advantage over ordinary binary search. The exact integer predictor avoids floating-point rounding, but it assumes numeric keys and static ranks. Any claimed speedup needs measurement against bisect on the actual workload.

Common Mistakes

Do not trust a predicted rank without checking the stored keys.
Do not ignore between-key lower-bound jumps when sizing the correction window.
Do not keep a model after inserting or removing catalog keys.
Do not claim fixed-width blocks are a minimal piecewise model.

Connected lessons

Compare its update and query contract with FM-index backward search: narrow a suffix interval by character, Block-max postings: skip safe document-score regions, Euler-tour RMQ: answer static common ancestors in constant query time, then complete the structure audit and decision quiz.

data structures

array-data-structure-guide