Performance is not good when finding the paths between 2 nodes with k-shortest

Users Dgraph
1

Hi there,
I tried to find paths between 2 nodes, currently only k-shortest path queries could be used, the performance was not good when i queried with numpaths larger than 10.
Is there any suggestion on that ?
Why the performance lose a lot when numpaths become larger?
Why the performance changed with depth 10?
Any way to improve it?

I used the dgraph-ha.yaml to deploy my dgraph
and here’s my ql to query
{
path as shortest(from: 0x107db5, to: 0x138ac1, numpaths:10) {
_Concept
~_Concept
_MainProduct
~_MainProduct
}
path(func: uid(path)) {
Name
StockCode
}
}

here’s the results:
10<=numpaths<=20 : 9.5s to 10s
numpaths<10 : 100 to 300ms

BTW, i used the HDD for this test

Thanks

2

k-shortest paths is not a particularly cheap calculation. Yen’s
algorithm (I don’t know if dgraph uses this, but it likely uses
something similar - it does look much more complicated than it needs to
be though) has a time complexity of O(k|V|(|E|+|V|log|V|)).

4

hi kortschark, thanks for your reply. With the time complexity, it should cost more time with larger k. But by my testing, the time didn’t change a lot when i changed the k to 10 or larger, it looks very strange. Do you have any idea on that?

5

I’ve just had a closer look at the code, and despite the illegibility of it it’s reasonably clear that they are not using Yan, though they are doing similar work less efficiently.

I can’t see any discontinuity at 10 unless it’s something in the runtime (grow map?, though that seems unlikely) or something to do with the backing store (more likely).

6

thanks for your info, i’ll try to find if there’s some limitation on the backing store

7

This topic was automatically closed 30 days after the last reply. New replies are no longer allowed.