giraph-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Pushparaj Motamari <>
Subject Re: RandomVertexId
Date Mon, 16 Dec 2013 22:41:54 GMT
Thank You for your suggestions

On Tue, Dec 17, 2013 at 3:19 AM, Jan van der Lugt <> wrote:

> Hi Pushparaj,
> I would not recommend doing either of these latter two approaches, since
> the first one will only work for small graphs (in which case: why use a
> distributed platform like Giraph?) and the second one does not give you
> true random vertices. To do this efficiently, you would have to implement
> it on a lower level in the Giraph stack, since the Pregel model prevents
> you from doing it in another way than aggregators. Implementing this in the
> WorkerContext could be slightly more efficient, but for big graphs this
> would be unfeasible as well, because you are basically creating a copy of
> the vertices in your graph in a way that you can access it slightly more
> flexible. I think it is fair to file a JIRA to request this functionality.
> A computationally more expensive, but memory-wise more efficient way to do
> this would be to have every vertex generate a random integer/long,
> aggregate it to a custom MaximumAggregator (that also keeps track of a
> second number that denotes the number of times the maximum occured) and
> repeat this until only one vertex has picked the maximum value, but that
> can take quite a few supersteps, which each require a pass over the entire
> graph.
> - Jan
> On Mon, Dec 16, 2013 at 1:11 PM, Ameya Vilankar <>wrote:
>> Hi
>> There are several ways of doing this.
>> If you know you vertex Ids lie between a certain range of values like
>> from 0 - (some value). Then you can simple generate a random value in that
>> range and call sendMessage to send message to the randomly selected vertex.
>> However, if your vertices do not lie in a certain range and you try
>> sending a value to a non-existent vertex, giraph will automatically create
>> the vertex(to the best of my knowledge.).
>> A simpler way is have every vertex send its id to an aggregator and that
>> will accumulate an array of all vertex ids which will be available next
>> superstep to all the other vertices. Then they can randomly select a vertex
>> id and send a message. But again, if you have millions of vertices , you
>> would run into scalability problems with array of vertex ids growing too
>> large. A simpler alternative is to send a random message to the existing
>> edges of the vertex because to already have access to it.
>> Thanks,
>> Ameya.
>> On Mon, Dec 16, 2013 at 7:41 AM, Pushparaj Motamari <
>>> wrote:
>>> Hi,
>>> In a compute method I would like to send message to a random vertex, how
>>> could I able to get random vertexid?
>>> Thanks
>>> Pushparaj

View raw message