Probabilistic Reverse Geocoding

Abstract

The accuracy of a reverse geocode for a GPS fix in a mobile phone navigation device is improved significantly by considering together the user's last known location on an original route, the elapsed time between the last known location on the original route and the latest GPS fix, and the likelihood that the user could have traveled from the last known location on the original route to one of numerous candidate locations (generated from the reverse geocode) in the elapsed time. The navigation server relies only on a GPS fix, timestamps, and a back-end routing database to provide improved or superior accuracy of reverse geocoding a GPS fix (selection of a point on a road) when a relevant user has deviated from the intended route. The reverse geocoding allows for accurate and functional re-routing capabilities.

1 - 9 . (canceled) 
     
     
         10 . A method of improving a reverse geocode for a location fix in a mobile phone navigation device, comprising:
 obtaining a latest location of a mobile phone navigation device, together with a latest timestamp associated with said latest location;   obtaining a last known location on a navigated route displayed on said mobile phone navigation device, together with a last timestamp associated with said last known location on said navigated route;   measuring an elapsed time between said last timestamp and said latest timestamp;   comparing said elapsed time to a plurality of candidate locations generated by a reverse geocode in said elapsed time; and   re-routing said navigation route to include one of said plurality of candidate locations that has a predicted elapsed time of travel from said latest location to said one of said plurality of candidate locations closest to said elapsed time.   
     
     
         11 . The method of improving a reverse geocode for a location fix in a mobile phone navigation device according to  claim 10 , wherein:
 said latest location is determined by a global positioning satellite (GPS) system.   
     
     
         12 . The method of improving a reverse geocode for a location fix in a mobile phone navigation device according to  claim 10 , further comprising:
 providing a new navigation route from said latest location to said one of said plurality of candidate locations on said navigated route.   
     
     
         13 . The method of improving a reverse geocode for a location fix in a mobile phone navigation device according to  claim 10 , wherein:
 said latest location is off-route of said navigated route.   
     
     
         14 . The method of improving a reverse geocode for a location fix in a mobile phone navigation device according to  claim 10 , wherein:
 said wireless navigation device is a wireless phone.   
     
     
         15 . Apparatus for improving a reverse geocode for a location fix in a mobile phone navigation device, comprising:
 means for obtaining a latest location of a mobile phone navigation device, together with a latest timestamp associated with said latest location;   means for obtaining a last known location on a navigated route displayed on said mobile phone navigation device, together with a last timestamp associated with said last known location on said navigated route;   means for measuring an elapsed time between said last timestamp and said latest timestamp;   means for comparing said elapsed time to a plurality of candidate locations generated by a reverse geocode in said elapsed time; and   means for re-routing said navigation route to include one of said plurality of candidate locations that has a predicted elapsed time of travel from said latest location to said one of said plurality of candidate locations closest to said elapsed time.   
     
     
         16 . The apparatus for improving a reverse geocode for a location fix in a mobile phone navigation device according to  claim 15 , wherein:
 said means for obtaining said latest location obtains said latest location from a global positioning satellite (GPS) system.   
     
     
         17 . The apparatus for improving a reverse geocode for a location fix in a mobile phone navigation device according to  claim 15 , further comprising:
 means for providing a new navigation route from said latest location to said one of said plurality of candidate locations on said navigated route.   
     
     
         18 . The apparatus for improving a reverse geocode for a location fix in a mobile phone navigation device according to  claim 15 , wherein:
 said latest location is off-route of said navigated route.   
     
     
         19 . The apparatus for improving a reverse geocode for a location fix in a mobile phone navigation device according to  claim 15 , wherein:
 said wireless navigation device is a wireless phone.