You are viewing a plain text version of this content. The canonical link for it is here.
Posted to user@flink.apache.org by Benoît Hanotte <be...@campus.tu-berlin.de> on 2015/04/14 08:11:39 UTC
Nested Iterations supported in Flink?
Hello,
I'm implementing an algorithm which requires nested iterations, and, from
what I understood, this feature was not yet available in Flink [1], and my
experiments with 2 nested bulk iterations seem to confirm that. However I
came across a Flink unit test [2] using nested iterations, so I'm now a
bit confused. Could you please give me some insight on what is supported
or not in the current state of the project?
Thanks!
Benoît.
[1]
http://mail-archives.apache.org/mod_mbox/flink-user/201411.mbox/%3CCANC1h_tpNFWwrnm14+Et1yBvkQPQ1-pfk=iUPP5Un90ZgUGeyg@mail.gmail.com%3E
[2]
https://github.com/apache/flink/blob/master/flink-optimizer/src/test/java/org/apache/flink/optimizer/NestedIterationsTest.java
Re: Nested Iterations supported in Flink?
Posted by Stephan Ewen <se...@apache.org>.
I think running the program multiple times is a reasonable way to start
working on this.
I would try and see whether this can be re-written to a non-nested
iterations case. Nestes iterations algorithms may have much more overhead
to start with.
Stephan
On Tue, Apr 14, 2015 at 3:53 PM, Benoît Hanotte <
benoit.jc.hanotte@campus.tu-berlin.de> wrote:
> Thanks for you quick answers!
>
> The algorithm is the following: I've got a spatial set of data and I want
> to find dense regions. The space is beforehand discretized into "cells" of
> a fixed size. Then, for each dense cell (1st iteration), starting with the
> most dense, the algorithm tries to extend it with neighboring cells (the
> nested iteration) until the density of the obtained extended cell is under
> a threshold (and some other conditions). When that's done, the used cells
> are removed from the input set, and the next most dense cell is extended.
>
> Would running the program multiple times be efficient in that case (I
> would have to save the datasets and reload them probably)? As for using
> the mapPartition operator I think it wouldn't be possible since the nested
> iteration needs the entire cells datasets.
>
> Best,
>
> Benoît
>
>
> Le Tue, 14 Apr 2015 15:16:48 +0200, Till Rohrmann <ti...@gmail.com>
> a écrit:
>
> If your inner iterations happens to work only on the data of a single
> partition, then you can also implement this iteration as part of a
> mapPartition operator. The only problem there would be that you have to
> keep all the partition's data on the heap, if you need access to it.
>
> Cheers,
>
> Till
>
> On Tue, Apr 14, 2015 at 3:11 PM, Stephan Ewen <se...@apache.org> wrote:
>
>> Hi Benoît!
>>
>> You are right, the nested iterations are currently not supported.
>>
>> The test you found actually checks that the Optimizer gives a good error
>> message when encountering nested iterations.
>>
>> Can you write your program as one iterations (the inner) and start the
>> program multiple times to simulate the nesting?
>>
>> Greetings,
>> Stephan
>>
>>
>> On Tue, Apr 14, 2015 at 8:11 AM, Benoît Hanotte <
>> benoit.jc.hanotte@campus.tu-berlin.de> wrote:
>>
>>> Hello,
>>>
>>> I'm implementing an algorithm which requires nested iterations, and,
>>> from what I understood, this feature was not yet available in Flink [1],
>>> and my experiments with 2 nested bulk iterations seem to confirm that.
>>> However I came across a Flink unit test [2] using nested iterations, so I'm
>>> now a bit confused. Could you please give me some insight on what is
>>> supported or not in the current state of the project?
>>>
>>> Thanks!
>>>
>>> Benoît.
>>>
>>> [1]
>>> http://mail-archives.apache.org/mod_mbox/flink-user/201411.mbox/%3CCANC1h_tpNFWwrnm14+Et1yBvkQPQ1-pfk=iUPP5Un90ZgUGeyg@mail.gmail.com%3E
>>> [2]
>>> https://github.com/apache/flink/blob/master/flink-optimizer/src/test/java/org/apache/flink/optimizer/NestedIterationsTest.java
>>>
>>
>>
>
>
>
>
Re: Nested Iterations supported in Flink?
Posted by Benoît Hanotte <be...@campus.tu-berlin.de>.
Thanks for you quick answers!
The algorithm is the following: I've got a spatial set of data and I want
to find dense regions. The space is beforehand discretized into "cells" of
a fixed size. Then, for each dense cell (1st iteration), starting with the
most dense, the algorithm tries to extend it with neighboring cells (the
nested iteration) until the density of the obtained extended cell is under
a threshold (and some other conditions). When that's done, the used cells
are removed from the input set, and the next most dense cell is extended.
Would running the program multiple times be efficient in that case (I
would have to save the datasets and reload them probably)? As for using
the mapPartition operator I think it wouldn't be possible since the nested
iteration needs the entire cells datasets.
Best,
Benoît
Le Tue, 14 Apr 2015 15:16:48 +0200, Till Rohrmann
<ti...@gmail.com> a écrit:
> If your inner iterations happens to work only on the data of a single
> partition, then you can also implement this iteration as part >of a
> mapPartition operator. The only problem there would be that you have to
> keep all the partition's data on the heap, if you >need access to it.
>
> Cheers,
>
> Till
>
> On Tue, Apr 14, 2015 at 3:11 PM, Stephan Ewen <se...@apache.org> wrote:
>> Hi Benoît!
>>
>> You are right, the nested iterations are currently not supported.
>>
>> The test you found actually checks that the Optimizer gives a good
>> error message when encountering nested iterations.
>>
>> Can you write your program as one iterations (the inner) and start the
>> program multiple times to simulate the nesting?
>>
>> Greetings,
>> Stephan
>>
>>
>> On Tue, Apr 14, 2015 at 8:11 AM, Benoît Hanotte
>> <be...@campus.tu-berlin.de> wrote:
>>> Hello,
>>>
>>> I'm implementing an algorithm which requires nested iterations, and,
>>> from what I understood, this feature was not yet >>>available in Flink
>>> [1], and my experiments with 2 nested bulk iterations seem to confirm
>>> that. However I came across a >>>Flink unit test [2] using nested
>>> iterations, so I'm now a bit confused. Could you please give me some
>>> insight on what is >>>supported or not in the current state of the
>>> project?
>>>
>>> Thanks!
>>>
>>> Benoît.
>>>
>>> [1]
>>> http://mail-archives.apache.org/mod_mbox/flink-user/201411.mbox/%3CCANC1h_tpNFWwrnm14+Et1yBvkQPQ1->>>pfk=iUPP5Un90ZgUGeyg@mail.gmail.com%3E
>>> [2]
>>> https://github.com/apache/flink/blob/master/flink-optimizer/src/test/java/org/apache/flink/optimizer/>>>NestedIterationsTest.java
Re: Nested Iterations supported in Flink?
Posted by Till Rohrmann <ti...@gmail.com>.
If your inner iterations happens to work only on the data of a single
partition, then you can also implement this iteration as part of a
mapPartition operator. The only problem there would be that you have to
keep all the partition's data on the heap, if you need access to it.
Cheers,
Till
On Tue, Apr 14, 2015 at 3:11 PM, Stephan Ewen <se...@apache.org> wrote:
> Hi Benoît!
>
> You are right, the nested iterations are currently not supported.
>
> The test you found actually checks that the Optimizer gives a good error
> message when encountering nested iterations.
>
> Can you write your program as one iterations (the inner) and start the
> program multiple times to simulate the nesting?
>
> Greetings,
> Stephan
>
>
> On Tue, Apr 14, 2015 at 8:11 AM, Benoît Hanotte <
> benoit.jc.hanotte@campus.tu-berlin.de> wrote:
>
>> Hello,
>>
>> I'm implementing an algorithm which requires nested iterations, and, from
>> what I understood, this feature was not yet available in Flink [1], and my
>> experiments with 2 nested bulk iterations seem to confirm that. However I
>> came across a Flink unit test [2] using nested iterations, so I'm now a bit
>> confused. Could you please give me some insight on what is supported or not
>> in the current state of the project?
>>
>> Thanks!
>>
>> Benoît.
>>
>> [1] http://mail-archives.apache.org/mod_mbox/flink-user/
>> 201411.mbox/%3CCANC1h_tpNFWwrnm14+Et1yBvkQPQ1-pfk=
>> iUPP5Un90ZgUGeyg@mail.gmail.com%3E
>> [2] https://github.com/apache/flink/blob/master/flink-
>> optimizer/src/test/java/org/apache/flink/optimizer/
>> NestedIterationsTest.java
>>
>
>
Re: Nested Iterations supported in Flink?
Posted by Stephan Ewen <se...@apache.org>.
Hi Benoît!
You are right, the nested iterations are currently not supported.
The test you found actually checks that the Optimizer gives a good error
message when encountering nested iterations.
Can you write your program as one iterations (the inner) and start the
program multiple times to simulate the nesting?
Greetings,
Stephan
On Tue, Apr 14, 2015 at 8:11 AM, Benoît Hanotte <
benoit.jc.hanotte@campus.tu-berlin.de> wrote:
> Hello,
>
> I'm implementing an algorithm which requires nested iterations, and, from
> what I understood, this feature was not yet available in Flink [1], and my
> experiments with 2 nested bulk iterations seem to confirm that. However I
> came across a Flink unit test [2] using nested iterations, so I'm now a bit
> confused. Could you please give me some insight on what is supported or not
> in the current state of the project?
>
> Thanks!
>
> Benoît.
>
> [1] http://mail-archives.apache.org/mod_mbox/flink-user/
> 201411.mbox/%3CCANC1h_tpNFWwrnm14+Et1yBvkQPQ1-pfk=
> iUPP5Un90ZgUGeyg@mail.gmail.com%3E
> [2] https://github.com/apache/flink/blob/master/flink-
> optimizer/src/test/java/org/apache/flink/optimizer/
> NestedIterationsTest.java
>