Method of organizing map data for affinity relationships and application for use thereof

• US 20060200359A1
• Filed: 03/03/2005
• Published: 09/07/2006
• Est. Priority Date: 03/03/2005
• Status: Active Grant

• Current Assignee: Navteq B.V.
• Original Assignee: Navteq North America LLC (Nokia Corporation)
• Inventors: Khan, M. Salahuddin, Friederich, Matthew
• Granted Patent: US 7,805,317 B2
• Time in Patent Office: Days
• US Class Current: 701/201
• CPC Class Codes: G01C 21/3605 Destination input or retrieval
• CPC Class Codes: G01C 21/3878 Hierarchical structures, e.g. layering

Abstract

An affinity relationship index and a method for using it are disclosed. The affinity relationship index captures, for any given place name, an affinity to one or more potentially more important place names. Each such more important place subtends an affinity domain within which other places are deemed to lie. The index carries this on hierarchically and has the effect of creating a relatively meaningful and minimized structure that can be rapidly searched for a user'"'"'s intended destination. An application uses these affinity domains to determine the instructions necessary to embark upon a guided journey rather than determining all instructions needed to complete the journey.

Claims

1. A method of organizing an index of municipalities comprising:

forming a hierarchically layered data structure that includes a first set of municipalities, and

for each municipality in the first set of municipalities, indicating one or more other municipalities as having an affinity relationship for the municipality in the first set of municipalities,

wherein a municipality is determined to have an affinity relationship with the municipality in the first set of municipalities if the municipality is within an affinity domain of the municipality in the first set of municipalities.

2. 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 the municipality.

3. 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 the centroid of the polygon formed by the administrative boundary of the municipality.

4. 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.

5. The method of claim 4 wherein the importance value of a municipality is determined by the formula

I=AP^α

×

BN^β

×

CK^γ

×

DR^δ

,

where, P is the population within a polygon corresponding to an administrative boundary of the municipality, N is the number of road intersections in the polygon, K is the number of kilometers of roads contained within the polygon, and R is the number of road crossings of a boundary of the polygon.

6. The method of claim 5 wherein A, B, C, and D and α

, β

, γ

, and δ

are tuning variables that are used to adjust the value of the importance index, I.

7. The method of claim 1 wherein the affinity domain of a municipality defines a set of values that diminishes exponentially as a function of the distance from the municipality.

8. The method of claim 1 wherein the index is part of a geographic database.

9. The method of claim 1 wherein the index is used to find destinations.

10. The method of claim 1 wherein the index is part of a navigation system.

11. A 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 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;

while on 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.

12. The method of claim 11 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.

13. The method of claim 11 wherein the first route has a destination a location associated with the municipality that is nearby the desired actual destination.

14. The method of claim 11 wherein the first route has a destination a centroid of a polygon that corresponds to an administrative boundary of the municipality that is nearby the desired actual destination.

15. The method of claim 11 further comprising:

prior to receiving input from the user that indicates the municipality that is nearby the desired actual destination, providing the user with an option to specify the desired destination exactly or by indicating a nearby municipality.

16. The method of claim 11 further comprising:

while on route to the municipality that is nearby the desired actual destination and prior to receiving input from the user that indicates an exact location of the desired actual destination, requesting the user to indicate the exact location of the desired actual destination.

17. The method of claim 16 wherein the step of requesting the user to indicate the exact location of the desired actual destination occurs when the user has reached a predetermined threshold along the route.

18. The method of claim 11 further comprising:

while on route to the municipality that is nearby the desired actual destination and prior to receiving input from the user that indicates an exact location of the desired actual destination, providing the user with an option to indicate the exact location of the desired actual destination or another municipality that is nearby the desired actual destination.

19. A method of specifying a destination with a system comprising the steps of:

indicating a municipality that an actual desired destination is near;

receiving guidance for traveling to the municipality;

while on route to the municipality, indicating an exact address of the actual desired destination; and

receiving guidance for traveling to the exact address of the actual desired destination.

20. The method of claim 19 further comprising:

prior to indicating the municipality that the actual desired destination is near, receiving an option to select a destination exactly or by selecting a nearby municipality.