[jira] [Created] (FLINK-2145) Median calculation for windows

[Shang Yuanchun (Jira)]

Gabor Gevay created FLINK-2145:
----------------------------------

             Summary: Median calculation for windows
                 Key: FLINK-2145
                 URL: https://issues.apache.org/jira/browse/FLINK-2145
             Project: Flink
          Issue Type: Sub-task
          Components: Streaming
            Reporter: Gabor Gevay
            Assignee: Gabor Gevay
            Priority: Minor


The PreReducer for this has the following algorithm: We maintain two multisets (as, for example, balanced binary search trees), that always partition the elements of the current window to smaller-than-median and larger-than-median elements. At each store and evict, we can maintain this invariant with only O(1) multiset operations.



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