Krumm John Faculty Summit 071607

Slide2: 

John Krumm Microsoft Research Redmond, WA

Slide3: 

55 GPS receivers 241 subjects 1.97 million points 106,000 miles 171,000 kilometers 13,845 trips Home addresses and demographic data Greater Seattle Seattle Downtown Close-up Garmin Geko 201 $115 10,000 point memory Median recording interval 6 seconds 63 meters

Slide4: 

Destination Modeling Predestination – Destination prediction Snap-to-Road – Map matching with temporal constraints Personalized Routes Location Privacy

Slide5: 

Destinations of drivers in our location survey John Krumm and Eric Horvitz, "Driver Destination Models",  Eleventh International Conference on User Modeling (UM 2007), June 25-27, 2007, Corfu, Greece.

Slide6: 

U.S. Geological Survey – Seattle Area What are the most attractive kinds of ground cover?

Slide8: 

Time of Day Day of Week

Slide9: 

Rate of Decline versus Demographics Single versus partner – no significant difference Children versus no children – no significant difference Extended family nearby versus not – no significant difference Gender – women decline faster than men Drivers reach steady state after about two weeks

Slide10: 

Destination Modeling Predestination – Destination prediction Snap-to-Road – Map matching with temporal constraints Personalized Routes Location Privacy

Slide11: 

John Krumm and Eric Horvitz, "Predestination: Inferring Destinations from Partial Trajectories", Eighth International Conference on Ubiquitous Computing (UbiComp 2006), September 2006.

Slide12: 

Anticipatory information Location-based advertising Hybrid vehicle efficiency

Slide13: 

Greater Seattle, ~ 40 km X 40 km 1 km grid

Slide14: 

Ground Cover Prior U.S. Geological Survey – Seattle Area

Slide15: 

All Possible Destinations Destinations of One Subject

Slide16: 

Personal destinations = visited cells + clustering + sparkling

Slide17: 

start Current Location Candidate Destination R r Δt

Slide18: 

From 2001 U.S. National Household Transportation Survey

Slide19: 

Efficient driving likelihood: Trip time likelihood: Open-world prior: Final probability: Closed-world prior: Wedding cakes: Ground cover:

Slide20: 

Half of trips (3667) for training efficiency distributions Remaining half for testing Leave-one-out for personal destinations prior

Slide21: 

Destination Modeling Predestination – Destination prediction Snap-to-Road – Map matching with temporal constraints Personalized Routes Location Privacy

Slide22: 

Congestion Pricing Location Based Services Pay As You Drive (PAYD) Insurance Collaborative Traffic Probes (DASH) Research (London OpenStreetMap) John Krumm, "Inference Attacks on Location Tracks", Fifth International Conference on Pervasive Computing (Pervasive 2007), May 13-16, 2007, Toronto, Ontario, Canada.

Slide24: 

Last Destination – median of last destination before 3 a.m. Median error = 60.7 meters

Slide25: 

Weighted Median – median of all points, weighted by time spent at point (no trip segmentation required) Median error = 66.6 meters

Slide26: 

Largest Cluster – cluster points, take median of cluster with most points Median error = 66.6 meters

Slide27: 

Best Time – location at time with maximum probability of being home Median error = 2390.2 meters (!)

Slide28: 

GPS interval – 6 seconds and 63 meters GPS satellite acquisition – ≈45 seconds on cold start, time to drive 300 meters at 15 mph Covered parking – no GPS signal Distant parking – far from home Covered Parking Distant Parking

Slide29: 

Windows Live Search reverse white pages lookup (free API at http://dev.live.com/livesearch/)

Slide30: 

MapPoint Web Service reverse geocoding Windows Live Search reverse white pages

Slide31: 

Original σ= 50 meters noise added Effect of added noise on address-finding rate

Slide32: 

Original Snap to 50 meter grid Effect of discretization on address-finding rate

Slide33: 

Pick a random circle center within “r” meters of home Delete all points in circle with radius “R”

Slide34: 

© 2007 Microsoft Corporation. All rights reserved. Microsoft, Windows, Windows Vista and other product names are or may be registered trademarks and/or trademarks in the U.S. and/or other countries. The information herein is for informational purposes only and represents the current view of Microsoft Corporation as of the date of this presentation. Because Microsoft must respond to changing market conditions, it should not be interpreted to be a commitment on the part of Microsoft, and Microsoft cannot guarantee the accuracy of any information provided after the date of this presentation. MICROSOFT MAKES NO WARRANTIES, EXPRESS, IMPLIED OR STATUTORY, AS TO THE INFORMATION IN THIS PRESENTATION.