System and method for hierarchical synchronization of a dataset of image tiles

• US 10,013,474 B2
• Filed: 06/09/2015
• Issued: 07/03/2018
• Est. Priority Date: 10/25/2011
• Status: Active Grant

• Current Assignee: The Government Of The United States Of America, As Represented By The Secretary Of The Navy
• Original Assignee: the united states of america as represented by the secretary of the navy
• Inventors: Sample, John T., Ioup, Elias Z K
• Primary Examiner(s): Coby, Frantz
• Application Number:
  US14/734,232
• Publication Number:
  US 20160147860A1
• Time in Patent Office: 1,120 Days
• Field of Search: 707696, 707763, 707737, 707805, 707673, 707711, 707741, 707830, 709201, 709203, 709213, 709217, 709248
• CPC Class Codes: G06F 16/20 of structured data, e.g. relational data
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 16/275 Synchronous replication
• CPC Class Codes: G06F 16/282 Hierarchical databases, e.g. IMS, LDAP data stores or Lotus Notes
• CPC Class Codes: G06F 16/50 of still image data
• CPC Class Codes: G06F 16/51 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/93 Document management systems
• CPC Class Codes: G06T 1/60 Memory management
• CPC Class Codes: G06T 17/05 Geographic models
• CPC Class Codes: G06T 3/40 Scaling of whole images or parts thereof, e.g. expanding or contracting
• CPC Class Codes: G09B 29/003 Maps
• CPC Class Codes: G09B 29/005 Map projections or methods associated specifically therewith

Abstract

A system and method for hierarchical synchronization of tiles between a first dataset and a second dataset by computing and storing multiple composite cluster hash values for multiple clusters in the first and second dataset. For each of the composite cluster hash values, comparing a composite cluster hash value of a particular cluster in the first dataset with a composite cluster hash value of a corresponding cluster in the second dataset. When the composite cluster hash values of the corresponding clusters do not match, retrieving all tile hashes corresponding to all the tiles from the non-matching cluster in the first dataset, and retrieving all tile hashes corresponding to all the tiles from the non-matching cluster in the second dataset. Finally, determining the one or more changed tiles between the non-matching cluster in the first dataset and the non-matching cluster in the second dataset by comparing the corresponding tile hashes.

Claims

1. A method for hierarchical synchronization of tiles between a first dataset and a second dataset, comprising the steps of:

computing and storing a plurality of composite cluster hash values for each of a plurality of clusters in the first dataset and the second dataset, wherein the plurality of clusters are configured with a hierarchical pyramid structure that arranges a plurality of tiles into levels such that a second level of tiles comprises four times as many tiles as a first level of tiles, and wherein each tile in the second level of tiles has a lower scale that is four times smaller than a higher scale of each tile in the first level of tiles;

for each of the plurality of composite cluster hash values, comparing a composite cluster hash value of a particular cluster in the first dataset with a composite cluster hash value of a corresponding cluster in the second dataset, wherein the particular cluster comprises a geographic subset of the plurality of tiles that are each located in a geographic region, and wherein the geographic subset comprises related tiles from both the first set of tiles and the second set of tiles;

determining that the composite cluster hash values of the corresponding clusters of the first and second datasets do not match;

retrieving a plurality of tile hashes corresponding to the plurality of tiles from the non-matching cluster in the first dataset and retrieving a plurality of tile hashes corresponding to a plurality of tiles from the non-matching cluster in the second dataset; and

determining the one or more changed tiles between the non-matching cluster in the first data set and the non-matching cluster in the second dataset by comparing the corresponding tile hashes, for each of the plurality of tile hashes.

2. The method of claim 1, wherein the step of computing and storing a plurality of composite cluster hash values for each of a plurality of clusters in the first and second datasets comprises the step of concatenating a plurality of tile hashes of tiles together in each cluster, and computing a hash on the concatenated tile hashes, which generates the composite cluster hash value for the cluster.

3. The method of claim 1, further comprising the step of copying the one or more changed tiles from the first dataset to the second dataset to match the first and second datasets.

4. A method for hierarchical synchronization of a plurality of tiles between a first dataset and a second dataset, comprising the steps of:

comparing top level hash values for each top level tile of the first dataset and the second dataset, wherein each top level tile is in a top level of a hierarchical pyramid structure for arranging the plurality of tiles into levels such that a second level of tiles comprises four times as many tiles as a top level of tiles, and wherein each tile in the second level of tiles has a lower scale that is four times smaller than a higher scale of each tile in the top level of tiles;

determining that the top level hash value for each top level tile do not match;

comparing second level hash values for each tile in the second level of tiles of the first dataset and the second dataset;

recursively comparing next level hash values for each corresponding level tiles of the first dataset and the second dataset until a bottom level is reached; and

determining one or more changed tiles based on any hash level values that do not match.

5. The method of claim 4, further comprising the step of copying the one or more changed tiles from the first dataset to the second dataset to match the first and second datasets.

6. A hierarchical synchronization system, comprising:

a storage mechanism to store a first dataset that comprises a plurality of tiles;

a computer processor operatively connected to the storage mechanism, the computer processor to execute;

a cluster hierarchical synchronization module that is configured to;

compute and store a plurality of composite cluster hash values for each of a plurality of clusters in the first dataset and a second dataset, wherein the plurality of clusters are configured in a hierarchical pyramid structure that arranges the plurality of tiles into levels such that a second level of tiles comprises four times as many tiles as a first level of tiles, and wherein each tile in the second level of tiles has a lower scale that is four times smaller than a higher scale of each tile in the first level of tiles;

for each of the plurality of composite cluster hash values, compare a composite cluster hash value of a particular cluster in the first dataset with a composite cluster hash value of a corresponding cluster in the second dataset, wherein the particular cluster comprises a geographic subset of the plurality of tiles that are each located in a geographic region, and wherein the geographic subset comprises related tiles from both the first set of tiles and the second set of tiles;

determine that the composite cluster hash values of the corresponding clusters of the first and second datasets do not match;

retrieve a plurality of tile hashes corresponding to the plurality of tiles from the non-matching cluster in the first dataset and retrieving a plurality of tile hashes corresponding to a plurality of tiles from the non-matching cluster in the second dataset; and

determine the one or more changed tiles between the non-matching cluster in the first data set and the non-matching cluster in the second dataset by comparing the corresponding tile hashes, for each of the plurality of tile hashes.

7. The hierarchical synchronization system of claim 6, wherein the computer processor also executes a dynamic heuristic module to automatically determine which of the cluster hierarchical synchronization module or a tile hierarchical synchronization module to utilize to synchronize the first dataset with the second dataset depending on a frequency in which the plurality of tiles in the first dataset change.

8. The hierarchical synchronization system of claim 7, wherein the tile hierarchical synchronization module is configured to perform a hierarchical synchronization of tiles between the first dataset and the second dataset by:

comparing top level hash values for each top level tile of the first dataset and the second dataset;

determining that the top level hash value for each top level tile do not match;

comparing second level hash values for each second level tile of the first dataset and the second dataset;

recursively comparing next level hash values for each corresponding level tiles of the first dataset and the second dataset until a bottom level is reached; and

determining one or more changed tiles based on any hash level values that do not match.