Method and apparatus for providing smaller incremental updates to a navigational database

• US 9,613,527 B2
• Filed: 09/26/2014
• Issued: 04/04/2017
• Est. Priority Date: 09/26/2014
• Status: Active Grant

• Current Assignee: HERE Global B.V. (HERE Holding Corporation)
• Original Assignee: HERE Global B.V. (HERE Holding Corporation)
• Inventors: Pfeifle, Martin
• Primary Examiner(s): Edwards, Jerrah
• Assistant Examiner(s): WEBER, TAMARA L
• Application Number:
  US14/498,758
• Publication Number:
  US 20160093206A1
• Time in Patent Office: 921 Days
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G08G 1/00 Traffic control systems for road vehicles arrangement of road signs or traffic signals E01F9/00 ; automatic vehicle control B62D

Abstract

An approach is provided for determining at least one first cluster set associated with at least one database of one or more navigable links at a first time period and at least one second cluster set associated with the at least one database at a second time period, wherein the at least one first cluster set and the at least one second cluster set include one or more clusters of the one or more navigable links. The approach involves causing, at least in part, a computation of a minimal matching between at least one first cluster set and the at least one second cluster set. The approach also involves causing, at least in part, a renaming of the one or more clusters in the at least one first cluster set, the at least one second cluster set, or a combination thereof based, at least in part, on the minimal matching, wherein the one or more clusters organize the one or more navigable links based, at least in part, on traffic pattern information.

Claims

1. A method of reducing a size of at least one incremental navigation update package sent to a mobile navigation device comprising:

receiving traffic data at a traffic server sent from a plurality of navigational devices over a communication network, the traffic server comprising a processor and a memory that stores the traffic data, wherein the processor;

determines at least one first cluster set associated with at least one database of navigable links at a first time period and at least one second cluster set associated with the at least one database at a second time period, wherein each of the at least one first cluster set and the at least one second cluster set includes one or more clusters of the navigable links organized based on traffic pattern information;

computes a minimal matching between at least one first cluster set and the at least one second cluster set using at least one algorithm of a minimal overall runtime complexity that determines a minimal number of elementary operations on the one or more clusters of the at least one first cluster set to transform the at least one first cluster set into the at least one second cluster set;

reorders the one or more clusters in the at least one second cluster set using an order determined based on the minimal matching; and

creates the at least one incremental navigation update package based, at least in part, on the reordering, wherein the at least one incremental navigation update package includes a minimal number of updates which transform the at least one first cluster set into the at least one second cluster set; and

sends the at least one incremental navigation update package to the mobile navigation device for determining real-time route navigation for a vehicle, a user, or a combination thereof.

2. A method of claim 1, wherein the elementary operations include a delete operation, a rename operation, an add operation, or a combination thereof, of one or more navigable links of the one or more clusters of the at least one first cluster set.

3. A method of claim 1, wherein the processor further:

determines at least one weighted bipartite graph between the at least one first cluster set and the at least one second cluster set using the at least one algorithm,

wherein the minimal matching is selected from the at least one weighted bipartite graph.

4. A method of claim 1, wherein the processor further:

determines that the at least one first cluster set and the at least one second cluster set do not have a same cardinality of clusters; and

adds one or more dummy clusters to the at least one first cluster set, the at least one second cluster set, or a combination thereof to cause the at least one first cluster set and the at least one second cluster set to have the same cardinality prior to the computation of the minimal matching.

5. A method of claim 1, wherein the reordering includes a re-enumeration of the one or more clusters respectively in the at least one first cluster set, the at least one second cluster set, or a combination thereof.

6. A method of claim 1, wherein the processor further:

initiates an arbitrary matching, an optimal matching, or a combination thereof between the at least one first cluster set and the at least one second cluster set.

7. A non-transitory computer-readable storage medium carrying one or more sequences of one or more instructions store thereon executed by a traffic server configured to reduce a size of at least one incremental navigation update package sent to a mobile navigation device, by:

determining at least one first cluster set associated with at least one database of navigable links at a first time period and at least one second cluster set associated with the at least one database at a second time period, wherein each of the at least one first cluster set and the at least one second cluster set includes one or more clusters of the navigable links organized based on traffic pattern information;

computing a minimal matching between at least one first cluster set and the at least one second cluster set using at least one algorithm of a minimal overall runtime complexity that determines a minimal number of elementary operations on the one or more clusters of the at least one first cluster set to transform the at least one first cluster set into the at least one second cluster set;

reordering the one or more clusters in the at least one second cluster set, based on the minimal matching; and

creating the at least one incremental navigation update package based, at least in part, on the reordering, wherein the at least one incremental navigation update package includes a minimal number of updates which transform the at least one first cluster set into the at least one second cluster set; and

sending the at least one incremental navigation update package to the mobile navigation device for determining real-time route navigation for a vehicle, a user, or a combination thereof.

8. A non-transitory computer-readable storage medium of claim 7, wherein the traffic server is further configured to reduce the size of the at least one incremental navigation update package by:

determining at least one weighted bipartite graph between the at least one first cluster set and the at least one second cluster set using the at least one algorithm,

wherein the minimal matching is selected from the at least one weighted bipartite graph.

9. A non-transitory computer-readable storage medium of claim 7 wherein the traffic server is further configured to reduce the size of the at least one incremental navigation update package by:

determining that the at least one first cluster set and the at least one second cluster set do not have a same cardinality of clusters; and

adding one or more dummy clusters to the at least one first cluster set, the at least one second cluster set, or a combination thereof to cause the at least one first cluster set and the at least one second cluster set to have the same cardinality prior to the computation of the minimal matching.

10. A traffic server comprising a processor and a memory that stores traffic data received from a plurality of navigational devices over a communication network, wherein the processor:

determines at least one first cluster set associated with at least one database of navigable links at a first time period and at least one second cluster set associated with the at least one database at a second time period, wherein each of the at least one first cluster set and the at least one second cluster set includes one or more clusters of the navigable links organized based on traffic pattern information;

computes a minimal matching between at least one first cluster set and the at least one second cluster set using at least one algorithm of a minimal overall runtime complexity that determines a minimal number of elementary operations on the one or more clusters of the at least one first cluster set to transform the at least one first cluster set into the at least one second cluster set;

reorders the one or more clusters in the at least one second cluster set using an order determined based on the minimal matching; and

creates the at least one incremental navigation update package based, at least in part, on the reordering, wherein the at least one incremental navigation update package includes a minimal number of updates which transform the at least one first cluster set into the at least one second cluster set; and

sends the at least one incremental navigation update package to the mobile navigation device for determining real-time route navigation for a vehicle, a user, or a combination thereof.