Core algorithms

Two techniques keep queries cheap: a time-invariant key for pure decay, and bounded segment scans for lag kernels.

Forward-decay ordering

For priority uses with exponential decay, scores move every second, but their order does not. In log space:

$$\log \mathrm{score}(e, t) = \underbrace{\log w_e + \lambda t_e}_{\text{stored key}} - \lambda t$$

The last term is shared by every event, so the stored key fixes the ordering forever. Insert is O(log n), peek is O(1), and nothing is ever reheapified. The current score is recovered as exp(key − λ·now) only for the items returned. Keys grow linearly with time, so a background task rebases the reference epoch long before floating-point precision runs out.

Lag kernels and segment pruning

Attribution kernels are not monotonic (a meal eaten five minutes ago is less likely to cause bloating than one eaten two hours ago), so the forward-decay trick does not apply. Instead:

1. Events are stored per entity in time-bucketed segments (default 15 min). Each segment keeps its time range, an inverted index of features, and its distinct (event type, feature set) pairs with the largest weight seen for each.
2. A query selects segments inside the kernel's support window.
3. Each segment gets an upper bound: kernel max over its time range × the largest value, over its distinct feature sets, of (max weight of that set × noisy-OR of its current link strengths × the most permissive rule multiplier for its event type). It is computed at query time, so it stays valid as links learn. Segments with more than 64 distinct sets fall back to the noisy-OR over the union of their features.
4. Segments are scanned in descending bound order into a size-k min-heap.
5. The scan stops as soon as the k-th best score is at least the next segment's bound.

Why per-set rather than the union: a noisy-OR over every feature in the segment lets one strong event lift the bound for fifty weak ones. Replacing the noisy-OR with the single strongest link is tempting but wrong: an event's noisy-OR is at least its strongest link and often more, so that would no longer be an upper bound and the scan could skip a true top answer. The per-set maximum is exact for the segment's actual events. On a test stream of heavy weak events with one light strong event per segment, it prunes 149 of 151 segments where the union bound pruned 15, with identical answers.

This is the threshold-algorithm and block-max WAND idea applied to time. With a peaked kernel, the scan concentrates on segments near the peak and skips the tails.

Ranking is only half the loop. Learning and EXPLAIN covers how answers improve with feedback.