逆元のない集約もスライディングウィンドウでO(1)に
Two-Stack Sliding-Window Aggregation
スライディングウィンドウ集約は、合計のように逆演算がある場合には簡単だが、最小値やHyperLogLogなど逆元がない演算では難しい。本記事では、2つのスタックを用いて任意の結合的な集約を償却O(1)で処理するシンプルなアルゴリズムを紹介。浮動小数点の非結合性やNaNの影響を局所化できる利点も解説する。
その代わり、ウィンドウ外の値に結果が依存しないようにすることで、長期的な誤差の蓄積を完全に排除できる。