Map Update Scripts with Tree Edit Operations

• US 20140108462A1
• Filed: 10/15/2012
• Published: 04/17/2014
• Est. Priority Date: 10/15/2012
• Status: Active Grant

• Current Assignee: HERE Global B.V. (HERE Holding Corporation)
• Original Assignee: Navteq B.V. (HERE Holding Corporation)
• Inventors: Pfeifle, Martin, Reichert, Andre, Schmitz, David
• Granted Patent: US 9,015,200 B2
• Time in Patent Office: Days
• US Class Current: 707/795
• CPC Class Codes: G06F 16/2219 Large Object storage; Management thereof
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 16/9027 Trees

Abstract

A geographic database is defined using hierarchical data trees and updated by changing selected portions of a data tree. A device defines a binary large object (BLOB) including map data as a first data tree and an update to the map data as a second data tree. The device computes a difference between the first data tree and the second data tree. The difference may include the data and links that are being updated. The device generates an update script including a sequence of edit operations needed to update the map data. The device may communicate the update script to a navigation device, which is configured to execute the update script to perform the update on a local version of the map data.

Claims

1. A method comprising:

representing a binary large object including map data as a first data tree;

representing a new version of the binary large object including map data as a second data tree;

identifying, using a processor, a sequence of edit operations as a difference between the first data tree and the second data tree; and

generating, using the processor, an update script including the sequence of edit operations and map data.

2. The method of claim 1, wherein the sequence of edit operations includes one or more of an insert operation, a delete operation, and an update operation.

3. The method of claim 1, wherein at least one operation of the sequence of edit operations affects a subtree of the first data tree.

4. The method of claim 1, wherein the map data includes navigational data.

5. The method of claim 1, wherein the new version of the binary large object includes a new road link.

6. The method of claim 1, wherein the update script is expressed in relational data script.

7. The method of claim 1, further comprising:

forwarding the update script to a mobile device.

8. The method of claim 7, further comprising:

calculating an order of the sequence of edit operations according to a cost minimizing algorithm.

9. The method of claim 1, further comprising:

accessing an update size selector; and

defining a number of nodes of the update script according to the update size selector, wherein an amount of time for executing the update script depends on the update size selector and a size of the update script depends on the update size selector.

10. The method of claim 9, wherein the amount of time is proportionally related to the update size selector and the size of the update script is inversely related to the update size selector.

11. An apparatus comprising:

a memory including computer program code;

a processor configured to execute the computer program code to cause the navigation apparatus to;

compare a binary large object including map data to an update to the map data;

identify a sequence of edit operations as a difference between the binary large object and the update to the map data; and

generate an update script including the sequence of edit operations, wherein the update script includes less data than the binary large object.

12. The apparatus of claim 11, wherein the sequence of edit operations includes one or more of an update operation, an insert operation, and a delete operation.

13. The apparatus of claim 11, wherein the update scripts modifies a subtree of the binary large object.

14. The apparatus of claim 11, wherein the update script is defined according to an embedded relational data script.

15. The apparatus of claim 11, wherein the sequence of edit operations includes path segment data.

16. The apparatus of claim 11, the processor configured to execute the computer program code to cause the navigation apparatus to:

calculate an order of the sequence of edit operations in the update script according to an edit cost minimizing algorithm.

17. The apparatus of claim 11, the processor configured to execute the computer program code to cause the navigation apparatus to:

access a number of operations selector;

define a number of operations in the sequence of edit operations according to the number of operations selector, wherein an amount of time for executing the update script depends on the number of operations selector and a size of the update script depends on the number of operations selector.

18. The apparatus of claim 17, wherein the amount of time is proportionally related to the number of operations selector and the size of the update script is inversely related to the number of operations selector.

19. A non-transitory computer readable medium including instructions that when executed are operable to:

receive, over a wireless communication path, an update script including an update command for a subtree of a first data tree representing a binary large object;

identify a second data tree associated with the first data tree; and

modify, using a processor, the second data tree from execution of the update script on the second data tree, wherein the subtree describes a difference between the first data tree and the second data tree.

20. The non-transitory computer readable medium of claim 19, the instructions further operable to:

display updated map data including the data in the subtree in a navigation application.