This is an improved version of the analysis here:
18 May - Testing with new geohash algorithm
Headlines
This is a more accurate analysis than before.
8 char geohashes are noticeably less precise than GPS point-distance calculations.
The use of 8 char geohashes + notifying only when 4 of 6 points are detected, more-or-less masks the GPS inaccuracy that we are seeing (at least for my measurements in rural Italy). It looks as though improvng GPS accuracy in MVP1 (SAF-175) may not in fact be necessary for MVP1.
GPS Reliability (SA-278 / SAF-257), however, remains absolutley critical.
Introduction
With some improvements to the tools to better simulate geohashing, I now have some more accurate data.
Note that we continue to have a very serious issue with reliability of GPS data recording. I will cover that briefly at the end, but for most of this article, we assume GPS data is recorded with 100% reliability - but not necessarily with good accuracy.
8 char Geohashes vs. GPS point distance calculations
First, what’s the impact of Geohashing vs. GPS point calculations in the context of a perfectly accurate GPS signal?
Using 8 char geohashes, we do make our detection significantly less precise.
This chart shows a couple of options for our geohash implementation.
If we compute “nearby” geohashes, as any geohash within 20m of the data point, then geohashes match a superset of points that we’d match with GPS - but the downside is that we start matching points at 40m+ distance.
This is not very surprising - if you draw a 20m radius circle on a map, and then allow for matches on all the geohashes you touch, and those geohashes can be up to 38m wide, then from time to time you will match points at a significant distance.
(note the “near geohashes” calculation is asymettric - we do it for local points on the App. We don’t do this for points coming from Safe Places, which are expected to be always mapped to a single geohash - except in rare cases where a Contact Tracer may add a 2nd geohash (e.g. if a visited location covers two geohash tiles).
So simply by moving to 8 char geohashes, we make things a lot less atccurate.
An appealing fix is to move the circle use use to select “nearby” geohashes to a 10m radiua. This does mean we will occasionally miss points within 20m, but it reduces the overall footrpint a lot, and reduce distant false positives. This is shown by the yellow line on the chart above. For the rest of this article, we assume that we will use this policy.
The other fix is to move to smaller geohash tiles, e.g. 5m x 5m 9 char geohashes. We absolutely can do that, and we can then get our match footprint much closer to what we achieve with GPS distance. But there is more implementation complexity, so we assume this is not something we will do for MVP1.
In practise for MVP1 9and possibly beyond, overall inaccuracy in GPS means that the above difference won’t actually be relevant.
Impact of GPS noise
We look first at the impact of GPS noise on the GPS point-based solution (i.e. not Geohashes). While this isn’t a planned implementation, we look at this:
To establish that the geohash-related inaccuracy above isn’t a big deal in the current context
To have a point of comparison when we come to look at GPS inaccuracy on the geophash solution
Now we have introduced noise, we have to introduce a time parameter to our experiement, and for these charts I chose a 1 hour timeframe.
So if 2 people were stood at the designated distance apart for an hour, this chart shows the percentage likelihood of a notification.
The above chart shows 3 lines
The orange line is the baseline from the previous chart
The blue line is what happens when you add current levels of GPS noise in, and notify whenever an intersection is detected. This is much worse than the geohashes above, in particular we will see false positives at 70m. Given that the area covered is n-squared with the distance away, false positives at this range are a real problem.
The grey line shows what happens when we apply a rule that we must trigger 4 notifications within a 30 minute period (i.e. 66% of 6 checks) at some point within the hour.
Applying this 4/6 policy does create the potential for us to miss some times when people are in close proximity, particularly in to 10m to 20m range. However it also brings the number of false positives to a sensible level.
As we’ll see next, this policy actually works even better in the geohash case.
GPS noise + Geohashes
This chart is the same as the previous one (probability of a notification, with 2 people in static positions a fixed distance apart for an hour), but now using 78 char geohashes for matching.
I used the radius of 10m for “nearby” geohashes, as per discussion above.
The orange line shows the impact of noise if we treated every match as a notification - as you can see we end up with high numbers of false positives at 70m distance and beyond - unaceptable.
The blue line shows what we’d achieve with 8 char geohash matching, with perfect GPS accuracy. It is the same as the yellow line in the 1st chart.
The interesting thing this chart shows is that if we apply a 4/6 Notification policy in this case, we get a very close approximation to this line.
That indicates that implementing the 4/6 Notifcation policy almost completely removes the impact of our current levels of GPS inaccuracy.
If that seems iplausible consider that while the GPS signal does vary significantly, most of the noise consists of single “wild” points - the 4/6 Notiication policy means that very few of these will yield false positives.
On the other hand, the fairly broad geohash tiles help us to avoid false negatives.
Net of this:
if 8 char geohash matching is good enough fror MVP1 - see 1st chart for inherent deficiencies in 8 char geohashes vs GPS point/distance matching
and if we are happy with the 4/6 notification policy (which means we cannot detect encounters less than 20 mins in duration
then from a technical pov, we don’t actually need to fix the GPS accuracy issues in MVP1.
However we may decide that we need to make progress there for other reasons, credibility would be a key one, given the very public visibility of teh data that we share.
What about Reliability?
The elephant in the room is Reliability of our production of GPS data. At the moment (20/5), the currwent software generates only about 68% of the expected data points on Android, and iOS may be even worse.
When you allow for reliability issues on both parties, and apply the 4/6 notification rule, we end up with notifications for only 35% of instances where 2 people are together for an hour.
If contact tracers fill in missing points on the data that they process, this will help somewhat - we’ve not modelled that impact, but it would presumably get us into the 50-60% range. This is still a very long way from where we need to be…