Systems and methods for expedited data transfer in a communication system using hash segmentation

• US 20050004954A1
• Filed: 07/01/2003
• Published: 01/06/2005
• Est. Priority Date: 07/01/2003
• Status: Abandoned Application

• Current Assignee: Hand Held Products Incorporated (Honeywell International Inc.)
• Original Assignee: Hand Held Products Incorporated (Honeywell International Inc.)
• Inventors: Soule, Robert Marion III
• Application Number:
  US10/611,015
• Publication Number:
  US 20050004954A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/20 of structured data, e.g. relational data

Abstract

The present invention provides for an improved method and system for determining differences in data sets or data files, expedited data transfer and data reconciliation in a communication network using hash segmentation processing. The system and method provides for an efficient means of communicating updated files, new revisions or verifying files between a source host and a target host. By implementing hash segmentation processing, and in many embodiments iterative hash segmentation processing, the updates within the files can be isolated for the purpose of minimizing the amount of data communicated from the source host to the target host. The system and methods provide for the transfer of data between two hosts in instances in which neither host is aware of the revision that exists on the other host. The hash segmentation process may implement a logarithmic hash approach or a sliding linear hash approach.

Claims

1. A method for determining differences between datasets residing on separate hosts in a communication network, the method comprising the steps of:

creating first hash values, at a first host, corresponding to a plurality of segments of a first dataset;

creating second hash values, at a second host, corresponding to a plurality of segments of a second dataset; and

comparing one or more first hash values to the second hash values to determine which segments of the datasets differ.

2. The method of claim 1 further comprising the step of communicating the first hash values from the first host to the second host and wherein the step of comparing one or more first hash values to the second hash values to determine which segments of the datasets differ further comprises comparing, at the second host, one or more first hash values to the second hash values to determine which segments of the datasets differ.

3. The method of claim 1 further comprising the step of communicating the first and second hash values to a third host and wherein the step of comparing one or more first hash values to the second hash values to determine which segments of the datasets differ further comprises comparing, at the third host, one or more first hash values to the second hash values to determine which segments of the datasets differ.

4. The method of claim 1, further comprising the step of communicating from the first host to the second host one or more segments of the first dataset if the comparison determines that one or more segments of the first dataset differ from the second dataset.

5. The method of claim 4, wherein the step of communicating from the first host to the second host is conducted automatically once the comparison determines that one or more segments of the first dataset differ from the second dataset.

6. The method of claim 4, wherein the step of communicating from the first host to the second host is conducted only if the comparison determines that the total length of the differing segments is below a maximum threshold.

7. The method of claim 4, wherein the step of communicating from the first host to the second host one or more segments of the first dataset if the comparison determines that one or more segments of the first dataset differ from the second dataset further comprises choosing, from a plurality of communication medium options, a communication medium by which to transmit the differing segments based on the total length of the differing segments.

8. The method of claim 4, further comprising the step of compiling a third dataset that includes those segments of the first dataset determined to differ from the second dataset and those segments of the second dataset determined not to differ from the first dataset.

9. The method of claim 8, wherein the step of compiling a third dataset occurs at a host chosen from the group consisting of the first host, the second host or a third host.

10. The method of claim 4, further comprising the step of searching in the second dataset for a match to a subset of one of the first dataset segments communicated from the first host.

11. The method of claim 1 further comprising the step of isolating, iteratively, one or more differences within the one or more segments of the first and second datasets determined to have differed.

12. The method of claim 11 wherein the step of isolating, iteratively, one or more differences within the one or more segments of the first and second datasets determined to have differed further comprises the steps of:

creating third hash values, at the first host, corresponding to sub-segments of the segment of the first dataset determined to have differed;

creating fourth hash values, at the second host, corresponding to sub-segments of the segment of the second dataset determined to have differed; and

comparing the third hash values to the fourth hash values to determine which sub-segments of the segment differs.

13. The method of claim 12, further comprising the steps of communicating from the first host to the second host one or more sub-segments of the first dataset if a determination is made that one or more sub-segments of the segment differs.

14. The method of claim 13, further comprising the step of compiling a segment of the third dataset that includes those sub-segments of the first dataset determined to differ from the second dataset and those segments of the second dataset determined not to differ from the first dataset.

15. A method for expedited data transfer and data reconciliation in a communication network, the method comprising the steps of:

creating, at a first host, first hash values corresponding to segments of a first dataset;

communicating the first hash values to a second host having a second dataset residing thereon;

creating, at the second host, second hash values corresponding to segments of the second dataset;

comparing, at the second host, the first and second hash values to determine if a segment difference exists between corresponding first dataset segments and second dataset segments;

communicating to the second host one or more segments of the first dataset that have been determined to differ from the second dataset; and

compiling a third dataset that includes the one or more segments of the first dataset determined to differ from the second dataset and one or more segments of the second dataset determined not to differ from the first dataset.

16. The method of claim 15, further comprising the step of determining where, within the one or more segments determined to differ, the difference occurs.

17. The method of claim 15, further comprising the step of isolating a difference within a segment difference by iteratively comparing hash values corresponding to sub-segments of the segments determined to differ.

18. The method of claim 15, wherein the step of communicating to the second host those segments of the first dataset that have been determined to differ from the second dataset occurs automatically when a difference has been determined.

19. The method of claim 15, wherein the step of communicating to the second host one or more segments of the first dataset that have been determined to differ from the second dataset is conducted only if the comparison determines that the total length of the differing segments is below a maximum threshold.

20. The method of claim 15, further comprising the step of choosing, from a plurality of communication medium options, a communication medium by which to transmit the differing segments based on the total length of the differing segments.

21. The method of claim 15 further comprising the step of determining, if a segment difference exists, whether the differing segment exceeds a length threshold, thus, requiring further segmentation to isolate the difference.

22. The method of claim 21, further comprising the steps of:

creating if a segment difference has been determined to exceed the length threshold, third hash values corresponding to sub-segments of the second dataset segment in which the difference exists;

creating fourth hash values corresponding to sub-segments of the first dataset segment in which the difference exists; and

comparing the third and fourth hash lists to determine a sub-segment difference between corresponding first dataset sub-segments and second dataset sub-segments.

23. The method of claim 22, further comprising the step of determining, if a sub-segment difference exists, whether the differing sub-segment exceeds a length threshold.

24. The method of claim 23, further comprising the step of compiling a segment of the third dataset that includes one or more sub-segments of the first dataset that have been determined to differ from one or more sub-segments of the second dataset.

25. A method for determining differences between datasets residing on separate hosts in a communication network, the method comprising the steps:

creating first dataset hash values, at a first host, corresponding to segments of a first dataset; and

searching, at a second host, for segments of a second dataset that have matching hash values to the first dataset hash values using a slide function of a sliding hash algorithm.

26. The method of claim 25 wherein the step of searching, at second host, for segments of a second dataset that have matching hash values to the first dataset hash values using a slide function of a sliding hash algorithm, further comprises the steps of:

creating, at a second host, a first hash value for a first segment of a second dataset;

comparing the first hash value of the first segment of the second dataset to one or more of the first dataset hash values to determine if the first hash value matches any of the first dataset hash values;

sliding, by a predefined length, the first segment of the second dataset to create a second hash value for a second segment of the second dataset; and

comparing the second hash value to one or more first dataset hash values to determine if the second hash value matches any of the first dataset hash values.

27. The method of claim 26, further comprising the step of:

continuing to iteratively slide, by a predefined length, segments of the second dataset to create subsequent hash values for subsequent segments of the second dataset; and

comparing the subsequent hash values to the first dataset hash values to determine if the subsequent hash values match any of the first dataset hash values.

28. The method of claim 25 further comprising the step of communicating the first dataset hash values from the first host to the second host prior to searching, at the second host, for segments of a second dataset that have matching hash values to the first dataset hash values using a slide function of a sliding hash algorithm.

29. The method of claim 25, further comprising the step of communicating from the first host to the second host one or more segments of the first dataset if the comparison determines that one or more segments of the second dataset have no valid matches to segments of the first dataset.

30. The method of claim 29, wherein the step of communicating from the first host to the second host is conducted automatically once the comparison determines that one or more segments of the second dataset have no matching hash values amongst the first dataset first dataset hash values.

31. The method of claim 29, wherein the step of communicating from the first host to the second host is conducted only if the comparison determines that the total length of the differing segments is below a maximum threshold.

32. The method of claim 29, wherein the step of communicating from the first host to the second host one or more segments of the first dataset if the comparison determines that one or more segments of the first dataset differ from the second dataset further comprises choosing, from a plurality of communication medium options, a communication medium by which to transmit the differing segments based on the total length of the differing segments.

33. The method of claim 29, further comprising the step of compiling a third dataset that includes those segments of the second dataset that have matching hash values amongst the first dataset hash values and those segments of the first dataset determined not to have matching hash values amongst the hash values of the second dataset segments.

34. The method of claim 29, wherein the step of compiling a third dataset occurs at a host chosen from the group consisting of the first host, the second host or a third host.

35. A system for expedited data transfer and data reconciliation in a communication network, the system comprising:

a first processor residing in a first host, the first processor implements a hash algorithm to create first hash values corresponding to segments of a first dataset; and

a second processor residing in a second host and in network communication with the first processor, the second processor implements the first hash algorithm to create second hash values corresponding to segments of a second dataset;

wherein the first hash values are compared to the second hash values to determine which segments of the datasets differ and wherein the first host communicates to the second host one or more segments of the first dataset if a determination is made that one or more segments of the first dataset differ from the second dataset.

36. The system of claim 35, further comprising a compiler, in communication with the second processor, which compiles a third dataset that includes those segments of the first dataset determined to differ from the second dataset and those segments of the second dataset determined not to differ from the first dataset.

37. The system of claim 35, wherein the second processor is capable of searching in the second dataset for a match to a subset of one of the first dataset segments communicated from the first host.

38. The system of claim 35, wherein the first and second processors determine where, within the segments that have been determined to differ, the differences occur.

39. The system of claim 35, wherein the first and second processors isolate, iteratively, one or more differences within the one or more segments of the first and second datasets determined to have differed.

40. The system of claim 35, wherein the first processor implements the hash algorithm to create third hash values corresponding to sub-segments of the first dataset determined to have differed, the second processor implements the hash algorithm to create fourth hash values corresponding to sub-segments of the second dataset segments determined to have differed, wherein the first processor compares the third hash values to the fourth hash values to determine which sub-segments of the datasets differ.

41. The system of claim 35, wherein the second processor determines, if a segment difference exists, whether the differing segment exceeds a length threshold, thus, requiring further segmentation to isolate the difference.