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 <[email protected]> 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 <[email protected]> > 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 <[email protected]> >> 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:[email protected] <[email protected]>] >> *Sent:* Friday, June 17, 2016 12:13 PM >> *To:* Mailing list to discuss Project OSRM <[email protected]> >> *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 <[email protected]> >> 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 >> [email protected] >> 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 >> [email protected] >> https://lists.openstreetmap.org/listinfo/osrm-talk >> >> >> >> _______________________________________________ >> OSRM-talk mailing list >> [email protected] >> https://lists.openstreetmap.org/listinfo/osrm-talk >> >> > > > -- > - Kerrick > -- - Kerrick
_______________________________________________ OSRM-talk mailing list [email protected] https://lists.openstreetmap.org/listinfo/osrm-talk
