Apparatus and methods for updating a map database

Patent metadata

Field	Value
Publication number	US-11567928-B2
Application number	US-201916584280-A
Country	US
Kind code	B2
Filing date	Sep 26, 2019
Priority date	Sep 26, 2019
Publication date	Jan 31, 2023
Grant date	Jan 31, 2023

Abstract

An apparatus, a method, and a computer program product for obtaining map update data of a region are provided. The method comprises determining an update candidate node, wherein the update candidate node is associated with a node identifier and a first node digest; sending the node identifier and the first node digest to an update data service; and receiving, from the update data service, a response containing one of node digests of the child nodes of the update candidate node at the update data service; or updated content corresponding to the update candidate node. The method may further include updating the map database based on the received response.

First claim

We claim:

1. A method for updating a map database, the method comprising:
determining, by at least one processor, an update candidate node, wherein the update candidate node is associated with a node identifier and a first node digest;
sending, by the at least one processor, the node identifier and the first node digest to an update data service;
receiving, by the at least one processor, from the update data service, a response containing one of:
node digests of child nodes of the update candidate node at the update data service; or
updated content corresponding to the update candidate node; and

updating, by the at least one processor, the map database, based on the received response,
wherein a node corresponds to a map tile or cube, and a node digest of the node corresponds to a hash value.

2. The method of claim 1 , further comprising:
determining a hierarchical tree structure, wherein a root node or an inner node comprises a parental node digest based on an eXclusive OR (XOR) function of the node digests of their corresponding child nodes, and
wherein a leaf node comprises a leaf node digest based on the node identifier of the leaf node and map content associated with the node identifier of the leaf node.

3. The method of claim 2 , further comprising:
in response of receiving update data service-side node digests of the child nodes of the update candidate node, comparing the digest of the update data service-side child nodes of the update candidate node to corresponding nodes of the hierarchical tree structure; and,
in case of mismatch between the compared nodes, sending a node identifier and a node digest of at least one mismatched node to the update data service.

4. The method of claim 2 , further comprising in response to receiving updated content corresponding to the update candidate node, recomputing the hierarchical tree structure based on the received updated content.

5. The method of claim 2 , wherein a value of the leaf node digest is zero if the map content associated with the node identifier is empty.

6. The method of claim 2 , wherein a value of the parental node digest is zero if the corresponding child nodes are empty.

7. The method of claim 1 , further comprising associating a map area identifier to a map tile of a quad-tree map data structure, wherein tiles corresponding to quad-tree leaf nodes are data tiles.

8. The method of claim 7 , further comprising associating the map area identifier to a map cube of an oct-tree map data structure, wherein cubes corresponding to oct-tree leaf nodes are data cubes.

9. An apparatus for updating a map database, the apparatus comprising:
at least one memory configured to store computer executable instructions; and
at least one processor configured to execute the computer executable instructions to:
determine an update candidate node, wherein the update candidate node is associated with a node identifier and a first node digest;
send the node identifier and the first node digest to an update data service;
receive, from the update data service, a response containing one of:
node digests of child nodes of the update candidate node at the update data service; or
updated content corresponding to the update candidate node; and
update the map database, based on the received response,
wherein a node corresponds to a map tile or cube, and a node digest of the node corresponds to a hash value.

10. The apparatus of claim 9 , wherein the at least one processor is further configured to:
determine a hierarchical tree structure, wherein a root node or an inner node comprises a parental node digest based on an eXclusive OR (XOR) function of the node digests of their corresponding child nodes, and
wherein a leaf node comprises a leaf node digest based on the node identifier of the leaf node and map content associated with the node identifier of the leaf node.

11. The apparatus of claim 10 , wherein the at least one processor is further configured to:
in response of receiving update data service-side node digests of the child nodes of the update candidate node, compare the digest of the update data service-side child nodes of the update candidate node to corresponding nodes of the hierarchical tree structure; and,
in case of mismatch between the compared nodes, send a node identifier and a node digest of at least one mismatched node to the update data service.

12. The apparatus of claim 10 , in response to receiving updated content corresponding to the update candidate node, the at least one processor is further configured to recompute the hierarchical tree structure based on the received updated content.

13. The apparatus of claim 10 , wherein a value of the leaf node digest is zero when the map content associated with the node identifier is empty.

14. The apparatus of claim 10 , wherein a value of the parental node digest is zero if the corresponding child nodes are empty.

15. The apparatus of claim 9 , wherein the at least one processor is further configured to associate the map area identifier to a map tile of a quad-tree map data structure, wherein tiles corresponding to quad-tree leaf nodes are data tiles.

16. The apparatus of claim 9 , wherein the at least one processor is further configured to associate the map area identifier to a map cube of an oct-tree map data structure, wherein cubes corresponding to oct-tree leaf nodes are data cubes.

17. A computer program product comprising a non-transitory computer-readable medium having stored thereon computer-executable instructions which when executed by one or more processors of an apparatus, cause the apparatus to carry out operations for updating a map database, the operations comprising:
determining an update candidate node, wherein the update candidate node is associated with a node identifier and a first node digest;
sending the node identifier and the first node digest to an update data service;
receiving, from the update data service, a response containing one of:
node digests of the child nodes of the update candidate node at the update data service; or
updated content corresponding to the update candidate node; and
updating the map database, based on the received response,
wherein a node corresponds to a map tile or cube, and a node digest of the node corresponds to a hash value.

18. The computer program product of claim 17 , wherein the operations further comprise:
determining a hierarchical tree structure, wherein a root node or an inner node comprises a parental node digest based on an eXclusive OR (XOR) function of the node digests of their corresponding child nodes, and
wherein a leaf node comprises a leaf node digest based on the node identifier of the leaf node and map content associated with the node identifier of the leaf node.

19. The computer program product of claim 18 , wherein the operations further comprise:
in response of receiving update data service-side node digests of the child nodes of the update candidate node , comparing the digest of the update data service-side child nodes of the update candidate node to corresponding nodes of the hierarchical tree structure; and,
in case of mismatch between the compared nodes, sending a node identifier and a node digest of at least one mismatched node to the update data service.

20. The computer program product of claim 18 , wherein the operations further comprise in response to receiving updated content corresponding to the update candidate node, recomputing the hierarchical tree structure based on the rece

Assignees

• Here Global Bv

Inventors

• Cajias Raul
• Rolf Daniel

Classifications

• G06F16/2379 Primary

  Updates performed during online database operations; commit processing · CPC title

• G06F16/2246

  Trees, e.g. B+trees · CPC title

• G06F16/29 Primary

  Geographical information databases · CPC title