Transcript CrowdAltas
CrowdAtlas: Self-Updating
Maps
for Cloud and Personal Use
Mike Lin
Authors
Yin Wang
I earned my B.S. and M.S. degrees at the
Shanghai Jiao Tong University in 2000 and
2003, respectively, both in control theory.
During 2003-2008, I worked with Stéphane
Lafortune at the University of Michigan for
my Ph.D degree in EECS. HP Labs was
my first job after graduation. Since May
2013, I am affliated with Facebook.
Authors
George Forman
I am a computer science researcher in the
Data Mining and Machine Learning group
at Hewlett-Packard Laboratories. I work
on techniques for automated classification,
e.g. technology that learns to categorize
documents into a topic hierarchy based on
a small number of training examples given
by humans, or to recognize computer
systems that are likely to fail based on their
past failures. Repeatedly I find that
applying such technologies to real-world
business problems often leads to fixable
robustness issues & opportunities for
substantial performance
improvement. Hence, HP Labs is an
excellent place for technology research as
well as business impact.
Introduction
i.
ii.
iii.
iv.
Aggregates exceptional traces from users
Not conform to the open street map
Automatically update the map
Computer-generated roads
inaccurate maps:
A British insurance survey found that car accidents caused by or related
to digital maps.
Introduction
Introduction
Introduction
Contribution
i. An automatic map update system
ii. Map inference with navigation
iii. Contributing 61 km of roads for the beijing map on
OSM.
CrowdAtlas Service
8 days of data from 70 taxis in Beijing, with a sampling interval of 10 seconds.
CrowdAtlas Service
Extracting unmatched segments (red) after map matching seconds.
CrowdAtlas Service
With one week of data and a threshold of four sub-traces,
there are three clusters in the area
CrowdAtlas Service
With one week of data and a threshold of four sub-traces,
there are three clusters in the area with aerial image
MAP MATCHING
1. Within the error radius
2. Candidate sets ex: {x00, x10}
3. Likely drive path with observing sequence
Extracting Unmatched
Segments
Type I mismatch:
Out of the error radius
When a sample’s error radius of 50m does not intersect any road.
Type II mismatch:
Accidental long trajectories will be eliminated
The maximum travel speed to 180 km/h;
therefore, any consecutive samples matched to locations beyond 50t meters from
each other are considered a mismatch, where t is the sampling interval.
New Road Inference
i. Trace clustering by Hausdorff distance:
The distance between two trajectories
ii. Centerline fitting:
exceeds threshold
generates a polyline to minimize its mean square error to the
samples.
iii. Connection:
connect with intersections
iv. Iteration:
Re-match and re-cluster
New Road Inference
New Road Inference
i. Road attributes:
Give directions of roads
ii. Standalone mode:
User-selected type of roads(drive,cycling,walking)
Challenges and Limitations
IMPLEMENTATION
PERFORMANCE
PERFORMANCE
PERFORMANCE
CONTRIBUTION
CENTERLINE OFFSET
COMMENT
DATA COLLECTION
RELIABLITY CHECK