Bug in Shortest Path Evaluation

Update.

I did finally receive a response from the Support Team on the initial logging of this issue. Coincidence that this was the day after posting the issue here?

While they did fix one specific issue (although didn't explain how) there was still no acknowledgement of the fact that I have many such issues and that this should be investigated and fixed as a bug.

Comments Mike Stangel ?

Craig: My understanding is that the searching for (creation of) a path comes from first looking through an internal 'cache' of existing relationship path fragments, piecing them together, instead of doing a "fresh" search from start-to-finish (which can be quite an intensive operation).

I have seen the behavior where walking down from one profile to a child will suddenly "flip" to a completely different path shown via the other parent, not just simply adding to the one it "walked down" from. I haven't really paid close attention to the length difference between the two when that "flip" happens. Maybe there is a bug in how it decides which parent's path/fragment it looks at first and how it decides which "parent-path" to pursue...

Thanks Dan Cornett

Obviously the potential shortest path is always potentially changing and most of the time the "refresh path" action seems to fix an outdated one.

I have had a number of occasions where the "refresh" has failed to update a shortest path and as a result of previous interactions with Support I was pointed in the direction of "walking the shortest path" from start to finish, which can be a bit laborious.

I have had limited success with the above approach but still experienced occasions where navigating from a parent to child, which should present the relationship to the child as one generation from the parent (eg if parent is 14th cousin thrice removed then the child should be 15th cousin twice removed), there is an irremovable discontinuity where as in the example above the child is displayed as eg 15th cousin ie not what was expected.

The case I have described here is different again as the issue is occurring "at the start of the chain". With a known relationship from myself to a profile, there is no room for uncertainty for the relationship from my daughter to that same person. There is no tree that can be walked to force the correct result because as soon as you navigate from my daughter's profile to mine the path is now correct. The problem is that the algorithm is choosing the longer path via my wife in this instance with seemingly no way to undo this and force it to be otherwise.

It would be really nice if someone at Geni would acknowledge this bug.

It took support 2 months to respond at all and even then there was no suggestion that this issue had been passed on to anyone with the responsibility or expertise to expedite a fix.

It's a pretty fundamental issue on a Genealogy site if the correct relationship between 2 profiles is not being evaluated correctly.

I know this is a "hobby site" but regardless, I feel that some level of response is due to fee-paying customers.

Does anyone have any suggestions how best to proceed in the face of silence from Geni themselves?

Hi Craig,

The issue you reported two months ago was a simple refresh problem that is fixed with this icon right here:

The issue you've report above is (believe it or not) completely unrelated. I see the problem and we will work on a fix ASAP.

Mike

Hi Mike Stangel

Thanks for the response.

I am fully aware of the refresh path icon and have probably used it a few thousand times. The problem is that it doesnt always refresh the path correctly! While it has worked for me on many occasions it certainly didnt work for the problem I initially reported to support 2 months ago and doesnt work for the issue reported earlier in this thread. I also have many other instances of the same which I have not reported as single cases as I assume they are all symptomatic of the same underlying shortest path issue.

I am thrilled that you are acknowledging the issue and look forward to the fix being in place. Hopefully someone will let me know.

Thanks

Craig Andrew Miles I didn't handle your help ticket from 2 months ago so I didn't pick up on the fact that the refresh icon didn't work. We have released a fix for the Britney Spears problem (from your daughter) so let me know whether or not it fixes the other (refresh will be required).

Mike Stangel Thanks very much for putting a fix into work.

The signs started out encouraging when I got the expected results for the shortest path from Millie to Britney Spears. Good news!

However, things took a turn for the worse when I examined some other instances.

Here is an example:

Bear in mind that Craig (6000000079020527890) is the father of Millie (6000000079019742513), and Kelly (6000000079020670916) is the mother of Millie.

Compare these results

Anna Paquin

https://www.geni.com/api/profile-g6000000079020527890/path-to/profile-g6000000005350378009?path_type=blood&access_token=<access_token>

relationship "27th cousin"
status "done"
step_count 55
url "https://www.geni.com/path/Craig-Miles+is+related+to+Anna-Paquin?from=6000000079020527890&path_type=blood&to=6000000005350378009"

https://www.geni.com/api/profile-g6000000079020670916/path-to/profile-g6000000005350378009?path_type=blood&access_token=<access_token>

relationship "26th cousin once removed"
status "done"
step_count 54
url "https://www.geni.com/path/Kelly-Miles+is+related+to+Anna-Paquin?from=6000000079020670916&path_type=blood&to=6000000005350378009"

https://www.geni.com/api/profile-g6000000079019742513/path-to/profile-g6000000005350378009?path_type=blood&access_token=<access_token>

relationship "27th cousin twice removed"
status "done"
step_count 58
url "https://www.geni.com/path/Millie+is+related+to+Anna-Paquin?from=6000000079019742513&path_type=blood&to=6000000005350378009"

You can see that while the shortest path for Craig to Anna Paquin is 55 steps, and 54 for Kelly, the shortest path for Millie is being evaluated at 58 steps when it should obviously be 55 (via Kelly).

Furthermore, I did notice shortest paths taking longer to evaluate than I have previously witnessed - perhaps this was due to the fix implemented causing a higher workload due to more necessary path re-evaluation?

So it seems as though some other issue with the shortest path is still affecting the results?

Thanks for looking into this.

Craig Andrew Miles thanks for your diligence on this... we've just released some fixes for both performance and additional shortest-path calculations. Anna Paquin is now showing as Millie's 17th cousin as expected. Let me know if you find anything else out of sorts.

Thanks so much Mike Stangel

That's a very speedy turnaround.

All of the previous issues I have looked at so far appear to be resolved. There's still a few more to check, but I am feeling confident.

Also, performance very much improved. That's great.

I do have a question though - in the event that there are multiple shortest paths between 2 profiles with exactly the same number of steps, is there a preference order for which one is surfaced, or is it random?

I haven't got a current example unfortunately, but in the past I have experienced the following for the shortest path from a profile A to 2 different profiles X and Y which have a common ancestor M:

Shortest path from A to X via common ancestor M goes via intermediate ancestor B (A->B->M->X)
Shortest path from A to Y via common ancestor M goes via intermediate ancestor C (A->C->M->Y)

This was unexpected but led me to believe the path chosen to be random in the event that the number of steps were equal, with in this case A->M via B having the same number of steps as A->M via C.

Personally, I would prefer a predictable path in the event of equal steps, rather than a random one but I am keen to know your thoughts.

Cheers

Craig

In the case of equal number of steps, the algorithm is deterministic so it will consistently return the same path between two people but (in the interest of performance) we make no commitments as to how the algorithm chooses one path over another, equidistant one.

Thanks Mike Stangel

This is how I have observed it to be. I understand the trade-offs.