[OSRM-talk] GPS Accuracy for match service

Kerrick Staley kstaley at lyft.com
Mon Jun 20 19:17:25 UTC 2016


The map-match algorithm's running time is O(radius^4 * samples), because
the number of states (candidate segments) is proportional to radius^2 and
the Viterbi running time is O(states^2 * samples). It's definitely a tricky
balance between (really) poor performance and poor matching.

On Mon, Jun 20, 2016 at 12:12 PM, Kerrick Staley <kstaley at lyft.com> wrote:

> FWIW we (Lyft) have found that using a query radius of 3x gps_precision is
> insufficient and causes bad matches; we use either 10x (which is what 4.x
> uses) or 5x depending on how big gps_precision is in the first place. (We
> patched 4.x to make the multiplier configurable by URL param but can't
> upstream because we're not on 5.x yet :( ). The change going from 10x to 3x
> is here
> <https://github.com/Project-OSRM/osrm-backend/commit/2ce74c05e16cd178a38c08080568b47b9ae4f08c>
> .
>
> On Mon, Jun 20, 2016 at 11:41 AM, Daniel Patterson <daniel at mapbox.com>
> wrote:
>
>> Artur,
>>
>>   The meaning is the same in both versions, "gps_precision" and
>> "radiuses" are "the size of 1 standard deviation of accuracy".
>>
>>   However, between 4.x and 5.x, the range that we check is a lot
>> narrower.  It turns out that in 4.x, the default was about 10x too large,
>> which makes map-matching very slow because of the increased number of
>> candidates that it needed to check.  The smaller the radius you can use,
>> the faster map-matching will be.
>>
>>   There's no way to change the setting globally on the URL.  You can
>> change the code and re-compile OSRM if you want to modify the default.  Not
>> the best way to do it, but all we've got at the moment.
>>
>> daniel
>>
>>
>> On Jun 20, 2016, at 11:24 AM, Artur Bialecki <abialecki at intellimec.com>
>> wrote:
>>
>> Hello,
>>
>>
>> Thank you for the answer.
>>
>>
>> Did the match algorithm change between V4.8.1 and V5.2.2? Given the
>> default settings for GPS accuracy (5), V4 seems to match roads in larger
>> radius then version V5.
>>
>>
>> Also, is there a way to globally change the default GPS accuracy instead
>> of having to specify it for every point?
>>
>>
>> Thanks you,
>>
>>
>> Artur…
>>
>>
>>
>>
>> *From:* Daniel Patterson [mailto:daniel at mapbox.com <daniel at mapbox.com>]
>> *Sent:* Friday, June 17, 2016 12:13 PM
>> *To:* Mailing list to discuss Project OSRM <osrm-talk at openstreetmap.org>
>> *Subject:* Re: [OSRM-talk] GPS Accuracy for match service
>>
>>
>> Hi Artur,
>>
>>
>>   TL;DR - there's no direct conversion from HDOP to radius, that's not
>> what HDOP is.
>>
>>
>>   Just knowing HDOP isn't enough.  HDOP is based on satellite position
>> and basically tells you "if you had perfect reception right now, the best
>> accuracy you could achieve would be X".  Less-than-perfect reception will
>> also affect accuracy, and isn't part of the HDOP calculation.  Number of
>> satellites in view, multi-path-error, etc, all contribute to inaccuracy and
>> aren't part of HDOP.
>>
>>
>>   Things like iPhones can give a reasonable estimate because they have a
>> known GPS device with known characteristics, and they're possibly
>> monitoring satellite count, signal-to-noise ratio, etc and doing a fancier
>> calculation than you get from simple NMEA sentences.
>>
>>
>>   Cheap GPS devices sometimes do something naive like 3-5m * HDOP ~= 95%
>> radius (2 standard deviations).  It's not really correct, but if that's all
>> you've got, run with it.
>>
>>
>> daniel
>>
>>
>>
>> On Jun 17, 2016, at 8:36 AM, Artur Bialecki <abialecki at intellimec.com>
>> wrote:
>>
>>
>>
>>
>> Hello,
>>
>>
>> In the documentation of the V5 match service it states that radiuses are
>> “Standard deviation of GPS precision used for map matching. If applicable
>> use GPS accuracy”. If I have HDOP, how would I convert it to the radius
>> value.
>>
>>
>> Thank you.
>>
>>
>> Artur…
>> This e-mail message is confidential, may be privileged and is intended
>> for the exclusive use of the addressee. Any other person is strictly
>> prohibited from disclosing, distributing or reproducing it. If the
>> addressee cannot be reached or is unknown to you, please inform us
>> immediately and delete this e-mail message and destroy all copies. Thank
>> you. _______________________________________________
>> OSRM-talk mailing list
>> OSRM-talk at openstreetmap.org
>> https://lists.openstreetmap.org/listinfo/osrm-talk
>>
>>
>> This e-mail message is confidential, may be privileged and is intended
>> for the exclusive use of the addressee. Any other person is strictly
>> prohibited from disclosing, distributing or reproducing it. If the
>> addressee cannot be reached or is unknown to you, please inform us
>> immediately and delete this e-mail message and destroy all copies. Thank
>> you. _______________________________________________
>> OSRM-talk mailing list
>> OSRM-talk at openstreetmap.org
>> https://lists.openstreetmap.org/listinfo/osrm-talk
>>
>>
>>
>> _______________________________________________
>> OSRM-talk mailing list
>> OSRM-talk at openstreetmap.org
>> https://lists.openstreetmap.org/listinfo/osrm-talk
>>
>>
>
>
> --
> - Kerrick
>



-- 
- Kerrick
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/osrm-talk/attachments/20160620/c1b05fc2/attachment-0001.html>


More information about the OSRM-talk mailing list