[jira] [Resolved] (FLINK-2146) Fast calculation of min/max with arbitrary eviction and triggers

["Gabor Gevay (JIRA)" <ji...@apache.org>]

     [ https://issues.apache.org/jira/browse/FLINK-2146?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Gabor Gevay resolved FLINK-2146.
--------------------------------
    Resolution: Not A Problem

I'm closing this, since with the redesigned windowing API (since 0.10) this became much less important. The previous windowing worked by always keeping track of one window only, by adding newly arriving elements and evicting old elements, and it fitted all kinds of windowing strategies into this model. This issue concerned the updating of min/max when the window is updated this way. However, the new windowing API (mostly to handle out of order events) keeps track of several windows at the same time, so solving this issue wouldn't effect sliding windows for example.

> Fast calculation of min/max with arbitrary eviction and triggers
> ----------------------------------------------------------------
>
>                 Key: FLINK-2146
>                 URL: https://issues.apache.org/jira/browse/FLINK-2146
>             Project: Flink
>          Issue Type: Sub-task
>          Components: Streaming
>            Reporter: Gabor Gevay
>            Priority: Minor
>
> The last algorithm described here could be used:
> http://codercareer.blogspot.com/2012/02/no-33-maximums-in-sliding-windows.html
> It is based on a double-ended queue which maintains a sorted list of elements of the current window that have the possibility of being the maximal element in the future.
> Store: O(1) amortized
> Evict: O(1)
> emitWindow: O(1)
> memory: O(N)



--
This message was sent by Atlassian JIRA
(v6.3.4#6332)