Incremental testing of a navigation database

• US 9,075,822 B2
• Filed: 02/11/2011
• Issued: 07/07/2015
• Est. Priority Date: 02/11/2011
• Status: Active Grant

• Current Assignee: HERE Global B.V. (HERE Holding Corporation)
• Original Assignee: HERE Global B.V. (HERE Holding Corporation)
• Inventors: Richter, Jan, Pfeifle, Martin
• Primary Examiner(s): Choi, Yuk Ting
• Application Number:
  US12/931,850
• Publication Number:
  US 20120209818A1
• Time in Patent Office: 1,607 Days
• Field of Search: 707/609, 707/999.102, 707/999.103
• US Class Current: 1/1
• CPC Class Codes: G01C 21/3859 Differential updating map data
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 16/29 Geographical information databases

Abstract

A navigation system utilizes a testing package tailor made for an incremental update to a map database. An incorrect incremental update may corrupt a navigation database. Testing an incrementally updated database after updating allows a corrupted database to be detected before the corrupted database is used by the map database system. Map tiles associated with a list of recompiled objects are used to populate a table. A test script is created from the list map tiles and, when executed, checks the validity of references in the map database associated with the map tiles. The test script generates a return value that indicates whether errors occurred, the type of the errors, the quantity of errors, or any combination thereof. The navigation system analyzes the errors and determines whether to finalize or roll back the update.

Claims

1. A method of testing an incrementally updated map database, the method comprising:

receiving a list of objects derived from an update for the map database;

populating a table with map tiles associated with the objects, wherein the table includes a first map tile and a second map tile that is adjacent to the first map tile;

generating a test script including a consistency check algorithm for the first map tile associated with one or more of the objects of the update and the second map tile associated with one or more of the objects of the update, wherein the consistency check algorithm is configured to determine whether references of the second map tile to all objects associated with the first map tile are valid and whether references of the first map tile to all objects associated with the second map tile are valid;

storing the test script in a memory;

executing the test script on the navigation database to generate a return value, wherein the memory stores a threshold value; and

finalizing the update package to the navigation database when the return value indicates errors less than the threshold value and roll back the update package when the return value indicates errors in excess of the threshold value.

2. The method of claim 1, wherein the test script includes a test command for each of the map tiles.

3. The method of claim 1, wherein the first map tile includes a tile identification value and tile data including nodes and segments.

4. The method of claim 1, wherein the test script is uniquely generated for the update.

5. The method of claim 1, further comprising:

sending the update and the test script to a navigation device, wherein the memory is located in a map developer server.

6. The method of claim 1, wherein the memory is located in a navigation device and the update is received from a map developer server.

7. The method of claim 1, wherein the test script comprises structured query language.

18. The method of claim 1, wherein a reference is valid when the reference points to an existing object in the map database, and the first map tile is considered valid when all references between the first map tile and other tiles of the map database are determined to be valid.

19. The method of claim 1, wherein the consistency check algorithm is further configured to determine an error type of a plurality of error types for the first map tile when the first map tile is found invalid.

20. The method of claim 19, wherein the error type is determined based on a comparison between a number of errors determined for the first map tile and a plurality of error type thresholds, each of the error type thresholds corresponding to a particular error type.

8. An apparatus for testing an incrementally updated map database, the apparatus comprising:

a memory configured to store a table populated with a first plurality of map tiles associated with an update package for updating the map database, wherein the plurality of map tiles includes a first map tile geographically adjacent to a second map tile; and

a controller configured to generate a test script including a consistency check algorithm for the first plurality of map tiles, wherein the consistency check algorithm determines whether references between the first map tile and objects in the map navigation database are valid, and wherein the consistency check algorithm is further configured to determine an error type of a plurality of error types for the first map tile when the first map tile is found invalid, and the error type is determined based on a comparison between a number of errors determined for the first map tile and a plurality of error type thresholds, each of the error type thresholds corresponding to a particular error type, and the controller is further configured to finalize the update package to the navigation database when the comparison indicates that the number of errors of the error types is less than the error type threshold value for the particular error types and roll back the update package when the number of errors of the error types is more than one of the particular error type threshold values.

9. The apparatus of claim 8, wherein the controller is a map developer controller and generates the update package associated with the list of recompiled objects.

10. The apparatus of claim 8, wherein the controller is a navigation device controller and derives the list of recompiled objects from the updated package received from the map developer.

11. The apparatus of claim 8, wherein the test script includes a test command for each of the map tiles.

12. The apparatus of claim 8, wherein the consistency check algorithm determines whether references in the map database to the at least one of the map tiles and from the at least one of the map tiles are valid.

13. The apparatus of claim 8, wherein the at least one map tile includes a tile identification value and tile data including nodes and segments.

14. The apparatus of claim 8, wherein the test script comprises structured query language.

15. The apparatus of claim 8, wherein the controller is configured to execute the test script on the map database to generate a return value.

16. The apparatus of claim 15, wherein the controller is configured to finalize the update package to the map database when the return value indicates no errors and revert to a previous version of the map database when the return value indicates one or more errors.

17. An apparatus for testing an incrementally updated navigation database, the apparatus comprising:

a memory configured to store a table populated with a first plurality of map tiles associated with an update package for updating the navigation database,

wherein the plurality of map tiles includes a first map tile geographically adjacent to a second map tile; and

a controller configured to generate a test script including a consistency check algorithm for the first plurality of map tiles,

wherein the consistency check algorithm determines whether all references between the first map tile and the second map tile are valid and whether all references to each of the first plurality of map tiles from any of a second plurality of map tiles are valid,

wherein the controller is configured to execute the test script on the navigation database to generate a return value of invalid references, wherein the memory stores a threshold value and the controller is configured to finalize the update package to the navigation database when the return value indicates errors less that the threshold value and configured to roll back the update package when the return value indicates errors in excess than the threshold value.