flink-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "ASF GitHub Bot (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (FLINK-2143) Add an overload to reduceWindow which takes the inverse of the reduceFunction as a second parameter
Date Mon, 22 Jun 2015 12:01:00 GMT

    [ https://issues.apache.org/jira/browse/FLINK-2143?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14595824#comment-14595824

ASF GitHub Bot commented on FLINK-2143:

GitHub user ggevay opened a pull request:


    [FLINK-2143] Added ReduceFunctionWithInverse

    (The first commit is the same as the second commit in PR 684)
    I didn't add an overload to reduce, but instead created ReduceFunctionWithInverse as a
descendant of ReduceFunction. It has an invReduce method, which should be the inverse of reduce.
getWindowBuffer checks if `transformation.getUDF() instanceof ReduceFunctionWithInverse` and
creates an InversePreReducer in this case (except when the policy is tumbling or jumping).
    I made SumAggregator implement ReduceFunctionWithInverse, so calculating sums of sliding
or even more general windows should get a speedup from this. WindowIntegrationTest tests this.
(FLINK-2144 will also have a few ReduceFunctionWithInverse implementors.)
    Grouped case: This is just creating an instance of the pre-reducer for each new group
that appears in the window, which is the same as how the MedianGroupedPreReducer works. Thus,
I created a GenericGroupedPreReducer that does this with any non-grouped pre-reducer, and
refactored the median code to also use this.
    I also added a missing clean and removed a superfluous one.

You can merge this pull request into a Git repository by running:

    $ git pull https://github.com/ggevay/flink invReduce

Alternatively you can review and apply these changes as the patch at:


To close this pull request, make a commit to your master/trunk branch
with (at least) the following in the commit message:

    This closes #856
commit 3424a6294cdda8f8b364aa68747d7890a0a9dbab
Author: Gabor Gevay <ggab90@gmail.com>
Date:   2015-05-24T10:43:30Z

    [FLINK-2145] [streaming] Fast calculation of medians of windows

commit b44d2d3323249ce5488cc2389f8fd53d3613b448
Author: Gabor Gevay <ggab90@gmail.com>
Date:   2015-06-15T15:35:47Z

    [FLINK-2143] [streaming] Added ReduceFunctionWithInverse, which sometimes speeds up reduceWindow


> Add an overload to reduceWindow which takes the inverse of the reduceFunction as a second
> ---------------------------------------------------------------------------------------------------
>                 Key: FLINK-2143
>                 URL: https://issues.apache.org/jira/browse/FLINK-2143
>             Project: Flink
>          Issue Type: Sub-task
>          Components: Streaming
>            Reporter: Gabor Gevay
>            Assignee: Gabor Gevay
> If the inverse of the reduceFunction is also available (for example subtraction when
summing numbers), then a PreReducer can maintain the aggregate in O(1) memory and O(1) time
for evict, store, and emitWindow.

This message was sent by Atlassian JIRA

View raw message