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

• US 7,805,317 B2
• Filed: 03/03/2005
• Issued: 09/28/2010
• Est. Priority Date: 03/03/2005
• Status: Expired due to Fees

• Current Assignee: Navteq B.V.
• Original Assignee: Navteq North America LLC (Nokia Corporation)
• Inventors: Friederich, Matthew, Khan, M. Salahuddin
• Primary Examiner(s): OUELLETTE, JONATHAN P
• Application Number:
  US11/072,877
• Publication Number:
  US 20060200359A1
• Time in Patent Office: 2,035 Days
• Field of Search: 705/1, 705/1.1
• US Class Current: 705/1.1
• 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 providing guidance to a destination with a computing system, the method 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, prompting the user to enter data that indicates an exact location of the desired actual destination;

receiving input from the user that indicates the 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:

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.

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

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

5. The method of claim 1 wherein the step of promoting the user to enter data that indicates the exact location of the desired actual destination occurs when the user has reached a predetermined threshold along the mute.

6. A method of specifying a destination with a navigation system, the method comprising the steps of:

indicating a municipality via the navigation system, the municipality being near an actual desired destination;

receiving guidance for traveling to the municipality;

when reaching a predetermined threshold while on route to the municipality, receiving a request to indicate an exact address of the actual desired destination via the navigation system;

indicating the exact address of the actual desired destination; and

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

7. A computer-readable medium including computer-executable instructions for performing a method of providing guidance to a destination via a navigation system, the method comprising:

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

using the received input to search an index of the navigation system, the index including a hierarchically layered data structure of an affinity relationship between municipalities, wherein the affinity relationship corresponds to an affinity domain of the municipality that defines a set of data values that diminish as a function of a distance from a maximum importance value of the municipality;

calculating a first route to the municipality that is nearby the desired actual destination based on the search;

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.

8. The method of claim 7 wherein the desired actual destination being nearby the municipality comprises the desired actual destination being within the affinity domain of the municipality.

9. The method of claim 7 wherein the maximum importance value is associated with a centroid of a polygon representing an administrative boundary of the municipality.

10. The method of claim 7 wherein data corresponding to the desired actual destination is stored at a same index level of the index as data corresponding to the municipality if an importance value of the desired actual destination exceeds a respective value of the affinity domain of the municipality.

11. The method of claim 7 wherein data corresponding to the desired actual destination is stored at a different index level of the index than data corresponding to the municipality if an importance value of the desired actual destination does not exceed a respective value of the affinity domain of the municipality.

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

13. The method of claim 7 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 the exact location of the desired actual destination, requesting the user to indicate the exact location of the desired actual destination.