TECHNIQUE FOR STRUCTURING NAVIGATION DATA

• US 20130117322A1
• Filed: 11/06/2012
• Published: 05/09/2013
• 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
• Granted Patent: US 9,507,808 B2
• Time in Patent Office: Days
• US Class Current: 707/792
• 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; and

establishing an interlinking between route links of neighboring local tiles that represent a road segment of a regional distance road extending over corresponding neighboring local tiles.

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 comprises:

splitting route links representing road segments extending over at least more than one local tile up into distinct route links;

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 establishing an interlinking between route links of neighboring local tiles comprises:

organizing route links representing road segments extending over neighboring tiles into special routing clusters, and providing each route link therein with a permanent identifier.

6. 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 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 tile.

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

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

9. The method according to claim 8, 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.

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

11. The method according to claim 10, 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.

12. The method according to claim 11, 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.

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

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

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

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

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

18. The method according to claim 17, 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.

19. The method according to claim 17, 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.

20. The method according to claim 17, 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.

21. The method according to claim 17, 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.

22. A computer program product with program code for carrying out the method according to claim 1 when the computer program product is executed on a computer device.

23. The computer program product of claim 22, which is stored on a computer-readable recording medium.

24. A navigation database structured in accordance with claim 1.

25. A navigation device comprising the navigation database of claim 24.

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

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

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

27. The data signal according to claim 26, 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.

28. The data signal according to claim 26, 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.

29. The data signal according to claim 26, further comprising updated tile version data.

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