giraph-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Jan van der Lugt <janl...@gmail.com>
Subject Re: RandomVertexId
Date Mon, 16 Dec 2013 21:49:41 GMT
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 <ameya.vilankar@gmail.com>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 <pushparajxa@gmail.com
> > 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
>>
>
>

Mime
View raw message