giraph-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Eli Reisman <initialcont...@gmail.com>
Subject Re: [jira] [Commented] (GIRAPH-191) Random Walks on Graphs
Date Mon, 13 Aug 2012 03:42:44 GMT
Yeah its too bad there isn't an easier way to do this, if you want just
bare metal performance then per-vertex internal state regarding out-edges
could easily be an array of primitives, during the calculation steps you
really only need writables for outgoing messages on the wire, but the whole
framework is really interwoven with them. Several people here were talking
about this same problem. I guess the need for writables during the calc
stages varies depending on your algorithm and the nature of each vertex's
interaction with non local vertices. Ideally we could deal with writables
only in the InputSplit and final output stages and use Netty to send
whatever compact data structures we want to populate the application with
but that might be a few JIRA's away.



On Sat, Aug 11, 2012 at 11:59 AM, Alessandro Presta <alessandro@fb.com>wrote:

> Hi Gianmarco,
>
> I sympathize with that. However, I can't think of a way to avoid it:
> Vertex needs to be defined in terms of Writables, we depend on that for
> serialization (which enables communication and fault tolerance).
> Was it any different in the 0.1 API? The only thing I can think of is that
> now a vertex with weighted edges needs to return Edge objects in its
> iterator.
>
> That said, if you're writing your own vertex with optimized edge storage,
> I guess you could add iterators over primitiave types, and use those in
> your algorithm. However, for example, you would still have to wrap values
> in Writables for message passing.
> But yeah, if this is for a vertex that gets shipped with Giraph, we
> probably don't want to do that.
>
> Please let me know if I understood the issue and any ideas you might have
> to improve it.
>
> Alessandro
>
> On 8/10/12 6:37 PM, "Gianmarco De Francisci Morales" <gdfm@apache.org>
> wrote:
>
> >Hi Alessandro,
> >
> >My main concern is that I need a lot of wrapping objects if I want to keep
> >data as primitive values in the vertex implementation.
> >Right now I have some wrapper iterables/iterators that do that, but I
> >think
> >all this temporary object creation kind of kills the memory efficiency of
> >the vertex implementation.
> >
> >I am rebasing the patch once again after the aggregator changes (and
> >trying
> >to understand how they work now).
> >As soon as I finish and Jira comes up again I will post an updated patch.
> >
> >Cheers,
> >--
> >Gianmarco
> >
> >
> >
> >On Thu, Aug 9, 2012 at 4:00 PM, Alessandro Presta (JIRA)
> ><jira@apache.org>wrote:
> >
> >>
> >>     [
> >>
> >>https://issues.apache.org/jira/browse/GIRAPH-191?page=com.atlassian.jira
> .
> >>plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13431815#c
> >>omment-13431815]
> >>
> >> Alessandro Presta commented on GIRAPH-191:
> >> ------------------------------------------
> >>
> >> Gianmarco: can you elaborate more on the difficulties you're having with
> >> vertex implementation?
> >>
> >> > Random Walks on Graphs
> >> > ----------------------
> >> >
> >> >                 Key: GIRAPH-191
> >> >                 URL: https://issues.apache.org/jira/browse/GIRAPH-191
> >> >             Project: Giraph
> >> >          Issue Type: New Feature
> >> >          Components: examples
> >> >    Affects Versions: 0.2.0
> >> >            Reporter: Gianmarco De Francisci Morales
> >> >            Assignee: Gianmarco De Francisci Morales
> >> >         Attachments: GIRAPH-191-1.patch, GIRAPH-191.2.patch,
> >> GIRAPH-191.patch, PIG-191.1.patch
> >> >
> >> >
> >> > Implementing RWR on Giraph should be a very simple modification of the
> >> SimplePageRankVertex code.
> >> > {code}
> >> > if ( myID == sourceID )
> >> >       DoubleWritable vertexValue = new DoubleWritable((0.15f + 0.85f *
> >> sum);
> >> > else
> >> >       DoubleWritable vertexValue = new DoubleWritable(0.85f * sum);
> >> > {code}
> >> > It would be nice to make it as configurable as possible by using
> >> parametric damping factors, preference vectors, strongly preferential,
> >> etc...
> >> > More or less along these lines:
> >> >
> >>
> >>
> http://law.dsi.unimi.it/software/docs/it/unimi/dsi/law/rank/PageRank.html
> >>
> >> --
> >> This message is automatically generated by JIRA.
> >> If you think it was sent incorrectly, please contact your JIRA
> >> administrators:
> >>
> https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
> >> For more information on JIRA, see:
> >>http://www.atlassian.com/software/jira
> >>
> >>
>
>

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