<div dir="ltr">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.</div><div class="gmail_extra"><br><div class="gmail_quote">On Mon, Jun 20, 2016 at 12:12 PM, Kerrick Staley <span dir="ltr"><<a href="mailto:kstaley@lyft.com" target="_blank">kstaley@lyft.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">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 <a href="https://github.com/Project-OSRM/osrm-backend/commit/2ce74c05e16cd178a38c08080568b47b9ae4f08c" target="_blank">here</a>.</div><div class="gmail_extra"><div><div class="h5"><br><div class="gmail_quote">On Mon, Jun 20, 2016 at 11:41 AM, Daniel Patterson <span dir="ltr"><<a href="mailto:daniel@mapbox.com" target="_blank">daniel@mapbox.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word">Artur,<div><br></div><div>  The meaning is the same in both versions, "gps_precision" and "radiuses" are "the size of 1 standard deviation of accuracy".</div><div><br></div><div>  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.</div><div><br></div><div>  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.</div><span><font color="#888888"><div><br></div><div>daniel</div></font></span><div><div><div><br></div><div><br></div><div><div><blockquote type="cite"><div>On Jun 20, 2016, at 11:24 AM, Artur Bialecki <<a href="mailto:abialecki@intellimec.com" target="_blank">abialecki@intellimec.com</a>> wrote:</div><br><div><div style="font-family:Helvetica;font-size:12px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px"><div style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)">Hello,</span></div><p class="MsoNormal" style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)"> </span></p><div style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)">Thank you for the answer.</span></div><p class="MsoNormal" style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)"> </span></p><div style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)">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.<span> </span></span></div><p class="MsoNormal" style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)"> </span></p><div style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)">Also, is there a way to globally change the default GPS accuracy instead of having to specify it for every point?</span></div><p class="MsoNormal" style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)"> </span></p><div style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)">Thanks you,</span></div><p class="MsoNormal" style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)"> </span></p><div style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)">Artur…</span></div><p class="MsoNormal" style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)"> </span></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)"> </span></p><div><div style="border-style:solid none none;border-top-color:rgb(225,225,225);border-top-width:1pt;padding:3pt 0in 0in"><div style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif"><b><span style="font-size:11pt;font-family:Calibri,sans-serif">From:</span></b><span style="font-size:11pt;font-family:Calibri,sans-serif"><span> </span>Daniel Patterson [<a href="mailto:daniel@mapbox.com" target="_blank">mailto:daniel@mapbox.com</a>]<span> </span><br><b>Sent:</b><span> </span>Friday, June 17, 2016 12:13 PM<br><b>To:</b><span> </span>Mailing list to discuss Project OSRM <<a href="mailto:osrm-talk@openstreetmap.org" target="_blank">osrm-talk@openstreetmap.org</a>><br><b>Subject:</b><span> </span>Re: [OSRM-talk] GPS Accuracy for match service</span></div></div></div><p class="MsoNormal" style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif"> </p><div style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif">Hi Artur,</div><div><p class="MsoNormal" style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif"> </p></div><div><div style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif">  TL;DR - there's no direct conversion from HDOP to radius, that's not what HDOP is.</div></div><div><p class="MsoNormal" style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif"> </p></div><div><div style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif">  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.</div></div><div><p class="MsoNormal" style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif"> </p></div><div><div style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif">  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.</div></div><div><p class="MsoNormal" style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif"> </p></div><div><div style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif">  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.</div></div><div><p class="MsoNormal" style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif">  </p></div><div><div style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif">daniel</div></div><div><p class="MsoNormal" style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif"> </p><div><blockquote style="margin-top:5pt;margin-bottom:5pt"><div><div style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif">On Jun 17, 2016, at 8:36 AM, Artur Bialecki <<a href="mailto:abialecki@intellimec.com" style="color:purple;text-decoration:underline" target="_blank">abialecki@intellimec.com</a>> wrote:</div></div><p class="MsoNormal" style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif"> </p><div><div><p class="MsoNormal" style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif"><span style="font-size:11pt;font-family:Calibri,sans-serif"> </span></p><div><div style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif"><span style="font-size:11pt;font-family:Calibri,sans-serif">Hello,</span></div></div><p class="MsoNormal" style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif"><span style="font-size:11pt;font-family:Calibri,sans-serif"> </span></p><div><div style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif"><span style="font-size:11pt;font-family:Calibri,sans-serif">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.</span></div></div><p class="MsoNormal" style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif"><span style="font-size:11pt;font-family:Calibri,sans-serif"> </span></p><div><div style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif"><span style="font-size:11pt;font-family:Calibri,sans-serif">Thank you.</span></div></div><p class="MsoNormal" style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif"><span style="font-size:11pt;font-family:Calibri,sans-serif"> </span></p><div><div style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif"><span style="font-size:11pt;font-family:Calibri,sans-serif">Artur…</span></div></div></div><div style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif"><span style="font-size:9pt;font-family:Helvetica,sans-serif">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. _______________________________________________<br>OSRM-talk mailing list<br></span><a href="mailto:OSRM-talk@openstreetmap.org" style="color:purple;text-decoration:underline" target="_blank"><span style="font-size:9pt;font-family:Helvetica,sans-serif;color:rgb(149,79,114)">OSRM-talk@openstreetmap.org</span></a><span style="font-size:9pt;font-family:Helvetica,sans-serif"><br></span><a href="https://lists.openstreetmap.org/listinfo/osrm-talk" style="color:purple;text-decoration:underline" target="_blank"><span style="font-size:9pt;font-family:Helvetica,sans-serif;color:rgb(149,79,114)">https://lists.openstreetmap.org/listinfo/osrm-talk</span></a></div></div></blockquote></div><p class="MsoNormal" style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif"> </p></div></div><span style="font-family:Helvetica;font-size:12px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;float:none;display:inline!important">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. _______________________________________________</span><br style="font-family:Helvetica;font-size:12px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px"><span style="font-family:Helvetica;font-size:12px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;float:none;display:inline!important">OSRM-talk mailing list</span><br style="font-family:Helvetica;font-size:12px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px"><a href="mailto:OSRM-talk@openstreetmap.org" style="color:purple;text-decoration:underline;font-family:Helvetica;font-size:12px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px" target="_blank">OSRM-talk@openstreetmap.org</a><br style="font-family:Helvetica;font-size:12px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px"><a href="https://lists.openstreetmap.org/listinfo/osrm-talk" style="color:purple;text-decoration:underline;font-family:Helvetica;font-size:12px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px" target="_blank">https://lists.openstreetmap.org/listinfo/osrm-talk</a></div></blockquote></div><br></div></div></div></div><br>_______________________________________________<br>
OSRM-talk mailing list<br>
<a href="mailto:OSRM-talk@openstreetmap.org" target="_blank">OSRM-talk@openstreetmap.org</a><br>
<a href="https://lists.openstreetmap.org/listinfo/osrm-talk" rel="noreferrer" target="_blank">https://lists.openstreetmap.org/listinfo/osrm-talk</a><br>
<br></blockquote></div><br><br clear="all"><div><br></div></div></div><span class="HOEnZb"><font color="#888888">-- <br><div data-smartmail="gmail_signature"><div dir="ltr">- Kerrick</div></div>
</font></span></div>
</blockquote></div><br><br clear="all"><div><br></div>-- <br><div class="gmail_signature" data-smartmail="gmail_signature"><div dir="ltr">- Kerrick</div></div>
</div>