<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<style>
<!--
@font-face
{font-family:Helvetica}
@font-face
{font-family:Helvetica}
@font-face
{font-family:Calibri}
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Times New Roman",serif}
a:link, span.MsoHyperlink
{color:blue;
text-decoration:underline}
a:visited, span.MsoHyperlinkFollowed
{color:purple;
text-decoration:underline}
span.hoenzb
{}
span.EmailStyle18
{font-family:"Calibri",sans-serif;
color:#1F497D}
.MsoChpDefault
{font-family:"Calibri",sans-serif}
@page WordSection1
{margin:1.0in 1.0in 1.0in 1.0in}
div.WordSection1
{}
-->
</style>
</head>
<body lang="EN-US" link="blue" vlink="purple">
<div class="WordSection1">
<p class="MsoNormal"><span style="font-size:11.0pt; font-family:"Calibri",sans-serif; color:#1F497D">Thank you. This is very helpful.</span></p>
<p class="MsoNormal"><span style="font-size:11.0pt; font-family:"Calibri",sans-serif; color:#1F497D"> </span></p>
<p class="MsoNormal"><span style="font-size:11.0pt; font-family:"Calibri",sans-serif; color:#1F497D">Artur…</span></p>
<p class="MsoNormal"><span style="font-size:11.0pt; font-family:"Calibri",sans-serif; color:#1F497D"> </span></p>
<p class="MsoNormal"><b><span style="font-size:11.0pt; font-family:"Calibri",sans-serif">From:</span></b><span style="font-size:11.0pt; font-family:"Calibri",sans-serif"> Kerrick Staley [mailto:kstaley@lyft.com]
<br>
<b>Sent:</b> Monday, June 20, 2016 3:17 PM<br>
<b>To:</b> Mailing list to discuss Project OSRM <osrm-talk@openstreetmap.org><br>
<b>Subject:</b> Re: [OSRM-talk] GPS Accuracy for match service</span></p>
<p class="MsoNormal"> </p>
<div>
<p class="MsoNormal">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.</p>
</div>
<div>
<p class="MsoNormal"> </p>
<div>
<p class="MsoNormal">On Mon, Jun 20, 2016 at 12:12 PM, Kerrick Staley <<a href="mailto:kstaley@lyft.com" target="_blank">kstaley@lyft.com</a>> wrote:</p>
<blockquote style="border:none; border-left:solid #CCCCCC 1.0pt; padding:0in 0in 0in 6.0pt; margin-left:4.8pt; margin-right:0in">
<div>
<p class="MsoNormal">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>.</p>
</div>
<div>
<div>
<div>
<p class="MsoNormal"> </p>
<div>
<p class="MsoNormal">On Mon, Jun 20, 2016 at 11:41 AM, Daniel Patterson <<a href="mailto:daniel@mapbox.com" target="_blank">daniel@mapbox.com</a>> wrote:</p>
<blockquote style="border:none; border-left:solid #CCCCCC 1.0pt; padding:0in 0in 0in 6.0pt; margin-left:4.8pt; margin-right:0in">
<div>
<p class="MsoNormal">Artur,</p>
<div>
<p class="MsoNormal"> </p>
</div>
<div>
<p class="MsoNormal"> The meaning is the same in both versions, "gps_precision" and "radiuses" are "the size of 1 standard deviation of accuracy".</p>
</div>
<div>
<p class="MsoNormal"> </p>
</div>
<div>
<p class="MsoNormal"> 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.</p>
</div>
<div>
<p class="MsoNormal"> </p>
</div>
<div>
<p class="MsoNormal"> 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.</p>
</div>
<div>
<p class="MsoNormal"><span style="color:#888888"> </span></p>
</div>
<div>
<p class="MsoNormal"><span style="color:#888888">daniel</span></p>
</div>
<div>
<div>
<div>
<p class="MsoNormal"> </p>
</div>
<div>
<p class="MsoNormal"> </p>
</div>
<div>
<div>
<blockquote style="margin-top:5.0pt; margin-bottom:5.0pt">
<div>
<p class="MsoNormal">On Jun 20, 2016, at 11:24 AM, Artur Bialecki <<a href="mailto:abialecki@intellimec.com" target="_blank">abialecki@intellimec.com</a>> wrote:</p>
</div>
<p class="MsoNormal"> </p>
<div>
<div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt; font-family:"Calibri",sans-serif; color:#1F497D">Hello,</span></p>
</div>
<p class="MsoNormal"><span style="font-size:11.0pt; font-family:"Calibri",sans-serif; color:#1F497D"> </span></p>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt; font-family:"Calibri",sans-serif; color:#1F497D">Thank you for the answer.</span></p>
</div>
<p class="MsoNormal"><span style="font-size:11.0pt; font-family:"Calibri",sans-serif; color:#1F497D"> </span></p>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt; font-family:"Calibri",sans-serif; color:#1F497D">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></p>
</div>
<p class="MsoNormal"><span style="font-size:11.0pt; font-family:"Calibri",sans-serif; color:#1F497D"> </span></p>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt; font-family:"Calibri",sans-serif; color:#1F497D">Also, is there a way to globally change the default GPS accuracy instead of having to specify it for every point?</span></p>
</div>
<p class="MsoNormal"><span style="font-size:11.0pt; font-family:"Calibri",sans-serif; color:#1F497D"> </span></p>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt; font-family:"Calibri",sans-serif; color:#1F497D">Thanks you,</span></p>
</div>
<p class="MsoNormal"><span style="font-size:11.0pt; font-family:"Calibri",sans-serif; color:#1F497D"> </span></p>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt; font-family:"Calibri",sans-serif; color:#1F497D">Artur…</span></p>
</div>
<p class="MsoNormal"><span style="font-size:11.0pt; font-family:"Calibri",sans-serif; color:#1F497D"> </span></p>
<p class="MsoNormal"><span style="font-size:11.0pt; font-family:"Calibri",sans-serif; color:#1F497D"> </span></p>
<div>
<div style="border:none; border-top:solid #E1E1E1 1.0pt; padding:3.0pt 0in 0in 0in">
<div>
<p class="MsoNormal"><b><span style="font-size:11.0pt; font-family:"Calibri",sans-serif">From:</span></b><span style="font-size:11.0pt; font-family:"Calibri",sans-serif"> Daniel Patterson [<a href="mailto:daniel@mapbox.com" target="_blank">mailto:daniel@mapbox.com</a>] <br>
<b>Sent:</b> Friday, June 17, 2016 12:13 PM<br>
<b>To:</b> Mailing list to discuss Project OSRM <<a href="mailto:osrm-talk@openstreetmap.org" target="_blank">osrm-talk@openstreetmap.org</a>><br>
<b>Subject:</b> Re: [OSRM-talk] GPS Accuracy for match service</span></p>
</div>
</div>
</div>
<p class="MsoNormal"> </p>
<div>
<p class="MsoNormal">Hi Artur,</p>
</div>
<div>
<p class="MsoNormal"> </p>
</div>
<div>
<div>
<p class="MsoNormal"> TL;DR - there's no direct conversion from HDOP to radius, that's not what HDOP is.</p>
</div>
</div>
<div>
<p class="MsoNormal"> </p>
</div>
<div>
<div>
<p class="MsoNormal"> 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.</p>
</div>
</div>
<div>
<p class="MsoNormal"> </p>
</div>
<div>
<div>
<p class="MsoNormal"> 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.</p>
</div>
</div>
<div>
<p class="MsoNormal"> </p>
</div>
<div>
<div>
<p class="MsoNormal"> 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.</p>
</div>
</div>
<div>
<p class="MsoNormal"> </p>
</div>
<div>
<div>
<p class="MsoNormal">daniel</p>
</div>
</div>
<div>
<p class="MsoNormal"> </p>
<div>
<blockquote style="margin-top:5.0pt; margin-bottom:5.0pt">
<div>
<div>
<p class="MsoNormal">On Jun 17, 2016, at 8:36 AM, Artur Bialecki <<a href="mailto:abialecki@intellimec.com" target="_blank"><span style="color:purple">abialecki@intellimec.com</span></a>> wrote:</p>
</div>
</div>
<p class="MsoNormal"> </p>
<div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt; font-family:"Calibri",sans-serif"> </span></p>
<div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt; font-family:"Calibri",sans-serif">Hello,</span></p>
</div>
</div>
<p class="MsoNormal"><span style="font-size:11.0pt; font-family:"Calibri",sans-serif"> </span></p>
<div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt; 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></p>
</div>
</div>
<p class="MsoNormal"><span style="font-size:11.0pt; font-family:"Calibri",sans-serif"> </span></p>
<div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt; font-family:"Calibri",sans-serif">Thank you.</span></p>
</div>
</div>
<p class="MsoNormal"><span style="font-size:11.0pt; font-family:"Calibri",sans-serif"> </span></p>
<div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt; font-family:"Calibri",sans-serif">Artur…</span></p>
</div>
</div>
</div>
<div>
<p class="MsoNormal"><span style="font-size:9.0pt; 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" target="_blank"><span style="font-size:9.0pt; font-family:"Helvetica",sans-serif; color:#954F72">OSRM-talk@openstreetmap.org</span></a><span style="font-size:9.0pt; font-family:"Helvetica",sans-serif"><br>
</span><a href="https://lists.openstreetmap.org/listinfo/osrm-talk" target="_blank"><span style="font-size:9.0pt; font-family:"Helvetica",sans-serif; color:#954F72">https://lists.openstreetmap.org/listinfo/osrm-talk</span></a></p>
</div>
</div>
</blockquote>
</div>
<p class="MsoNormal"> </p>
</div>
</div>
<p class="MsoNormal"><span style="font-size:9.0pt; 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" target="_blank"><span style="font-size:9.0pt; font-family:"Helvetica",sans-serif; color:purple">OSRM-talk@openstreetmap.org</span></a><span style="font-size:9.0pt; font-family:"Helvetica",sans-serif"><br>
</span><a href="https://lists.openstreetmap.org/listinfo/osrm-talk" target="_blank"><span style="font-size:9.0pt; font-family:"Helvetica",sans-serif; color:purple">https://lists.openstreetmap.org/listinfo/osrm-talk</span></a></p>
</div>
</blockquote>
</div>
<p class="MsoNormal"> </p>
</div>
</div>
</div>
</div>
<p class="MsoNormal" style="margin-bottom:12.0pt"><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" target="_blank">https://lists.openstreetmap.org/listinfo/osrm-talk</a></p>
</blockquote>
</div>
<p class="MsoNormal"><br>
<br clear="all">
</p>
<div>
<p class="MsoNormal"> </p>
</div>
</div>
</div>
<p class="MsoNormal"><span class="hoenzb"><span style="color:#888888">-- </span></span></p>
<div>
<div>
<p class="MsoNormal"><span style="color:#888888">- Kerrick</span></p>
</div>
</div>
</div>
</blockquote>
</div>
<p class="MsoNormal"><br>
<br clear="all">
</p>
<div>
<p class="MsoNormal"> </p>
</div>
<p class="MsoNormal">-- </p>
<div>
<div>
<p class="MsoNormal">- Kerrick</p>
</div>
</div>
</div>
</div>
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.
</body>
</html>