Method of using map data that has been organized for affinity relationships

• US 8,117,041 B1
• Filed: 06/23/2006
• Issued: 02/14/2012
• Est. Priority Date: 03/03/2005
• Status: Active Grant

• Current Assignee: HERE Global B.V. (Nokia Corporation)
• Original Assignee: Navteq B.V.
• Inventors: Khan, M. Salahuddin, Herbst, James
• Primary Examiner(s): OUELLETTE, JONATHAN P
• Application Number:
  US11/473,800
• Time in Patent Office: 2,062 Days
• Field of Search: 705/1.1
• US Class Current: 705/1.1
• CPC Class Codes: G01C 21/3617 using user history, behaviour, conditions or preferences, e.g. predicted or inferred from previous use or current movement

Abstract

A method is disclosed for providing guidance to a destination with a computing system that uses geographic data indexed by affinity relationships. A user specifies a municipality of relatively greater importance that is located nearby the desired actual destination. The computing system provides guidance to the user to follow a route to the specified municipality. While the user is following the route to the specified municipality, additional routes are calculated to each of a plurality of roads that cross into an affinity domain associated with the specified municipality. Before the user reaches the point at which any of the additional routes diverge from the route to the specified municipality, input is obtained from the user, one or more times as needed, specifying either another municipality progressively closer to the desired actual destination or the actual desired destination. Guidance is provided to the user to follow the routes to the closer municipalities or the desired actual destination.

Claims

1. A computer-implemented method of providing guidance to a destination with a computing system comprising:

receiving input from a user that indicates a municipality that is nearby a desired actual destination;

calculating, via the computing system, a first route to the municipality that is nearby the desired actual destination;

providing guidance to the user to follow the first route to the municipality that is nearby the desired actual destination;

determining additional routes to each of a plurality of roads that cross a boundary into an affinity domain associated with the municipality that is nearby the desired actual destination;

while on route to the municipality that is nearby the desired actual destination and prior to reaching the point along the first route at which any of the additional routes diverge from the route to the municipality that is nearby the desired actual destination, receiving input from the user that indicates an exact location of the desired actual destination;

calculating a second route to the desired actual destination; and

providing guidance to the user to follow the second route to the desired actual destination.

2. The method of claim 1 further comprising:

after the step of determining additional routes, determining a point along the first route at which any of the additional routes diverge.

3. The method of claim 1 wherein the plurality of roads include all roads that cross the boundary into the affinity domain associated with the municipality that is nearby the desired municipality.

4. The method of claim 1 wherein the plurality of roads include only roads of a highest functional class into the affinity domain associated with the municipality that is nearby the desired municipality.

5. The method of claim 1 further comprising:

after the step of determining additional routes, determining a leading point that is located a given distance in advance of the point along the first route at which any of the additional routes diverge, and

wherein the input from the user that indicates the exact location of the desired actual destination is obtained in response to an inquiry to the user provided at the leading point.

6. The method of claim 1 wherein the affinity domain of a municipality defines a set of values that diminishes as a function of the distance from a location associated with an importance value determined for the municipality.

7. The method of claim 1 further comprising:

before calculating the first route to the municipality that is nearby the desired actual destination, using an affinity relationship index that relates municipalities to other municipalities based on importance of the other municipalities.

8. The method of claim 1, wherein the step of determining additional routes is performed as a background process.

9. The method of claim 1, wherein the step of determining additional routes is performed using pre-calculated routes.

10. The method of claim 1, wherein the step of determining additional routes is performed while providing guidance to the user to follow the first route to the municipality that is nearby the desired actual destination.

11. The method of claim 1, wherein the step of determining additional routes is performed while determining a current position of the user.

12. A computer-implemented method of providing guidance to a destination with a computing system comprising:

(i) receiving input from a user that indicates a first municipality that is nearby a desired actual destination;

(ii) calculating, via the computing system, a first route to the first municipality that is nearby the desired actual destination;

(iii) providing guidance to the user to follow the first route to the first municipality that is nearby the desired actual destination;

(iv) determining additional routes to each of a plurality of roads that cross a boundary into an affinity domain associated with the first municipality that is nearby the desired municipality;

(v) while on route to the municipality that is nearby the desired actual destination and prior to reaching the point along the first route at which any of the additional routes diverge, performing steps (i)-(iv) one or more times for additional municipalities that are progressively closer to the desired actual destination;

(vi) while on route to one of the municipalities that is nearby the desired actual destination and prior to reaching the point along the first route at which any of the additional routes diverge, receiving input from the user that indicates an exact location of the desired actual destination;

(vii) calculating a second route to the desired actual destination; and

(viii) providing guidance to the user to follow the second route to the desired actual destination.

13. The method of claim 12 further comprising:

after the step of determining additional routes, determining a point along the first route at which any of the additional routes diverge.

14. The method of claim 12 wherein the plurality of roads include all roads that cross the boundary into the affinity domain associated with the municipality that is nearby the desired municipality.

15. The method of claim 12 wherein the plurality of roads include only roads of a highest functional class into the affinity domain associated with the municipality that is nearby the desired municipality.

16. The method of claim 12 further comprising:

after the step of determining additional routes, determining a leading point that is located a given distance in advance of the point along the first route at which any of the additional routes diverge, and

wherein the input from the user that indicates the exact location of the desired actual destination is obtained in response to an inquiry to the user provided at the leading point.

17. The method of claim 12 wherein the affinity domain of a municipality defines a set of values that diminishes as a function of the distance from a location associated with an importance value determined for the municipality.

18. The method of claim 12 further comprising:

before calculating the first route to the municipality that is nearby the desired actual destination, using an affinity relationship index that relates municipalities to other municipalities based on importance of the other municipalities.

19. The method of claim 12, wherein the step of determining additional routes is performed as a background process.

20. The method of claim 12, wherein the step of determining additional routes is performed using pre-calculated routes.

21. The method of claim 12, wherein the step of determining additional routes is performed while providing guidance to the user to follow the first route to the municipality that is nearby the desired actual destination.

22. The method of claim 12, wherein the step of determining additional routes is performed while determining a current position of the user.