Technique for structuring navigation data

• US 9,507,808 B2
• Filed: 11/06/2012
• Issued: 11/29/2016
• Est. Priority Date: 11/07/2011
• Status: Active Grant

• Current Assignee: Elektrobit Automotive GmbH (Continental AG)
• Original Assignee: Elektrobit Automotive GmbH (Continental AG)
• Inventors: Fischer, Sebastian, Dormann, Holger
• Primary Examiner(s): Chaki, Kakali
• Assistant Examiner(s): Wu, Fuming
• Application Number:
  US13/669,591
• Publication Number:
  US 20130117322A1
• Time in Patent Office: 1,484 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G01C 21/3815 Road data
• CPC Class Codes: G01C 21/3878 Hierarchical structures, e.g. layering
• CPC Class Codes: G01C 21/3881 Tile-based structures
• CPC Class Codes: G06F 16/21 Design, administration or maintenance of databases
• CPC Class Codes: G06N 5/01 Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound

Abstract

A technique for structuring a navigation data base in order to support incremental data updates is provided. A method implementation of the technique includes the steps of providing at least two data levels, wherein a first data level is associated with route links representing road segments of regional distance roads, partitioning the first data level into local tiles, wherein each local tile is associated with route links representing road segments of regional distance roads for a specific local geographic area, and interlinking those route links of neighboring local tiles that represent road segment portions of a regional distance road extending over neighboring local tiles.

Claims

1. A method of structuring navigation database content for supporting incremental data updates, comprising:

providing at least two data levels, wherein a first data level is associated with route links representing road segments of regional distance roads;

partitioning the first data level into local tiles, wherein each local tile is associated with route links representing road segments of regional distance roads associated with a specific local geographic area, wherein route links representing road segments extending over more than one local tile are split up into distinct route links representing road segment portions corresponding to the extending road segments within the corresponding local tiles; and

establishing an interlinking between related split up route links of neighboring local tiles by organizing split up route links of each local tile in at least one special routing cluster, wherein the at least one special routing cluster comprises split up route links being organized in a route link table with fixed route link order and each being associated with a permanent identifier, and by referencing from a split up route link of a local tile to corresponding split up route links of neighboring local tiles using their permanent identifiers.

2. The method according to claim 1, wherein a second data level of the at least two data levels is associated with route links representing far distance road segments.

3. The method according to claim 2, wherein the route links within the second data level are organized independent of the local tile structure in the first data level.

4. The method according to claim 1, wherein the partitioning step further comprises:

providing the distinct route links with route link data for representing road segment portions of regional distance roads extending over neighboring tiles; and

assigning the distinct route links together with route link data to the corresponding local tiles.

5. The method according to claim 1, wherein providing an interlinking between route links of neighboring local tiles comprises:

providing each local tile with tile knots and tile knot identifiers;

assigning related split up route links of neighboring local tiles to be interlinked to tile knots of the neighboring tiles having the same identifier; and

providing each local tile with a tile knot identifier table representing an assignment between knots and split up links of the local tile.

6. The method according to claim 1, further comprising organizing route links representing road segments within each local tile into one or more routing clusters.

7. The method according to claim 1, further comprising providing an interlinking between route links associated with the at least two data levels by providing each data level with level knots and level knot identifiers.

8. The method according to claim 7, further comprising providing each local tile of the first data level with at least one first identifier table representing an assignment between route links of the local tiles to be interlinked with corresponding route links of the second data level and the corresponding level knots as well as providing the second data level with at least one second identifier table representing an assignment between the corresponding route links of the second data level to be interlinked with route links of the first data level and the corresponding level knots.

9. The method according to claim 1, wherein the database content further comprises at least one of basic map display data, destination entry data, Point Of Interest (POI) data, Traffic Message Channel (TMC) data and further enhanced navigation data.

10. The method according to claim 9, wherein the destination entry data of the navigation database are organized in accordance with the at least two data levels, wherein Local Destination Entry (LDE) data are associated with the first data level and Global Destination Entry (GDE) data are associated with the second data level.

11. The method according to claim 10, wherein GDE data comprise destination entry indices for far distance roads and cities or city parts and wherein LDE data comprise destination entry indices for regional distance roads.

12. The method according to claim 11, further comprising partitioning the destination entry indices associated with regional distance roads in accordance with the local tiles.

13. The method according to claim 1, wherein each local tile has a predefined size and wherein each local tile is further provided with a unique tile identifier.

14. The method according to claim 13, wherein routing clusters of a local tile are further assigned to the corresponding tile identifier.

15. The method according to claim 1, wherein each local tile is further provided with tile version data.

16. A method of incrementally updating a navigation database of a navigation device, the navigation database being structured in accordance with claim 1, and wherein the updating is performed by a navigation data server, comprising:

receiving an update request from the navigation device; and

providing the navigation device with updated navigation data on a local tile basis.

17. The method according to claim 16, wherein the update request comprises information about current navigation data version in the navigation database, and further comprising:

comparing the received information with navigation data versions available on the navigation data server; and

depending on a result of the comparison, providing the updated navigation data.

18. The method according to claim 16, wherein the updated navigation data may at least comprise one of updated routing data for at least one tile to be updated and updated interlinking data.

19. The method according to claim 16, wherein each local tile of the first data level is individually updatable by replacing at least one of navigation data, interlinking data and tile version data associated with the corresponding local tile during an incremental update procedure.

20. The method according to claim 16, wherein the first data level and second data level are independently updatable from each other or wherein the second data level is updatable together with the first data level by replacing the whole navigation data associated with the second data level.

21. A computer program product comprising a non-transitory computer-readable recording medium with program code for carrying out the method according to claim 1 when the computer program product is executed on a computer device.

22. A memory device including a navigation database structured in accordance with claim 1.

23. A navigation device comprising the memory device including the navigation database of claim 22.

24. A method for incrementally updating a navigation database of a navigation device, wherein the navigation database is structured in accordance with claim 1, the method comprising:

updating navigation data comprising at least updated routing data for at least one local tile of the first data level; and

updating interlinking data for the at least one local tile to be updated to ensure connectivity between the at least one updated local tile and the remaining unchanged navigation data of the navigation database.

25. The method according to claim 24, wherein the updated navigation data further comprises at least one of destination entry data, basic map display data, POI data and other enhanced navigation data for at least one local tile of the first data level.

26. The method according to claim 24, wherein the updated interlinking data comprise at least one permanent identifier table at least including an assignment between tile route links of the first data level to be interlinked with route links of the second data level and corresponding tile knots.

27. The method according to claim 24, further comprising updated tile version data.

28. The method according to claim 24, further comprising updated navigation data and interlinking data in form of a permanent identifier table for the second data level.