You are viewing a plain text version of this content. The canonical link for it is here.

Posted to dev@flink.apache.org by "Gabor Gevay (JIRA)" <ji...@apache.org> on 2015/06/03 11:56:50 UTC

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

Gabor Gevay created FLINK-2146:
----------------------------------

             Summary: 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
            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)