On 9/7/11 3:49 PM, Jake Mannix wrote:
On Wed, Sep 7, 2011 at 10:43 PM, Dmitriy Ryaboy <dmit...@twitter.com <mailto:dmit...@twitter.com>> wrote:

    Something else to think about -- in some cases you may want to
    implement extreme compression of the edge list. For example, we might
    want to calculate n-th degree reach for all nodes in a graph. Given a
    graph with a few nodes with lots of incoming edges ("biebernodes", we
    call them), anything that jumps across them winds up essentially
    replicating large chunks of the graph to each node. Things like RLE
    might make sense when you are doing that sort of thing in memory and
    only have so many terabytes of that lying around.

Right, in some cases, we may want to not have edge values at all.  Just
existence in the vertex's target list of a target vertex id denotes "connection",
and so "SortedMap<I, Edge<E,I>>" gets replaced with "long[]".
In this type of case, you could also use the vertex value to store a application specific set of edges and edge values (if any).

Reply via email to