Zwei-Stapel-Trick: Sliding-Window-Aggregation ohne Inverses
Two-Stack Sliding-Window Aggregation
Sliding-Window-Aggregationen wie Minimum oder HyperLogLog lassen sich nicht mit einer einfachen Summe berechnen, da die Operation kein Inverses hat. Der Blogbeitrag stellt einen Zwei-Stapel-Algorithmus vor, der für jede assoziative Aggregation in amortisiert O(1) funktioniert. Der Trick: Ein Stapel speichert die Werte, der andere die kumulativen Aggregate. Besonders nützlich bei Fließkommazahlen, da NaN oder Infinity nur das aktuelle Fenster verfälschen.
Selbst etwas so Einfaches wie eine Fließkomma-Summe leidet darunter, dass die Fließkomma-Addition nicht invertierbar ist.