Iterative logical renewal of navigable map database

• US 20050049783A1
• Filed: 08/29/2003
• Published: 03/03/2005
• Est. Priority Date: 08/29/2003
• Status: Active Grant

• Current Assignee: DENSO Corporation
• Original Assignee: DENSO Corporation
• Inventors: Hunzinger, Jason F.
• Granted Patent: US 7,079,946 B2
• Time in Patent Office: Days
• US Class Current: 701/208
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

An improved method is provided for identifying road sections in a navigation database. The method includes: receiving a database update identifying at least one road intersection; constructing a logical representation of the road topology surrounding the at least one road intersection; and identifying the at least one road intersection in the navigation database by comparing the logical representation to a logical representation of the navigation database.

Claims

1. A method for identifying road sections in a navigation database, comprising:

receiving a database update identifying at least one road intersection;

constructing a logical representation of the road topology surrounding the at least one road intersection; and

identifying the at least one road intersection in the navigation database by comparing the logical representation to a logical representation of the navigation database.

2. The method of claim 1 wherein the step of constructing a logical representation further comprises building a graph representing the road topology in the vicinity of the at least one road intersection, where nodes of the graph represent road intersections and links of the graph represent road segments.

3. The method of claim 1 wherein the database update further includes an attribute associated with the at least one road intersection, and using the attribute to identify the at least one road intersection in the navigation database.

4. The method of claim 1 wherein the database update further identifies at least one road segment having an attribute, and using the attribute of the at least one road segment to identify the at least one road intersection in the navigation database.

5. The method of claim 1 wherein the step of constructing a logical representation further comprises building a tree graph to represent the road topology surrounding the at least one road intersection, where nodes of the tree graph represent road intersections and links of the tree graph represent road segments.

6. The method of claim 5 wherein the at least one road intersection serves as a root node for the tree graph.

7. The method of claim 5 wherein the step of identifying the at least one road intersection further comprises using a minimum spanning tree matching operation.

8. The method of claim 5 wherein the step of identifying the at least one road intersection further comprises using an all spanning tree matching operation.

9. The method of claim 5 further comprises selecting candidate road intersections in the navigation database based on proximate location to the at least one road intersection, prior to comparing the logical representation to a logical representation of the navigation database.

10. The method of claim 5 wherein depth of the tree graph is based on a probability of number of road segments meeting at one or more road intersection represented by the tree graph.

11. The method of claim 5 wherein depth of the tree graph is determined to be a minimum depth required for the tree graph to uniquely identify the at least one road intersection.

12. The method of claim 1 further comprises applying the database update to the identified road intersection in the navigation database.

13. The method of claim 1 further comprises formulating a patch indicative of the database update in relation to the navigation database.

14. A method for applying an update to a navigation database, comprising:

receiving an update instruction specifying two nodes and a link, where the nodes represent road intersections and the link represents a road segment interconnecting the two nodes;

identifying an existing node in the navigation database which corresponds to at least one of the specified nodes using a logical pattern matching operation;

classifying each of the specified nodes based on its relation to at least one of an existing node or an existing link in the navigation database; and

applying the update instruction in accordance with an ordered operations rule set.

15. The method of claim 14 wherein the step of identifying an existing node further comprises constructing a logical representation of the road topology in the vicinity of at least one of the specified node;

and comparing the logical representation to a logical representation of the navigation database.

16. The method of claim 14 where the step of comparing the logical representation further comprises performing a minimum spanning tree matching operation, where the logical representation is defined as a tree graph and the at least one specified node serves as a root node for the tree graph.

17. The method of claim 14 where the step of comparing the logical representation further comprises performing a all spanning tree matching operation, where the logical representation is defined as a tree graph and the at least one specified node serves as a root node for the tree graph.

18. The method of claim 14 wherein the step of classifying each of the specified nodes further comprises categorizing a specified node as one of the group consisting of:

a node corresponding to an existing node in the navigation database, a point on an existing link in the navigation database, a not-yet-existing element in the navigation database.

19. The method of claim 14 wherein the ordered operations rule set specifies that a link having two nodes which correlate to existing nodes in the navigation database can be added to the navigation database.

20. The method of claim 14 wherein the ordered operations rule set specifies that a link having a node which is a point on an existing link in the navigation database is added by deleting said existing link and adding two links interconnecting said node to other existing nodes in the navigation database.

21. The method of claim 14 wherein the ordered operations rule set specifies a link having two nodes where neither node correlates to an existing node in the navigation data is not be added to the navigation database.

22. The method of claim 14 wherein application of the update instruction is delayed in accordance with the ordered operations rule set until a subsequent update instruction is applied to the navigation database.

23. A method for generating a database renewal for a navigation database, comprising:

providing a list of links to be updated in the navigation database, where each link is represented as two road intersections interconnected by a road segment;

constructing a logical representation for each road intersection uniquely specified in the list of links, such that the logical representation is indicative of the road topology in the vicinity of specified road intersection; and

formulating an ordered set of update instructions for the list of links, such that each update instruction references at least one logical representation.

24. The method of claim 23 further comprises compiling each of the logical representations and the ordered set of update instruction to form a database renewal.

25. The method of claim 23 further comprises identifying attribute data associated with either road segments or road intersections specified in the list of links, and formulating the ordered set of update instructions, such that at least one update instruction references the attribute data.

26. The method of claim 23 wherein the step of constructing a logical representation further comprises building a graph representing the road topology in the vicinity of the at least one road intersection, where nodes of the graph represent road intersections and links of the graph represent road segments