Method and apparatus for use in navigational applications

• US 10,444,025 B2
• Filed: 06/16/2017
• Issued: 10/15/2019
• Est. Priority Date: 01/30/2013
• Status: Active Grant

• Current Assignee: HERE Global B.V. (Nokia Corporation)
• Original Assignee: HERE Global B.V. (Nokia Corporation)
• Inventors: Pfeifle, Martin
• Primary Examiner(s): Cheung, Mary
• Application Number:
  US15/625,126
• Publication Number:
  US 20170307389A1
• Time in Patent Office: 851 Days
• CPC Class Codes: G01C 21/26 specially adapted for navigation in a road network
• CPC Class Codes: G01C 21/32 Structuring or formatting of map data
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes
• CPC Class Codes: G01C 21/3461 Preferred or disfavoured areas, e.g. dangerous zones, toll or emission zones, intersections, manoeuvre types, segments such as motorways, toll roads, ferries
• CPC Class Codes: G06F 16/00 Information retrieval; Database structures therefor; File system structures therefor
• CPC Class Codes: G06F 16/40 of multimedia data, e.g. slideshows comprising image and additional audio data retrieval of still image data G06F16/50; retrieval of audio data G06F16/60; retrieval of video data G06F16/70

Abstract

A method comprising providing or receiving updated information, previous and said updated information associated with a geographic region, said previous information comprising information about one or more links usable for connecting to one or more links in a different geographic region, and said updated information comprising at least said previous information and new Information about one or more links for connecting to one or more links in said different geographic region.

Claims

1. A computer-implemented method for incrementally updating a geographic database comprising optimal routing information for a first geographic region and an adjacent second geographic region so that an optimal route between the first and second geographic regions can be found after updating optimal routing data for only the first geographic region, the method comprising:

updating optimal routing information associated with the first geographic region, said updated optimal routing information comprising at least new optimal routing information about one or more links in the first geographic region usable for optimally connecting to one or more links in the second geographic region and previous optimal routing information about one or more links in the first geographic region usable for optimally connecting to one or more links in the second geographic region,

wherein updating includes;

computing a rank for one or more of the links of the first geographic region usable for connecting to one or more links of the second geographic region;

determining for each of the one of more links whether the computed rank has a lower importance than a previous computed rank for said link; and

if so, retaining the previous computed higher importance rank as the rank for said link.

2. The method according to claim 1, further comprising:

providing the updated routing information to a navigation device.

3. The method according to claim 1, further comprising storing said updated optimal routing information for said first geographic region in association with map information for said first geographic region.

4. The method according to claim 1, wherein a computed rank has a lower importance than a previous computed rank if:

the computed rank corresponds to a lower-ranked link level than the previous computed rank;

or

the computed rank corresponds to a lower-ranked value in an edge flag vector.

5. The method according to claim 1, further comprising using said updated optimal routing information when determining a route between said first geographic region and said second region or between a first location in said first geographic region and a second location in said second region.

6. The method according to claim 1, wherein the new optimal routing information is about:

one or more new links that were not covered by the previous optimal routing information; and

/or

one or more links that were covered by the previous optimal routing information where said one or more links has changed.

7. The method according to claim 1, wherein said previous optimal routing information and said updated optimal routing information comprises edge flag information.

8. The method according to claim 1, wherein said previous optimal routing information and said updated optimal routing information comprises a vector indicating if said link is a desired path to a respective node of respective partitions of a region.

9. The method according to claim 8, wherein said previous optimal routing information comprises a previous vector and said updated optimal routing information comprises a updated vector, each value of said updated vector being one of the same or changed with respect to said previous vector to a value representing a higher ranking.

10. The method according to claim 1, wherein said previous optimal routing information and said updated optimal routing information comprises link hierarchy information.

11. The method according to claim 1, wherein each of said links has a link class associated therewith.

12. The method according to claim 1, wherein the new optimal routing information is about a newly built road link.

13. An apparatus comprising at least one processor and at least one non-transitory memory including computer program code, the at least one memory and the computer program code configured to, with the at least one processor, cause the apparatus at least to:

for a geographic database comprising optimal routing information for a first geographic region and an adjacent second geographic region, update optimal routing information associated with the first geographic region so that an optimal route between the first and second geographic regions can be found after updating optimal routing data for only the first geographic region,

said updated optimal routing information comprising at least new optimal routing information about one or more links in the first geographic region usable for optimally connecting to one or more links in the second geographic region and previous optimal routing information about one or more links in the first geographic region usable for optimally connecting to one or more links in the second geographic region; and

determine a route between said first geographic region and said second region or between a first location in said first geographic region and a second location in said second region using said updated optimal routing information.

14. The apparatus according to claim 13, wherein updating optimal routing information includes:

computing a rank for one or more of the links of the first geographic region usable for connecting to one or more links of the second geographic region;

determining for each of the one of more links whether the computed rank has a lower importance than a previous computed rank for said link; and

retaining the previous computed higher importance rank as the rank for said link in response to the computed rank having a lower importance than the previous computed rank for said link.

15. The apparatus according to claim 14, wherein a computed rank has a lower importance than a previous computed rank if the computed rank corresponds to a lower-ranked link level than the previous computed rank or the computed rank corresponds to a lower-ranked value in an edge flag vector.

16. The apparatus according to claim 13, wherein the apparatus is further caused to provide the updated routing information to a navigation device.

17. The apparatus according to claim 13, wherein said previous optimal routing information and said updated optimal routing information comprises link hierarchy information.

18. A computer program product comprising at least one non-transitory computer-readable storage medium having computer-executable program code portions stored therein, the computer-executable program code portions comprising program code instructions configured to:

update optimal routing information associated with a first geographic region including new optimal routing information regarding one or more links in the first geographic region usable for optimally connecting to one or more links in a second geographic region, and previous optimal routing information about one or more links in the geographic region usable for optimally connecting to one or more links in the second geographic region;

store said optimal routing information in a geographic database for the first geographic region and the second, adjacent geographic region; and

determine a route between said first geographic region and said second region or between a first location in said first geographic region and a second location in said second region using said updated optimal routing information.

19. The computer program product of claim 18, further comprising program code instructions configured to:

compute a rank for one or more of the links of the first geographic region usable for connecting to one or more links of the second geographic region;

determine for each of the one of more links whether the computed rank has a lower importance than a previous computed rank for said link; and

retain the previous computed higher importance rank as the rank for said link in response to the computed rank having a lower importance than the previous computed rank for said link.

20. The computer program product of claim 19, wherein a computed rank has a lower importance than a previous computed rank if the computed rank corresponds to a lower-ranked link level than the previous computed rank or the computed rank corresponds to a lower-ranked value in an edge flag vector.