역원 없는 집계를 위한 우아한 알고리즘: Two-Stack Sliding-Window Aggregation
슬라이딩 윈도우 집계는 최소·최대·HyperLogLog 같은 역원이 없는 연산에서 어렵다. 저자는 두 개의 스택과 누적 집계를 이용해 상각 O(1) 시간에 임의의 결합적 집계를 처리하는 간단한 알고리즘을 소개한다. 이 알고리즘은 윈도우 밖의 값에 결과가 의존하지 않아 부동소수점 오차 누적이나 NaN 전파 문제를 근본적으로 해결한다. 2011년 Stack Overflow에서 기원한 이 기법은 널리 알려질 가치가 있다고 강조한다.
각 집계는 엄밀히 윈도우 내부 요소들의 조합일 뿐, 윈도우 밖 요소는 전혀 포함하지 않는다. 따라서 윈도우에 NaN이나 무한대(또는 다른 이상치)가 포함되면 그 값은 이를 포함하는 윈도우만 오염시킬 뿐 나머지 계산에는 영향을 주지 않는다.