flink-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Stephan Ewen <se...@apache.org>
Subject Re: DeltaIterations: Solution set delta does not depend on workset
Date Tue, 10 Jun 2014 14:31:18 GMT
Hey!

The way you have written the algorithm strikes me actually as a case for
bulk iterations. Delta iterations are typically cases where the work set
sizes goes down (not strictly up, as here).

In your specific code, the problem is that you can actually only
join/cogroup with the solution set, and produce deltas for it (deltas are
merged in to the solution set). You do not re-assign the solution set.

In order to grow the solution set by a set of elements, make a delta where
elements have new keys (do not replace any the current elements). When
adding the delta to what is already there, you get a union, with the
special condition that it is a set union on the keys, and if a key existed
before, it gets replaced by the delta entry with the same key. So the
solution set delta is just the result of the "newWorkSet" variable. No need
to union before.

For the workset, you may have to rethink the algorithm. The way you wrote
it, the workset will always grow. A delta iteration terminates when the
workset is empty. Try and write your algorithm such that the workset really
contains only the changes that are relevant to the next iteration. If the
changes become zero, the work is done and the iteration terminates.

Stephan

Mime
  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message