giraph-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Pushparaj Motamari <pushpara...@gmail.com>
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 <janlugt@gmail.com> 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 <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