<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Karina Goot on Medium]]></title>
        <description><![CDATA[Stories by Karina Goot on Medium]]></description>
        <link>https://medium.com/@thegootlife?source=rss-1de4137aa32------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*iy7a7vzTLTVRHbp2mQ-0Tw.png</url>
            <title>Stories by Karina Goot on Medium</title>
            <link>https://medium.com/@thegootlife?source=rss-1de4137aa32------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Wed, 18 Nov 2026 23:52:45 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@thegootlife/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Using Client-Side Map Data to Improve Real-Time Positioning]]></title>
            <link>https://eng.lyft.com/using-client-side-map-data-to-improve-real-time-positioning-a382585ac6e?source=rss-1de4137aa32------2</link>
            <guid isPermaLink="false">https://medium.com/p/a382585ac6e</guid>
            <category><![CDATA[marketplaces]]></category>
            <category><![CDATA[software-development]]></category>
            <category><![CDATA[lyft]]></category>
            <category><![CDATA[engineering]]></category>
            <category><![CDATA[mapping]]></category>
            <dc:creator><![CDATA[Karina Goot]]></dc:creator>
            <pubDate>Tue, 13 Jul 2021 17:14:20 GMT</pubDate>
            <atom:updated>2021-07-13T19:44:23.157Z</atom:updated>
            <content:encoded><![CDATA[<p>By <a href="https://www.linkedin.com/in/kgoot/">Karina Goot</a>, <a href="https://www.linkedin.com/in/tony-zhang-78249526/">Tony Zhang</a>, <a href="https://www.linkedin.com/in/burak-bostancioglu-94769523/">Burak Bostancioglu</a>, <a href="https://www.linkedin.com/in/bsudekum/">Bobby Sudekum</a>, <a href="https://www.linkedin.com/in/erik-kamp-07852361/">Erik Kamp</a></p><h4>Introduction</h4><p>GPS signals are notoriously noisy and unreliable (figure 1). One of the primary challenges for the Mapping team at Lyft is to translate the noisy GPS signal from our driver and rider devices into accurate location tracking on the map. This helps power rider and driver matching, dispatch decisions, accurate ETA predictions, and much more! We call this process map matching.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/758/1*MaBw9-Fs4F1y1qngCKf2KA.png" /><figcaption>Figure 1: example of noisy location data in a dense urban area and improvements after map matching</figcaption></figure><p>Map data helps the map matching process because it can reduce the space of locations to just the roads. For this reason, historically, we ran our map matching algorithms on the server-side to utilize the underlying map data.</p><p>For the past year, we have been building out an on-device localization system. Having localization capabilities on the client allows us to have more accurate sensor readings, reduce latency, localize drivers when they lose cell reception, and unlock new product use cases across the Lyft platform.</p><p>Unlike server-side localization systems, client localization is extremely constrained in both memory and latency requirements. As a result, we cannot efficiently utilize map data without impacting device memory (storing too much data will make the device run out of memory) or over-the-network cost (downloading maps while on cellular data is expensive).</p><p>These constraints drove us to design a system that supports map data in the client to unlock the location tracking accuracy gains of map data on-device without introducing unnecessary memory pressure.</p><h4>Why is map data useful to have on-client?</h4><p><strong>It helps improve navigation:</strong></p><ul><li>By understanding the road network and its features, we can improve our rerouting and off-route detection algorithms.</li><li>Cell network availability is not guaranteed. With map data available on-device, we can localize and reroute drivers when they are offline (for example, in tunnels or rural areas).</li></ul><p><strong>It helps improve location tracking:</strong></p><ul><li>Map matching on-device improves the freshness of localization models.</li><li>Moving high-cost computation from server to client simplifies server-side architecture, reduces hosting costs, and lowers server-to-client latency.</li><li>Direct access to high-frequency sensor data improves localization quality.</li></ul><p><strong>It helps build safety features for our drivers:</strong></p><ul><li>Notifying drivers of unauthorized drop-off/pick-up areas based on curb features.</li><li>Displaying speed limits.</li><li>Showing map elements like traffic lights and stop signs.</li></ul><h4>Designing the system</h4><p>We broke the project down into three main components.</p><ol><li>Lightweight map data generation</li><li>Client platform networking layer on iOS and Android</li><li>C++ core library</li></ol><p><strong>Lightweight map data generation</strong></p><p>In order to figure out the map data format, generation, and serving, we divided the entire LyftMap into small chunks of <em>S2Cells</em> built on top of the <a href="https://s2geometry.io/about/overview">S2Geometry</a> library. The basic unit of LyftMap data is a <em>MapElement</em> which stores two types of data:</p><ol><li>Road metadata to build a road network graph.</li><li>Segment sequences to infer turn restrictions and avoid illegal turns.</li></ol><p>Each <em>S2Cell</em> is a compilation of <em>MapElements</em> for a region, where each cell has a unique numeric id. We partitioned the map into cells that span roughly 1x1km sections (figure 2).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*-Yj2hTNT0VaZ8LGX" /><figcaption>Figure 2: S2 level 13 cells over the San Francisco region</figcaption></figure><p>When the client tries to download map data from the server, it will specify the <em>cell_id</em> + <em>map_version.</em> The server will return the map data serialized as <em>S2CellElements</em>.</p><p>We download the cells based on the current user location and dynamically build a road network graph in memory. With this design, we have a local graph built on the client providing the same core functionalities as a server-side graph.</p><p><strong>Client platform networking layer (iOS and Android)</strong></p><p>Next, we stood up a backend service, <em>MapAttributes</em>, that reads map elements data from DynamoDB based on an S2 geospatial index. <em>GetElementesByCellID</em> fetches serialized map elements from Dynamo, deserializes them, and filters on the requested element types. Finally, it converts them into <em>S2CellElements</em> objects to construct a response.</p><p>To improve reliability, reduce latency, and improve <em>MapAttributes</em> server hosting costs, we used a <a href="https://aws.amazon.com/cloudfront/">CloudFront CDN</a> to cache the MapAttributes response. CloudFront will return the results from the edge server on a cache hit without calling the <em>MapAttributes</em> service. On a cache miss, Cloudfront forwards the request to <em>MapAttributes</em> via <a href="https://www.envoyproxy.io/"><em>Envoy</em></a>, and the response gets cached for future requests.</p><p>To keep the memory footprint constant, we only load cells near the current location. To compensate for data loading latency, we keep a buffer of nearby cells to have enough map data around the current location. As illustrated in figure 4, we find the corresponding cell for a given raw location, <em>L</em>, and call it <em>S0</em>. Next, we fetch all the neighboring cells of <em>S0</em> and call them <em>S1</em>. Similarly, we compute the neighboring cells of <em>S1</em>s and call them <em>S2</em>. This way, for each location update, we generate 13 surrounding cells. As the user location changes, we recompute the list of cells.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*QoOcp6rHVwMFxPpy2tcvLw.png" /><figcaption>Figure 4: Computing level 0, 1, and 2 neighboring cells</figcaption></figure><p><strong>Core library functionality</strong></p><p>Once the client fetches the desired map cells from the server, it passes this information through an interface layer to a C++ localization library (figure 5).</p><p>We track the map data elements in a <em>MapDataManager</em> object, and after generating all 13 map data cells, we trigger a road network graph computation. This process happens async from the location updates that occur when new GPS readings come in from the device.</p><p>When the <em>MapDataManager</em> completes creating a <em>RoadNetworkGraph</em>, we pass a shared pointer to our <em>LocationTracker</em>, enabling the system to take advantage of various <a href="https://eng.lyft.com/a-new-real-time-map-matching-algorithm-at-lyft-da593ab7b006">Map-Based Models</a> for localization.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*LuZv35DG2GnjX9NJ" /><figcaption>Figure 5: High-level overview of the Localization Library</figcaption></figure><p>With this design, as the user moves around the physical world, we can dynamically generate new <em>RoadNetworkGraphs</em> of their surroundings and update our <em>LocationTracker</em> when the next graph object is ready (figure 6).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/288/1*X7jWQ-AIcm5hH4MdVnUifg.gif" /><figcaption>Figure 6: Prototype visualization of map data cells dynamically loading as user locations move</figcaption></figure><p>Lyft drivers generally operate in a single service area, and their locality is highly concentrated, so duplicate downloads of the same data are likely. Repeat downloads will lead to high over-the-network data usage for our drivers.</p><p>To solve this problem, we added an in-memory SQLite caching layer directly in C++. <a href="https://www.sqlite.org/index.html">SQLite</a> was our preferred database choice because of its simplicity and native support on client platforms.</p><p>This secondary cache allows us to store the unique highest locality data for each driver directly on-device. By persisting map data on disk, we can store data across sessions, so we only have to refresh the cache when the underlying map data changes.</p><p>Based on data analysis of driving patterns, we determined that with less than roughly 15MB of on-device data, we can achieve a high cache hit rate for the vast majority of Lyft Drivers (figure 7).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*qNj1CL0UZTxBtW6HmYWybg.png" /><figcaption>Figure 7: Driver cell usage stats</figcaption></figure><h4>Analyzing Results</h4><p>Once we finalized the initial prototypes and design plans, it was time to validate everything was working as expected.</p><p>We determined the best metric for success would be to track how often mobile clients have map data cells on-device. With the current release, we achieved map data availability metrics showing &gt;99% availability among drivers in the experiment group.</p><p>We also monitored the performance of the map data system to ensure it only uses a reasonable amount of computation power. In experimentation, we achieved sub 10ms latency for the p99 computation time of our map matching models.</p><p>Next, we investigated how client map data models affect quality. Figure 8 shows a local map simulation, where the blue dots represent raw locations roughly one second apart. The red dots reflect the map-snapped locations, centering over the road segment as expected.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/391/1*zBi6jfPLktmSS8JJBxVakA.png" /><figcaption>Figure 8: Raw and map matched locations</figcaption></figure><p>We also compared different localization strategies. In figure 9, we plotted <a href="https://en.wikipedia.org/wiki/Kalman_filter">Kalman filtered</a> locations in yellow against map-snapped locations in pink. Even with a basic snapping model without additional heuristics, the pink locations are a much better representation of where the driver is on the road.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*6iSKFiHPJmj1ikzi" /><figcaption>Figure 9: Kalman filtered locations and map snapped locations</figcaption></figure><p>Finally, we investigated the impact of the SQLite cache on the download rate of map data. In the chart in figure 10, we ranked drivers by the amount of over-the-network data they were downloading with and without the cache. Seeing the order of magnitude reduction in downloads helped us validate the database is working.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*zYEJ3wFrkFOIjln6" /><figcaption>Figure 10: Over the network download rate for users with and without the SQLite cache</figcaption></figure><h4>Conclusion</h4><p>The Map Data in the Client project is a foundational investment for our location tracking capabilities at Lyft. With this project complete, we managed to successfully download Lyft map data, build in-memory road network graphs, compute map matching models and ingest the locations back to the server — all in the mobile client!</p><p>Looking forward, we are excited to develop higher accuracy on-device localization models, implement offline routing and rerouting capabilities, and introduce new features that will make driver navigation and wayfinding in the physical world safer and more reliable.</p><h4>Acknowledgments</h4><p>Huge thanks to the entire Mapping Team at Lyft for helping shepherd this effort into production! Especially to Rex McArthur, Ben Low, and Phoenix Li for collaborating closely on the integration points.</p><p><em>As always, we are hiring! If you’re passionate about developing the future of mapping at Lyft, </em><a href="https://www.lyft.com/careers?gh_src=99e060d22us"><em>join our team</em></a><em>.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=a382585ac6e" width="1" height="1" alt=""><hr><p><a href="https://eng.lyft.com/using-client-side-map-data-to-improve-real-time-positioning-a382585ac6e">Using Client-Side Map Data to Improve Real-Time Positioning</a> was originally published in <a href="https://eng.lyft.com/">Lyft Engineering</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
    </channel>
</rss>