Hi all,
I am implementing a simple triangle counting example for a workshop with vertex-centric iteration and I found that the updateVertex method only gets called if there are new messages for that vertex. Is it the expected behavior? I know that the iteration should stop for the given vertex when the we don't change the vertex value but (at least in my case) it would be useful if the updateVertex got called with an empty message iterator. I guess receiving zero messages might have a meaning in other cases too, and the user would like to update the vertex value. Does changing the current behavior make sense? Cheers, Gabor |
Hello Gabor,
Yes, currently updateVertex only gets called when a new message was received. Could you please describe the logic behind your triangle count? The one I know is described at the beginning of page 1643 in this article: http://www.cc.gatech.edu/~bader/papers/GraphBSPonXMT-MTAAP2013.pdf As you can see, each time(for all the three supersteps), a message gets sent. Here is my suboptimal implementation of the algorithm in the paper (it's supposed to prove that high degree nodes overload the system): https://github.com/andralungu/gelly-partitioning/commit/224cb9b6917c2320e16a657a549b2a0313aeb300 It needs some serious rebasing. I'll get to it this weekend :). Nevertheless, it should serve as a starting point for your implementation. Let us know if you have further questions! Andra P.S. I'm not sure calling vertexUpdate with an empty message iterator would be so straightforward to implement. I'll have to look into it a bit more once I get some spare time :) On Thu, Apr 16, 2015 at 9:44 PM, Hermann Gábor <[hidden email]> wrote: > Hi all, > > I am implementing a simple triangle counting example for a workshop with > vertex-centric iteration and I found that the updateVertex method only gets > called if there are new messages for that vertex. Is it the expected > behavior? > > I know that the iteration should stop for the given vertex when the we > don't change the vertex value but (at least in my case) it would be useful > if the updateVertex got called with an empty message iterator. I guess > receiving zero messages might have a meaning in other cases too, and the > user would like to update the vertex value. > Does changing the current behavior make sense? > > Cheers, > Gabor > |
In reply to this post by Hermann Gábor
Hi Gabor,
the vertex-centric iteration implements the Pregel model, according to which a vertex is "active" during a superstep only when there are messages for this vertex. So, the behavior you are seeing is intended, yes :-) The logic behind this is that a vertex value gets updated by performing some computation on the received messages. Thus, there would be no vertex update if there are no new messages. If you want to keep a vertex active even when there are no messages sent to it, you could have it send a dummy message to itself. However, if your algorithm requires all vertices to be active in all supersteps, then you are probably looking for a bulk iteration instead. Since you're mentioning that you're implementing triangle counting, note that with Gelly you don't need to implement this as an iterative algorithm. Actually, it is probably a bad idea. In a system like Giraph, you don't have another choice because everything has to follow the Pregel model and be expressed as a series of supersteps. However, triangle counting is not an iterative algorithm; it consists of well-defined steps which you can express with the neighborhood and join functions of Gelly. Finally, you might want to take a look at the Flink examples. There are two implementations of triangle count there :-) Cheers, -Vasia. On 16 April 2015 at 21:44, Hermann Gábor <[hidden email]> wrote: > Hi all, > > I am implementing a simple triangle counting example for a workshop with > vertex-centric iteration and I found that the updateVertex method only gets > called if there are new messages for that vertex. Is it the expected > behavior? > > I know that the iteration should stop for the given vertex when the we > don't change the vertex value but (at least in my case) it would be useful > if the updateVertex got called with an empty message iterator. I guess > receiving zero messages might have a meaning in other cases too, and the > user would like to update the vertex value. > Does changing the current behavior make sense? > > Cheers, > Gabor > |
In reply to this post by Andra Lungu
Hey,
Thank you both for your help :) I was missing this point in the Pregel model. I thought it would be expected to receive empty message iterators. Yes, I know it is not the best use-case for vertex-centric iteration as there are well-defined steps, and also know the Flink examples. I only wanted this as a demonstration for the participants of the workshop (among other examples) of thinking in the vertex-centric Pregel model. Then I would show them the other solution that fits the problem more. Of course, I could implement triangle count with the vertex-centric iteration too, but I ran into this behavior and was not sure if it was expected. I might move on to other examples. Thanks anyway :) Cheers, Gabor |
Free forum by Nabble | Edit this page |