Detecting and Storing Map Dust from GPS data

[kpwebb]

How do we create Map Dust? (http://www.mapdust.com/)

• Clear opportunities for producing an automated side-stream of OSM improvements (missing links, incorrect directional/turn restrictions, etc.) from probe data sources.
• How do we collect GPS data (different from GPS-derived traffic data) that protects privacy and makes data sharable with OSM community?
• Can we make this an opt-in feature of Traffic Engine?
• Where does this data live? Obviously different from traffic data but is it conceptually related enough to make part of the same project?

[sbma44]

A couple of things:

• @aaronlidman has put a ton of work into to-fix, the tasking interface we use with our own data teams. At the moment most of its input errors come from KeepRight or OSMium, but this is the interface we'll be growing.
• I need to give both of these papers a more thorough read (I've really just skimmed), but these are the first things I came across when I started researching GPS trace anonymization. In both cases the data is quantized into a fixed set of locations which a trace visits in a particular order. If I understand them correctly, one approach then prunes the tree of uncommonly-visited nodes until a desired level of k-anonymity is achieved. In the other, a Markovian operation is used to generate statistically representative paths without revealing any exact source data. Curious to hear other approaches, this is all pretty new to me.
  • http://www.tdp.cat/issues/tdp.a020a09.pdf
  • http://ceur-ws.org/Vol-397/paper4.pdf

[kpwebb]

Just to add more references to potential methods for generative map creation from GPS data (putting aside privacy concerns):

From GPS Traces to a Routable Road Map

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.147.7247&rep=rep1&type=pdf This paper presents a method for automatically converting raw GPS traces from everyday vehicles into a routable road network. The method begins by smoothing raw GPS traces using a novel aggregation technique. This technique pulls together traces that belong on the same road in response to simulated potential energy wells created around each trace. After the traces are moved in response to the potential fields, they tend to coalesce into smooth paths. To help adjust the parameters of the constituent potential fields, we present a theoretical analysis of the behavior of our algorithm on a few different road configurations. With the resulting smooth traces, we apply a custom clustering algorithm to create a graph of nodes and edges representing the road network. We show how this network can be used to plan reasonable driving routes, much like consumer-oriented mapping Web sites. We demonstrate our algorithms using real GPS data collected on public roads, and we evaluate the effectiveness of our approach by comparing the route planning results suggested by our generated graph to a commercial route planner.

Inferring Road Maps from Global Positioning System Traces

http://www.cs.uic.edu/~jakob/papers/biagioni-trr12.pdf As a result of the availability of Global Positioning System (GPS) sensors in a variety of everyday devices, GPS trace data are becoming increasingly abundant. One potential use of this wealth of data is to infer and update the geometry and connectivity of road maps through the use of what are known as map generation or map inference algorithms. These algorithms offer a tremendous advantage when no existing road map data are present. Instead of the expense of a complete road survey, GPS trace data can be used to generate entirely new sections of the road map at a fraction of the cost. In cases of existing maps, road map inference may not only help to increase the accuracy of available road maps but may also help to detect new road construction and to make dynamic adaptions to road closures—useful features for in-car navigation with digital road maps. In past research, proposed algorithms had been evaluated qualitatively with little or no comparison with prior work. This lack of quantitative and comparative evaluation is addressed in this paper with the following contributions: (a) a comprehensive survey of the current literature on map generation; (b) a description of the first method for the automatic evaluation of generated maps; (c) a qualitative, quantitative, and comparative evaluation of three reference algorithms; and (d) an open source implementation of each of the three algorithms, with a 118-h trace data set and ground truth map for unrestricted use by the automatic map generation community

[bmander]

I like the idea of generating a set of MapRoulette tasks for review by humans, instead of using a bot to make edits. That way you don't have to worry so much about the accuracy of your GPS-to-way algorithm.

[sbma44]

This is the general approach we've been taking with to-fix, FWIW:

http://osmlab.github.io/to-fix/?error=deadendoneway

[bmander]

I've been impressed at the speed with which possible corrections get reviewed on Maproulette. It seems well impedance matched for rate at which the Traffic Engine would produce map dust.

(from my phone) On Mar 2, 2015 5:49 PM, "Tom Lee" [email protected] wrote:

This is the general approach we've been taking with to-fix, FWIW:

http://osmlab.github.io/to-fix/?error=deadendoneway

— Reply to this email directly or view it on GitHub https://github.com/maptrace/architecture/issues/3#issuecomment-76871262.