projection recipes?

[al.r...@gmail.com]

As a first introduction to Gremlin, I have been trying to understand
how to project a bipartite graph towards one of its nodesets.

Fortunately I have not found any explicit answer in the docs, so it is
been a good way to get used to the language, but on the other hand it
implies that I am not sure of the efficiency nor elegance of the
methods.

What I have come to, is the following. Sat we have the network of
users and checkins of foursquare, and we want to have a network of
"user similarity" by projecting out the places. If we want to start
from the surviving nodeset, I can do


g.V.filter{it.type=='user'}.as('a').out('was_at').in('was_at').as('b').select(['a','b']).groupCount()
{it.name}.cap()

while if we want, as it is going to happen more usually -think of a
time interval in the initial filter- from the projected subset, I can
do


g.V.filter{it.type=='place'}.sideEffect{x=it}.in('was_at').as('a').transform{x}.in('was_at').as('b').select(['a','b']).groupCount()
{it.name}.cap()

A first question is efficiency, albeit probably it is going also to
depend of the database implementation. Are these the faster recipes,
or can it be done in a better way?

Besides efficiency, another problem I see is that the projection can
not use the relative weight of the links and then it is only
implementing the "pure intersection". This is a more complex problem,
see for instance how many functions networkx implements...
http://networkx.lanl.gov/reference/algorithms.bipartite.html#module-networkx.algorithms.bipartite.projection
... and so I do not expect a simple pattern to work, but it should be
nice to discover that there is one :-)

And third issue is pipe-bility... At least the recipe output works
via REST interface, while a lot of table based solutions fail there.
But what about creating not a select but a virtual or fake edge
between nodes 'a' and 'b', so that further pipes could just believe
they are working with a real graph entity? Well, perhaps it is not a
good idea, as the fake edge is not going to be present in the in/out
edge lists of the nodes, and something is going to fail in the long
run. But I was intrigued about this possibility, can it be done?

Yours,

Alejandro Rivero

[Marko Rodriguez]

Hi Al,

I can't go through your email right now, but here is a some quick performance tips:

filter{it.type == 'user'} is going to be very slow -- replace with has('type','user')

Ha! I like your sideEffect{it=x}...transform{x} style. Never seen that before--perhaps you might want to use back() (may be more efficient).

In general, try to avoid closures as much as possible as they are slower and the Gremlin optimizer (path and query) can't reason about them.

https://github.com/tinkerpop/gremlin/wiki/Gremlin-Groovy-Path-Optimizations

Marko.

http://markorodriguez.com

[Marko Rodriguez]

Hi,

** Refer to my previous email for other optimizations. **

What I have come to, is the following. Sat we have the network of
users and checkins of foursquare, and we want to have a network of
"user similarity" by projecting out the places. If we want to start
from the surviving nodeset, I can do


g.V.filter{it.type=='user'}.as('a').out('was_at').in('was_at').as('b').select(['a','b']).groupCount()
{it.name}.cap()

g.V... is a linear scan. You will want to do g.V('type','user') (in Gremlin 2 --- or use g.idx() in Gremlin <2).

I would not groupCount with a selection as this is not memory efficient. I would do this:

g.V('type','user').each{

it.out('was_at').in('was_at').except([it]).groupCount.cap.next()

}

You can then iterate out your similarity rankings for each user. If you want a key to know what user, use an array.

g.V('type','user').each{

[it, it.out('was_at').in('was_at').except([it]).groupCount.cap.next()]

}

while if we want, as it is going to happen more usually -think of a
time interval in the initial filter- from the projected subset, I can
do

To account for a time interval, add a respective filter...

g.V('type','user').each{

it.outE('was_at').has('time',T.gt,12345).inV.in('was_at').has('time',T.gt,12345).outV.except([it]).groupCount.cap.next()

}

With the new QueryPipe, this will get compiled down appropriately.

https://github.com/tinkerpop/blueprints/wiki/Vertex-Query

A first question is efficiency, albeit probably it is going also to

depend of the database implementation. Are these the faster recipes,
or can it be done in a better way?

What I provided is going to be much more efficient than your g.V linear scan and filter{}-based model. Moreover, you have more control using each{} as you can then next out a ranking as needed -- e.g. use a range() or [0..10]. However, I don't know why you would create an n^2 ranking. That is pretty intense. I would do it for a user on demand:

g.v(1).out('was_at').in('was_at').except([g.v(1)]).groupCount.cap.next()

See how my each{} is simply iterating for all users instead of just g.v(1) (assuming v[1] is a user).

Besides efficiency, another problem I see is that the projection can
not use the relative weight of the links and then it is only
implementing the "pure intersection". This is a more complex problem,
see for instance how many functions networkx implements...
http://networkx.lanl.gov/reference/algorithms.bipartite.html#module-networkx.algorithms.bipartite.projection
... and so I do not expect a simple pattern to work, but it should be
nice to discover that there is one :-)

You can account for link weight if you want by using sideEffect and then groupCount() closures. See the closures you can provide to groupCount. The first closure allows you to control the key, the second, the value. This gives you more control over weighting the similarity.

And third issue is pipe-bility... At least the recipe output works
via  REST interface, while a lot of table based solutions fail there.
But what about creating not a select but a virtual or fake edge
between nodes 'a' and 'b', so that further pipes could just believe
they are working with a real graph entity?

Hm. You used select() is an odd way. Usually, select() is to project areas of the pipeline into the future stream -- and typically, its the last step in an expression. Crazy you can simulate an edge like this, but ... ?? ... sorta odd to me. Your best bet is to study what I provided above and perhaps you will see the more conventional way of doing things.

Good stuff man. Good luck,

Marko.

http://markorodriguez.com