Closed-Form Predicate-Level Shapley Attribution for Sliding-Window Aggregates
2026-08-24 • Databases
Databases
AI summaryⓘ
The authors focus on understanding why certain streaming data summaries, like averages or sums over sliding windows, have their current values. They use a concept called Shapley value to fairly attribute contributions from different data groups but find exact calculation typically too slow. Instead, they create a fast method that uses simple running summaries and mathematical formulas to quickly compute exact Shapley values without examining every subset of data. Their approach works well for common aggregates like sum, count, average, and variance but not for max or quantiles. Experiments show their method is both accurate and extremely fast, even on large real-world datasets.
Shapley valuestreaming datasliding windowaggregate functionscooperative game theorymoment polynomialsvarianceharmonic numberspredicate-level attributionreal-time analytics
Authors
Pouya Khani, Ira Assent
Abstract
Streaming engines report sliding-window aggregates in real time, but they do not explain \emph{why} an aggregate takes its current value. A natural target is the Shapley value from cooperative game theory, which axiomatically distributes an aggregate among the tuples in the window. Practitioners, however, ask predicate-level questions (e.g., how much a region or customer tier contributed to an average or variance spike). Exact Shapley computation is exponential in the window size, and existing estimators discard the massive overlap between consecutive windows. We show that for SUM, COUNT, AVG, and population/sample variance, exact predicate-level Shapley values admit closed forms in three additively maintained summaries per predicate (count, sum, and sum of squares), with coefficients that depend only on two running harmonic numbers. Attribution therefore reduces to $O(1)$ summary updates per slide for registered predicates, with no coalition enumeration. Overlapping and compositional predicates are answered exactly via atomic refinement of Boolean signatures. We further characterize the phenomenon: every moment-polynomial aggregate admits such a form, while MAX, MIN, and quantiles provably do not at any fixed moment order. Experiments match brute-force Shapley values to floating-point precision on over $10{,}000$ windows, sustain $\approx\!2\,μ$s per slide up to $N=10^6$ ($3{,}200\times$ faster than per-window recomputation of the same formulas), and explain a nighttime fare spike on 2.9M NYC taxi trips at $\approx\!1.8$M summary updates per second.