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

• US 20160147860A1
• Filed: 06/09/2015
• Published: 05/26/2016
• 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 Government Of The United States Of America, As Represented By The Secretary Of The Navy
• Inventors: Sample, John T., Ioup, Elias Z. K.
• Granted Patent: US 10,013,474 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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;

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;

when 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 a 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.

7. The hierarchical synchronization system of claim 1, wherein the cluster hierarchical synchronization module is configured to perform a hierarchical synchronization of tiles between the first dataset and the second dataset by 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;

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;

when 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 a 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.

8. The hierarchical synchronization system of claim 1, 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 a top level hash values for each top level tile of the first dataset and the second dataset;

if the top level hash value for each top level tile do not match, comparing the second level hash values for each second level tile of the first dataset and the second dataset;

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

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

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

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

if the top level hash value for each top level tile do not match, comparing the second level hash values for each second level tile of the first dataset and the second dataset;

recursively comparing the next level hash values for each corresponding level tiles of the first dataset and the second dataset until the 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 cluster hierarchical synchronization module, wherein the cluster hierarchical synchronization module is implemented in a computer system that comprises instructions stored in a machine-readable medium and a processor that executes the instructions;

a tile hierarchical synchronization module, wherein the tile hierarchical synchronization module is implemented in a computer system that comprises instructions stored in a machine-readable medium and a processor that executes the instructions; and

a dynamic heuristic module configured to automatically determine which of the cluster hierarchical synchronization module or the tile hierarchical synchronization module to utilize to synchronize a first dataset with a second dataset depending on a frequency in which a plurality of tiles in the first dataset change, wherein the dynamic heuristic module is implemented in a computer system that comprises instructions stored in a machine-readable medium and a processor that executes the instructions.