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
#3 (comment).