Questions about shortest path hop count in BI15.
ErvinXie opened this issue · 2 comments
BI 15 params comments says "(a) $person1Id – $person2Id pair with a distance of 4 hops. (b) $person1Id – $person2Id pair with a distance of 2 hops". However, the weight sum is required rather than the hops. So, can we assume that the shortest path's hop count is less than 4 or 2, respectively?
My spec file version is 2.2.0
Hi @ErvinXie: BI Q15 works as follows.
The parameter generator guarantees the existence of a 4-hop or 2-hop unweighted path. The existence of these paths only implies that a weighted shortest path (cheapest path) exists, i.e. person1 and person2 are in the same connected component of the graph.
When trying to find the cheapest path length, the existence of a k-hop unweighted path can be used to establish an upper bound for the path length. For example, for (b), the systems can find a cheapest path with two hops, then use its length to prune for the rest of the search. In practice, this seems to have a limited effect on runtimes and in benchmarks, I found variant (b) to be more difficult to compute than variant (a) due to its larger date interval, which is seems to be the dominating factor.
I got it! Thanks for your quick detailed reply. It helps a lot.