You are viewing a plain text version of this content. The canonical link for it is here.
Posted to user@giraph.apache.org by Claudio Martella <cl...@gmail.com> on 2011/09/13 12:09:03 UTC
ValueIndexed OutEdgeMap
Hello list,
I'm currently implementing large scale path traversals over an RDF graph.
the traversals are defined by the starting vertex and a set of edge labels
that have to be traversed, if possible, to obtain all the wanted paths. In
my current scenario the vertexID is Text, and the Edge is <Text, Text> as
well, as the edge value is the edge label. For obvious reasons, it would be
much more efficient to be able to obtain all the edges with a matching Edge
label (value), without iterating through the whole vertex edge list looking
for them (given avg vertex degree of K i'd go from O(K) to O(logK) at
least). I thought about creating my own labelledOutEdgeMap and populate it
by overriding Vertex.addEdge(), but that's final. I thought about adding a
method but VertexReader.next() is receiving a MutableVertex.
Do you have any suggestions?
TIA
--
Claudio Martella
claudio.martella@gmail.com
Re: ValueIndexed OutEdgeMap
Posted by Jake Mannix <ja...@gmail.com>.
On Tue, Sep 13, 2011 at 4:44 PM, Claudio Martella <
claudio.martella@gmail.com> wrote:
> Oh, misunderstanding. My code (github's I guess) and the javadoc on
> the apache site showed BasicVertex as an interface. Now everything
> makes sense.
>
BasicVertex was an interface until Sunday night, I think (welcome to the
bleeding edge
of the Incubator!), so it's not your fault. And the GitHub mirror is
sometimes
a day or so behind svn trunk (which makes it even less your fault).
> Thanks for the feedback, made my day!
>
Not a problem. GIRAPH-31 may be committed tonight (according to Avery), so
I'd wait until that goes in to implement your MutableVertex subclass. Once
you
do, let us know how the API feels, as it's in flux, and user feedback is
much
appreciated!
-jake
On Wed, Sep 14, 2011 at 1:01 AM, Jake Mannix <ja...@gmail.com> wrote:
> >
> > On Tue, Sep 13, 2011 at 3:34 PM, Claudio Martella
> > <cl...@gmail.com> wrote:
> >>
> >> ok, i understand. you suggest i IMPLEMENT BasicVertex and encapsulate
> >> Vertex. This sounds like a possibility. Still I think there should be
> >> an implementation without final addEdge (as the rest isn't final).
> >
> > BasicVertex is now an abstract class, not an interface, which implements
> > some
> > of the required functionality. MutableVertex defines addEdge() as
> > an abstract method, so if you extend MutableVertex, you can have it add
> to
> > your own data structure - do *not* encapsulate a Vertex, just do what you
> > need
> > in your MutableVertex subclass.
> > Vertex has a final addEdge() method, because its subclasses are depending
> > on the fact that it's adding edges to the TreeMap that it contains.
> > -jake
> >
> >>
> >> On Tue, Sep 13, 2011 at 6:31 PM, Jake Mannix <ja...@gmail.com>
> >> wrote:
> >> > Claudio,
> >> > If your vertex class has special internal data structures, what
> you'll
> >> > want to do is subclass either BasicVertex, or MutableVertex, not
> Vertex.
> >> > And then yes, add a "getEdgesByValue()" or whatever to that class.
> >> > -jake
> >> >
> >> > On Tue, Sep 13, 2011 at 8:22 AM, Claudio Martella
> >> > <cl...@gmail.com> wrote:
> >> >>
> >> >> Hi Jake,
> >> >> thanks for the feedback. I checked out the patch, but it looks like
> >> >> it's
> >> >> changing just the "read" access visibility. How could I provide a
> >> >> "value"-indexed internal datastructure according to the new api? the
> >> >> new
> >> >> addEdge is stil final. I can add my own "getEdgesByValue()" (as I
> might
> >> >> have
> >> >> more outedges with the same label) to my own vertex, but i must be
> able
> >> >> to
> >> >> modify override the addEdge() somehow.
> >> >>
> >> >> On Tue, Sep 13, 2011 at 4:55 PM, Jake Mannix <ja...@gmail.com>
> >> >> wrote:
> >> >>>
> >> >>> Hi Claudio,
> >> >>> So what you want is to be able to build up your own
> >> >>> application-specific data structure for the outbound edges of a
> vertex
> >> >>> (in
> >> >>> your case, one that effectively supports fulltext search on the edge
> >> >>> values)?
> >> >>> Check out: https://issues.apache.org/jira/browse/GIRAPH-31 - this
> >> >>> change, if merged to trunk, would allow you to keep whatever edge
> >> >>> datastructure you wanted, and implement your own internal
> structures.
> >> >>> Try
> >> >>> out that patch, give a comment on the JIRA if you've got any
> thoughts!
> >> >>> -jake
> >> >>>
> >> >>> On Tue, Sep 13, 2011 at 3:09 AM, Claudio Martella
> >> >>> <cl...@gmail.com> wrote:
> >> >>>>
> >> >>>> Hello list,
> >> >>>> I'm currently implementing large scale path traversals over an RDF
> >> >>>> graph. the traversals are defined by the starting vertex and a set
> of
> >> >>>> edge
> >> >>>> labels that have to be traversed, if possible, to obtain all the
> >> >>>> wanted
> >> >>>> paths. In my current scenario the vertexID is Text, and the Edge is
> >> >>>> <Text,
> >> >>>> Text> as well, as the edge value is the edge label. For obvious
> >> >>>> reasons, it
> >> >>>> would be much more efficient to be able to obtain all the edges
> with
> >> >>>> a
> >> >>>> matching Edge label (value), without iterating through the whole
> >> >>>> vertex edge
> >> >>>> list looking for them (given avg vertex degree of K i'd go from
> O(K)
> >> >>>> to
> >> >>>> O(logK) at least). I thought about creating my own
> labelledOutEdgeMap
> >> >>>> and
> >> >>>> populate it by overriding Vertex.addEdge(), but that's final. I
> >> >>>> thought
> >> >>>> about adding a method but VertexReader.next() is receiving a
> >> >>>> MutableVertex.
> >> >>>> Do you have any suggestions?
> >> >>>> TIA
> >> >>>>
> >> >>>> --
> >> >>>> Claudio Martella
> >> >>>> claudio.martella@gmail.com
> >> >>>
> >> >>
> >> >>
> >> >>
> >> >> --
> >> >> Claudio Martella
> >> >> claudio.martella@gmail.com
> >> >
> >> >
> >>
> >>
> >>
> >> --
> >> Claudio Martella
> >> claudio.martella@gmail.com
> >
> >
>
>
>
> --
> Claudio Martella
> claudio.martella@gmail.com
>
Re: ValueIndexed OutEdgeMap
Posted by Claudio Martella <cl...@gmail.com>.
Oh, misunderstanding. My code (github's I guess) and the javadoc on
the apache site showed BasicVertex as an interface. Now everything
makes sense.
Thanks for the feedback, made my day!
On Wed, Sep 14, 2011 at 1:01 AM, Jake Mannix <ja...@gmail.com> wrote:
>
> On Tue, Sep 13, 2011 at 3:34 PM, Claudio Martella
> <cl...@gmail.com> wrote:
>>
>> ok, i understand. you suggest i IMPLEMENT BasicVertex and encapsulate
>> Vertex. This sounds like a possibility. Still I think there should be
>> an implementation without final addEdge (as the rest isn't final).
>
> BasicVertex is now an abstract class, not an interface, which implements
> some
> of the required functionality. MutableVertex defines addEdge() as
> an abstract method, so if you extend MutableVertex, you can have it add to
> your own data structure - do *not* encapsulate a Vertex, just do what you
> need
> in your MutableVertex subclass.
> Vertex has a final addEdge() method, because its subclasses are depending
> on the fact that it's adding edges to the TreeMap that it contains.
> -jake
>
>>
>> On Tue, Sep 13, 2011 at 6:31 PM, Jake Mannix <ja...@gmail.com>
>> wrote:
>> > Claudio,
>> > If your vertex class has special internal data structures, what you'll
>> > want to do is subclass either BasicVertex, or MutableVertex, not Vertex.
>> > And then yes, add a "getEdgesByValue()" or whatever to that class.
>> > -jake
>> >
>> > On Tue, Sep 13, 2011 at 8:22 AM, Claudio Martella
>> > <cl...@gmail.com> wrote:
>> >>
>> >> Hi Jake,
>> >> thanks for the feedback. I checked out the patch, but it looks like
>> >> it's
>> >> changing just the "read" access visibility. How could I provide a
>> >> "value"-indexed internal datastructure according to the new api? the
>> >> new
>> >> addEdge is stil final. I can add my own "getEdgesByValue()" (as I might
>> >> have
>> >> more outedges with the same label) to my own vertex, but i must be able
>> >> to
>> >> modify override the addEdge() somehow.
>> >>
>> >> On Tue, Sep 13, 2011 at 4:55 PM, Jake Mannix <ja...@gmail.com>
>> >> wrote:
>> >>>
>> >>> Hi Claudio,
>> >>> So what you want is to be able to build up your own
>> >>> application-specific data structure for the outbound edges of a vertex
>> >>> (in
>> >>> your case, one that effectively supports fulltext search on the edge
>> >>> values)?
>> >>> Check out: https://issues.apache.org/jira/browse/GIRAPH-31 - this
>> >>> change, if merged to trunk, would allow you to keep whatever edge
>> >>> datastructure you wanted, and implement your own internal structures.
>> >>> Try
>> >>> out that patch, give a comment on the JIRA if you've got any thoughts!
>> >>> -jake
>> >>>
>> >>> On Tue, Sep 13, 2011 at 3:09 AM, Claudio Martella
>> >>> <cl...@gmail.com> wrote:
>> >>>>
>> >>>> Hello list,
>> >>>> I'm currently implementing large scale path traversals over an RDF
>> >>>> graph. the traversals are defined by the starting vertex and a set of
>> >>>> edge
>> >>>> labels that have to be traversed, if possible, to obtain all the
>> >>>> wanted
>> >>>> paths. In my current scenario the vertexID is Text, and the Edge is
>> >>>> <Text,
>> >>>> Text> as well, as the edge value is the edge label. For obvious
>> >>>> reasons, it
>> >>>> would be much more efficient to be able to obtain all the edges with
>> >>>> a
>> >>>> matching Edge label (value), without iterating through the whole
>> >>>> vertex edge
>> >>>> list looking for them (given avg vertex degree of K i'd go from O(K)
>> >>>> to
>> >>>> O(logK) at least). I thought about creating my own labelledOutEdgeMap
>> >>>> and
>> >>>> populate it by overriding Vertex.addEdge(), but that's final. I
>> >>>> thought
>> >>>> about adding a method but VertexReader.next() is receiving a
>> >>>> MutableVertex.
>> >>>> Do you have any suggestions?
>> >>>> TIA
>> >>>>
>> >>>> --
>> >>>> Claudio Martella
>> >>>> claudio.martella@gmail.com
>> >>>
>> >>
>> >>
>> >>
>> >> --
>> >> Claudio Martella
>> >> claudio.martella@gmail.com
>> >
>> >
>>
>>
>>
>> --
>> Claudio Martella
>> claudio.martella@gmail.com
>
>
--
Claudio Martella
claudio.martella@gmail.com
Re: ValueIndexed OutEdgeMap
Posted by Jake Mannix <ja...@gmail.com>.
On Tue, Sep 13, 2011 at 3:34 PM, Claudio Martella <
claudio.martella@gmail.com> wrote:
> ok, i understand. you suggest i IMPLEMENT BasicVertex and encapsulate
> Vertex. This sounds like a possibility. Still I think there should be
> an implementation without final addEdge (as the rest isn't final).
>
BasicVertex is now an abstract class, not an interface, which implements
some
of the required functionality. MutableVertex defines addEdge() as
an abstract method, so if you extend MutableVertex, you can have it add to
your own data structure - do *not* encapsulate a Vertex, just do what you
need
in your MutableVertex subclass.
Vertex has a final addEdge() method, because its subclasses are depending
on the fact that it's adding edges to the TreeMap that it contains.
-jake
>
> On Tue, Sep 13, 2011 at 6:31 PM, Jake Mannix <ja...@gmail.com>
> wrote:
> > Claudio,
> > If your vertex class has special internal data structures, what you'll
> > want to do is subclass either BasicVertex, or MutableVertex, not Vertex.
> > And then yes, add a "getEdgesByValue()" or whatever to that class.
> > -jake
> >
> > On Tue, Sep 13, 2011 at 8:22 AM, Claudio Martella
> > <cl...@gmail.com> wrote:
> >>
> >> Hi Jake,
> >> thanks for the feedback. I checked out the patch, but it looks like it's
> >> changing just the "read" access visibility. How could I provide a
> >> "value"-indexed internal datastructure according to the new api? the new
> >> addEdge is stil final. I can add my own "getEdgesByValue()" (as I might
> have
> >> more outedges with the same label) to my own vertex, but i must be able
> to
> >> modify override the addEdge() somehow.
> >>
> >> On Tue, Sep 13, 2011 at 4:55 PM, Jake Mannix <ja...@gmail.com>
> >> wrote:
> >>>
> >>> Hi Claudio,
> >>> So what you want is to be able to build up your own
> >>> application-specific data structure for the outbound edges of a vertex
> (in
> >>> your case, one that effectively supports fulltext search on the edge
> >>> values)?
> >>> Check out: https://issues.apache.org/jira/browse/GIRAPH-31 - this
> >>> change, if merged to trunk, would allow you to keep whatever edge
> >>> datastructure you wanted, and implement your own internal structures.
> Try
> >>> out that patch, give a comment on the JIRA if you've got any thoughts!
> >>> -jake
> >>>
> >>> On Tue, Sep 13, 2011 at 3:09 AM, Claudio Martella
> >>> <cl...@gmail.com> wrote:
> >>>>
> >>>> Hello list,
> >>>> I'm currently implementing large scale path traversals over an RDF
> >>>> graph. the traversals are defined by the starting vertex and a set of
> edge
> >>>> labels that have to be traversed, if possible, to obtain all the
> wanted
> >>>> paths. In my current scenario the vertexID is Text, and the Edge is
> <Text,
> >>>> Text> as well, as the edge value is the edge label. For obvious
> reasons, it
> >>>> would be much more efficient to be able to obtain all the edges with a
> >>>> matching Edge label (value), without iterating through the whole
> vertex edge
> >>>> list looking for them (given avg vertex degree of K i'd go from O(K)
> to
> >>>> O(logK) at least). I thought about creating my own labelledOutEdgeMap
> and
> >>>> populate it by overriding Vertex.addEdge(), but that's final. I
> thought
> >>>> about adding a method but VertexReader.next() is receiving a
> MutableVertex.
> >>>> Do you have any suggestions?
> >>>> TIA
> >>>>
> >>>> --
> >>>> Claudio Martella
> >>>> claudio.martella@gmail.com
> >>>
> >>
> >>
> >>
> >> --
> >> Claudio Martella
> >> claudio.martella@gmail.com
> >
> >
>
>
>
> --
> Claudio Martella
> claudio.martella@gmail.com
>
Re: ValueIndexed OutEdgeMap
Posted by Claudio Martella <cl...@gmail.com>.
ok, i understand. you suggest i IMPLEMENT BasicVertex and encapsulate
Vertex. This sounds like a possibility. Still I think there should be
an implementation without final addEdge (as the rest isn't final).
On Tue, Sep 13, 2011 at 6:31 PM, Jake Mannix <ja...@gmail.com> wrote:
> Claudio,
> If your vertex class has special internal data structures, what you'll
> want to do is subclass either BasicVertex, or MutableVertex, not Vertex.
> And then yes, add a "getEdgesByValue()" or whatever to that class.
> -jake
>
> On Tue, Sep 13, 2011 at 8:22 AM, Claudio Martella
> <cl...@gmail.com> wrote:
>>
>> Hi Jake,
>> thanks for the feedback. I checked out the patch, but it looks like it's
>> changing just the "read" access visibility. How could I provide a
>> "value"-indexed internal datastructure according to the new api? the new
>> addEdge is stil final. I can add my own "getEdgesByValue()" (as I might have
>> more outedges with the same label) to my own vertex, but i must be able to
>> modify override the addEdge() somehow.
>>
>> On Tue, Sep 13, 2011 at 4:55 PM, Jake Mannix <ja...@gmail.com>
>> wrote:
>>>
>>> Hi Claudio,
>>> So what you want is to be able to build up your own
>>> application-specific data structure for the outbound edges of a vertex (in
>>> your case, one that effectively supports fulltext search on the edge
>>> values)?
>>> Check out: https://issues.apache.org/jira/browse/GIRAPH-31 - this
>>> change, if merged to trunk, would allow you to keep whatever edge
>>> datastructure you wanted, and implement your own internal structures. Try
>>> out that patch, give a comment on the JIRA if you've got any thoughts!
>>> -jake
>>>
>>> On Tue, Sep 13, 2011 at 3:09 AM, Claudio Martella
>>> <cl...@gmail.com> wrote:
>>>>
>>>> Hello list,
>>>> I'm currently implementing large scale path traversals over an RDF
>>>> graph. the traversals are defined by the starting vertex and a set of edge
>>>> labels that have to be traversed, if possible, to obtain all the wanted
>>>> paths. In my current scenario the vertexID is Text, and the Edge is <Text,
>>>> Text> as well, as the edge value is the edge label. For obvious reasons, it
>>>> would be much more efficient to be able to obtain all the edges with a
>>>> matching Edge label (value), without iterating through the whole vertex edge
>>>> list looking for them (given avg vertex degree of K i'd go from O(K) to
>>>> O(logK) at least). I thought about creating my own labelledOutEdgeMap and
>>>> populate it by overriding Vertex.addEdge(), but that's final. I thought
>>>> about adding a method but VertexReader.next() is receiving a MutableVertex.
>>>> Do you have any suggestions?
>>>> TIA
>>>>
>>>> --
>>>> Claudio Martella
>>>> claudio.martella@gmail.com
>>>
>>
>>
>>
>> --
>> Claudio Martella
>> claudio.martella@gmail.com
>
>
--
Claudio Martella
claudio.martella@gmail.com
Re: ValueIndexed OutEdgeMap
Posted by Jake Mannix <ja...@gmail.com>.
I actually think the name should be reversed: everything "is a Vertex", so
that should be the base abstract class, and BasicVertex (or SimpleVertex)
should maybe be the name of "the simplest generic implementation" - ie what
is now called Vertex.
And yes, then document clearly when you should subclass which one.
-jake
On Tue, Sep 13, 2011 at 9:37 AM, Dmitriy Ryaboy <dm...@twitter.com> wrote:
> We should add that to Vertex's javadoc...
>
>
> On Tue, Sep 13, 2011 at 9:31 AM, Jake Mannix <ja...@gmail.com>wrote:
>
>> Claudio,
>>
>> If your vertex class has special internal data structures, what you'll
>> want to do is subclass either BasicVertex, or MutableVertex, not Vertex.
>> And then yes, add a "getEdgesByValue()" or whatever to that class.
>>
>> -jake
>>
>>
>> On Tue, Sep 13, 2011 at 8:22 AM, Claudio Martella <
>> claudio.martella@gmail.com> wrote:
>>
>>> Hi Jake,
>>>
>>> thanks for the feedback. I checked out the patch, but it looks like it's
>>> changing just the "read" access visibility. How could I provide a
>>> "value"-indexed internal datastructure according to the new api? the new
>>> addEdge is stil final. I can add my own "getEdgesByValue()" (as I might have
>>> more outedges with the same label) to my own vertex, but i must be able to
>>> modify override the addEdge() somehow.
>>>
>>>
>>> On Tue, Sep 13, 2011 at 4:55 PM, Jake Mannix <ja...@gmail.com>wrote:
>>>
>>>> Hi Claudio,
>>>>
>>>> So what you want is to be able to build up your own
>>>> application-specific data structure for the outbound edges of a vertex (in
>>>> your case, one that effectively supports fulltext search on the edge
>>>> values)?
>>>>
>>>> Check out: https://issues.apache.org/jira/browse/GIRAPH-31 - this
>>>> change, if merged to trunk, would allow you to keep whatever edge
>>>> datastructure you wanted, and implement your own internal structures. Try
>>>> out that patch, give a comment on the JIRA if you've got any thoughts!
>>>>
>>>> -jake
>>>>
>>>>
>>>> On Tue, Sep 13, 2011 at 3:09 AM, Claudio Martella <
>>>> claudio.martella@gmail.com> wrote:
>>>>
>>>>> Hello list,
>>>>>
>>>>> I'm currently implementing large scale path traversals over an RDF
>>>>> graph. the traversals are defined by the starting vertex and a set of edge
>>>>> labels that have to be traversed, if possible, to obtain all the wanted
>>>>> paths. In my current scenario the vertexID is Text, and the Edge is <Text,
>>>>> Text> as well, as the edge value is the edge label. For obvious reasons, it
>>>>> would be much more efficient to be able to obtain all the edges with a
>>>>> matching Edge label (value), without iterating through the whole vertex edge
>>>>> list looking for them (given avg vertex degree of K i'd go from O(K) to
>>>>> O(logK) at least). I thought about creating my own labelledOutEdgeMap and
>>>>> populate it by overriding Vertex.addEdge(), but that's final. I thought
>>>>> about adding a method but VertexReader.next() is receiving a MutableVertex.
>>>>>
>>>>> Do you have any suggestions?
>>>>>
>>>>> TIA
>>>>>
>>>>> --
>>>>> Claudio Martella
>>>>> claudio.martella@gmail.com
>>>>>
>>>>
>>>>
>>>
>>>
>>> --
>>> Claudio Martella
>>> claudio.martella@gmail.com
>>>
>>
>>
>
>
> --
> Dmitriy V Ryaboy
> Twitter Analytics
> http://twitter.com/squarecog
>
>
Re: ValueIndexed OutEdgeMap
Posted by Dmitriy Ryaboy <dm...@twitter.com>.
We should add that to Vertex's javadoc...
On Tue, Sep 13, 2011 at 9:31 AM, Jake Mannix <ja...@gmail.com> wrote:
> Claudio,
>
> If your vertex class has special internal data structures, what you'll
> want to do is subclass either BasicVertex, or MutableVertex, not Vertex.
> And then yes, add a "getEdgesByValue()" or whatever to that class.
>
> -jake
>
>
> On Tue, Sep 13, 2011 at 8:22 AM, Claudio Martella <
> claudio.martella@gmail.com> wrote:
>
>> Hi Jake,
>>
>> thanks for the feedback. I checked out the patch, but it looks like it's
>> changing just the "read" access visibility. How could I provide a
>> "value"-indexed internal datastructure according to the new api? the new
>> addEdge is stil final. I can add my own "getEdgesByValue()" (as I might have
>> more outedges with the same label) to my own vertex, but i must be able to
>> modify override the addEdge() somehow.
>>
>>
>> On Tue, Sep 13, 2011 at 4:55 PM, Jake Mannix <ja...@gmail.com>wrote:
>>
>>> Hi Claudio,
>>>
>>> So what you want is to be able to build up your own
>>> application-specific data structure for the outbound edges of a vertex (in
>>> your case, one that effectively supports fulltext search on the edge
>>> values)?
>>>
>>> Check out: https://issues.apache.org/jira/browse/GIRAPH-31 - this
>>> change, if merged to trunk, would allow you to keep whatever edge
>>> datastructure you wanted, and implement your own internal structures. Try
>>> out that patch, give a comment on the JIRA if you've got any thoughts!
>>>
>>> -jake
>>>
>>>
>>> On Tue, Sep 13, 2011 at 3:09 AM, Claudio Martella <
>>> claudio.martella@gmail.com> wrote:
>>>
>>>> Hello list,
>>>>
>>>> I'm currently implementing large scale path traversals over an RDF
>>>> graph. the traversals are defined by the starting vertex and a set of edge
>>>> labels that have to be traversed, if possible, to obtain all the wanted
>>>> paths. In my current scenario the vertexID is Text, and the Edge is <Text,
>>>> Text> as well, as the edge value is the edge label. For obvious reasons, it
>>>> would be much more efficient to be able to obtain all the edges with a
>>>> matching Edge label (value), without iterating through the whole vertex edge
>>>> list looking for them (given avg vertex degree of K i'd go from O(K) to
>>>> O(logK) at least). I thought about creating my own labelledOutEdgeMap and
>>>> populate it by overriding Vertex.addEdge(), but that's final. I thought
>>>> about adding a method but VertexReader.next() is receiving a MutableVertex.
>>>>
>>>> Do you have any suggestions?
>>>>
>>>> TIA
>>>>
>>>> --
>>>> Claudio Martella
>>>> claudio.martella@gmail.com
>>>>
>>>
>>>
>>
>>
>> --
>> Claudio Martella
>> claudio.martella@gmail.com
>>
>
>
--
Dmitriy V Ryaboy
Twitter Analytics
http://twitter.com/squarecog
Re: ValueIndexed OutEdgeMap
Posted by Jake Mannix <ja...@gmail.com>.
Claudio,
If your vertex class has special internal data structures, what you'll
want to do is subclass either BasicVertex, or MutableVertex, not Vertex.
And then yes, add a "getEdgesByValue()" or whatever to that class.
-jake
On Tue, Sep 13, 2011 at 8:22 AM, Claudio Martella <
claudio.martella@gmail.com> wrote:
> Hi Jake,
>
> thanks for the feedback. I checked out the patch, but it looks like it's
> changing just the "read" access visibility. How could I provide a
> "value"-indexed internal datastructure according to the new api? the new
> addEdge is stil final. I can add my own "getEdgesByValue()" (as I might have
> more outedges with the same label) to my own vertex, but i must be able to
> modify override the addEdge() somehow.
>
>
> On Tue, Sep 13, 2011 at 4:55 PM, Jake Mannix <ja...@gmail.com>wrote:
>
>> Hi Claudio,
>>
>> So what you want is to be able to build up your own application-specific
>> data structure for the outbound edges of a vertex (in your case, one that
>> effectively supports fulltext search on the edge values)?
>>
>> Check out: https://issues.apache.org/jira/browse/GIRAPH-31 - this
>> change, if merged to trunk, would allow you to keep whatever edge
>> datastructure you wanted, and implement your own internal structures. Try
>> out that patch, give a comment on the JIRA if you've got any thoughts!
>>
>> -jake
>>
>>
>> On Tue, Sep 13, 2011 at 3:09 AM, Claudio Martella <
>> claudio.martella@gmail.com> wrote:
>>
>>> Hello list,
>>>
>>> I'm currently implementing large scale path traversals over an RDF graph.
>>> the traversals are defined by the starting vertex and a set of edge labels
>>> that have to be traversed, if possible, to obtain all the wanted paths. In
>>> my current scenario the vertexID is Text, and the Edge is <Text, Text> as
>>> well, as the edge value is the edge label. For obvious reasons, it would be
>>> much more efficient to be able to obtain all the edges with a matching Edge
>>> label (value), without iterating through the whole vertex edge list looking
>>> for them (given avg vertex degree of K i'd go from O(K) to O(logK) at
>>> least). I thought about creating my own labelledOutEdgeMap and populate it
>>> by overriding Vertex.addEdge(), but that's final. I thought about adding a
>>> method but VertexReader.next() is receiving a MutableVertex.
>>>
>>> Do you have any suggestions?
>>>
>>> TIA
>>>
>>> --
>>> Claudio Martella
>>> claudio.martella@gmail.com
>>>
>>
>>
>
>
> --
> Claudio Martella
> claudio.martella@gmail.com
>
Re: ValueIndexed OutEdgeMap
Posted by Claudio Martella <cl...@gmail.com>.
Hi Jake,
thanks for the feedback. I checked out the patch, but it looks like it's
changing just the "read" access visibility. How could I provide a
"value"-indexed internal datastructure according to the new api? the new
addEdge is stil final. I can add my own "getEdgesByValue()" (as I might have
more outedges with the same label) to my own vertex, but i must be able to
modify override the addEdge() somehow.
On Tue, Sep 13, 2011 at 4:55 PM, Jake Mannix <ja...@gmail.com> wrote:
> Hi Claudio,
>
> So what you want is to be able to build up your own application-specific
> data structure for the outbound edges of a vertex (in your case, one that
> effectively supports fulltext search on the edge values)?
>
> Check out: https://issues.apache.org/jira/browse/GIRAPH-31 - this
> change, if merged to trunk, would allow you to keep whatever edge
> datastructure you wanted, and implement your own internal structures. Try
> out that patch, give a comment on the JIRA if you've got any thoughts!
>
> -jake
>
>
> On Tue, Sep 13, 2011 at 3:09 AM, Claudio Martella <
> claudio.martella@gmail.com> wrote:
>
>> Hello list,
>>
>> I'm currently implementing large scale path traversals over an RDF graph.
>> the traversals are defined by the starting vertex and a set of edge labels
>> that have to be traversed, if possible, to obtain all the wanted paths. In
>> my current scenario the vertexID is Text, and the Edge is <Text, Text> as
>> well, as the edge value is the edge label. For obvious reasons, it would be
>> much more efficient to be able to obtain all the edges with a matching Edge
>> label (value), without iterating through the whole vertex edge list looking
>> for them (given avg vertex degree of K i'd go from O(K) to O(logK) at
>> least). I thought about creating my own labelledOutEdgeMap and populate it
>> by overriding Vertex.addEdge(), but that's final. I thought about adding a
>> method but VertexReader.next() is receiving a MutableVertex.
>>
>> Do you have any suggestions?
>>
>> TIA
>>
>> --
>> Claudio Martella
>> claudio.martella@gmail.com
>>
>
>
--
Claudio Martella
claudio.martella@gmail.com
Re: ValueIndexed OutEdgeMap
Posted by Jake Mannix <ja...@gmail.com>.
Hi Claudio,
So what you want is to be able to build up your own application-specific
data structure for the outbound edges of a vertex (in your case, one that
effectively supports fulltext search on the edge values)?
Check out: https://issues.apache.org/jira/browse/GIRAPH-31 - this change,
if merged to trunk, would allow you to keep whatever edge datastructure you
wanted, and implement your own internal structures. Try out that patch,
give a comment on the JIRA if you've got any thoughts!
-jake
On Tue, Sep 13, 2011 at 3:09 AM, Claudio Martella <
claudio.martella@gmail.com> wrote:
> Hello list,
>
> I'm currently implementing large scale path traversals over an RDF graph.
> the traversals are defined by the starting vertex and a set of edge labels
> that have to be traversed, if possible, to obtain all the wanted paths. In
> my current scenario the vertexID is Text, and the Edge is <Text, Text> as
> well, as the edge value is the edge label. For obvious reasons, it would be
> much more efficient to be able to obtain all the edges with a matching Edge
> label (value), without iterating through the whole vertex edge list looking
> for them (given avg vertex degree of K i'd go from O(K) to O(logK) at
> least). I thought about creating my own labelledOutEdgeMap and populate it
> by overriding Vertex.addEdge(), but that's final. I thought about adding a
> method but VertexReader.next() is receiving a MutableVertex.
>
> Do you have any suggestions?
>
> TIA
>
> --
> Claudio Martella
> claudio.martella@gmail.com
>