System and method for unorchestrated determination of data sequences using sticky byte factoring to determine breakpoints in digital sequences

• US 7,272,602 B2
• Filed: 06/04/2004
• Issued: 09/18/2007
• Est. Priority Date: 11/06/2000
• Status: Expired due to Term

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Moulton, Gregory Hagan
• Primary Examiner(s): Wassum; Luke S
• Application Number:
  US10/861,796
• Publication Number:
  US 20040225655A1
• Time in Patent Office: 1,201 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 16/137 Hash-based content-based indexing of textual data G06F16/31
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A system and method for unorchestrated determination of data sequences using “sticky byte” factoring to determine breakpoints in digital sequences such that common sequences can be identified. Sticky byte factoring provides an efficient method of dividing a data set into pieces that generally yields near optimal commonality. This is effectuated by employing a rolling hashsum and, in an exemplary embodiment disclosed herein, a threshold function to deterministically set divisions in a sequence of data. Both the rolling hash and the threshold function are designed to require minimal computation. This low overhead makes it possible to rapidly partition a data sequence for presentation to a factoring engine or other applications that prefer subsequent synchronization across the data set.

Claims

1. A method for partitioning a digital sequence comprising:

performing a hash function on at least a portion of said digital sequence;

monitoring hash values produced by said hash function for a first predetermined numeric pattern found in a range of numeric values; and

marking a breakpoint in said digital sequence when said first predetermined numeric pattern occurs,

said step of performing said hash function comprising a rolling hash function adapted to scan portions of said digital sequence combined with adjusting a hash value based on a length of a current partition of said digital sequence to increase a likelihood of identifying a breakpoint in said current partition as a potential length of said current partition increases.

2. The method of claim 1, wherein said first predetermined numeric pattern is a bit pattern.

3. The method of claim 1, wherein said rolling hash function comprises a 32-bit hash function.

4. The method of claim 1, wherein said first predetermined numeric pattern comprises a consecutive sequence of bits.

5. The method of claim 4, wherein during said monitoring said consecutive sequence of bits is found in said hash values, the hash values comprising hash sequences that are not numerically consecutive.

6. The method of claim 4, wherein said consecutive sequence of bits comprises a plurality of endmost bits.

7. The method of claim 1, further comprising:

determining a threshold restriction for said step of monitoring said hash values; and

increasing a probability of said marking of said breakpoint in said digital sequence.

8. The method of claim 7, wherein said step of increasing said probability of said marking of said breakpoint in said digital sequence is a function of at least a desired chunk size.

9. The method of claim 7, wherein said step of increasing said probability of said marking of said breakpoint in said digital sequence is carried out by the step of:

utilizing a second predetermined numeric pattern for said step of monitoring said hash values; and

alternatively marking said breakpoint when said second predetermined numeric pattern occurs.

10. The method of claim 7, wherein said step of increasing said probability of said marking of said breakpoint in said digital sequence is a function of some content portion of said sequence.

11. A method for determining at least a first breakpoint in at least a first digital sequence comprising:

determining a subset group of said first digital sequence;

performing a hash function on said subset group of said first digital sequence beginning at a starting position in said first digital sequence until a first predetermined numeric pattern, which is found in a range of numeric values, in said hash value is obtained, wherein said hash function is combined with adjusting said hash value based on a length of a current partition of said first digital sequence to increase a likelihood of identifying said first breakpoint in said current partition as a potential length of said current partition increases; and

marking said first breakpoint when said first predetermined numeric pattern in said hash value is obtained.

12. The method of claim 11, wherein said numeric pattern comprises a bit pattern.

13. The method of claim 11, wherein said step of performing a hash function comprises a rolling hash function that scans portions of said digital sequence.

14. The method of claim 11, further comprising the steps of:

further performing a hash function on another subset group of said first digital sequence from said first breakpoint until said first predetermined numeric pattern in said hash value is again obtained; and

marking another breakpoint in said first digital sequence when said first predetermined numeric pattern in said hash value is again obtained.

15. The method of claim 14, wherein said step of further performing said hash function is carried out by means of a rolling hash function.

16. The method of claim 11, further comprising the steps of:

determining a second predetermined numeric pattern in said hash value; and

continuing said step of performing said hash function on said subset group of said first digital sequence until an established threshold restriction has been met.

17. The method of claim 11, further comprising the steps of:

storing said predetermined hash value of said first breakpoint in a data storage, said predetermined hash value of said first breakpoint pointing to a corresponding portion of said first digital data sequence from said starting point to said first breakpoint;

performing a hash function on a subset group beginning at a starting position in a second digital sequence until said first predetermined numeric pattern in said hash value is obtained;

marking a second breakpoint in said second digital sequence when said first predetermined numeric pattern in said hash value is obtained;

comparing said predetermined hash value at said first breakpoint with said predetermined hash value at said second breakpoint

if said predetermined hash value of said first breakpoint is not the same as said predetermined hash value of said second breakpoint, replacing said predetermined hash value of said first breakpoint in said data storage, said predetermined hash value of said second breakpoint pointing to a corresponding portion of said second digital data sequence from said starting point to said second breakpoint; and

if said predetermined hash value of said first breakpoint is the same as said predetermined hash value of said second breakpoint, storing said predetermined hash value of said second breakpoint in said data storage, said predetermine hash value of said second breakpoint pointing to said predetermined hash value of said first breakpoint.

18. A computer program product comprising:

a computer usable medium having computer readable code embodied therein for determining at least a first breakpoint in a first digital sequence comprising;

computer readable program code devices configured to cause a computer to effect determining a subset group of said first digital sequence;

computer readable program code devices configured to cause a computer to effect performing a hash function on said subset group of said first digital sequence beginning at a starting position in said first digital sequence until a first predetermined numeric pattern in said hash value is obtained, wherein said hash function is combined with adjusting said hash value based on a length of a current partition of said first digital sequence to increase a likelihood of identifying a first breakpoint in said current partition as a potential length of said current partition increases;

computer readable program code devices configured to cause a computer to effect marking said first breakpoint when said first predetermined numeric pattern in said hash value is obtained;

computer readable program code devices configured to cause a computer to effect storing said predetermined hash value of said first breakpoint in a data storage, said predetermined hash value of said first breakpoint pointing to a corresponding portion of said first digital data sequence from said starting point to said first breakpoint;

computer readable program code devices configured to cause a computer to effect performing a hash function on a subset group beginning at a starting position in a second digital sequence until said first predetermined numeric pattern in said hash value is obtained;

computer readable program code devices configured to cause a computer to effect marking a second breakpoint in said second digital sequence when said first predetermined numeric pattern in said hash value is obtained, wherein said hash function is combined with adjusting said hash value based on a length of a current partition of said second digital sequence to increase a likelihood of identifying said second breakpoint in said current partition as a potential length of said current partition increases; and

computer readable program code devices configured to cause a computer to effect comparing said predetermined hash value at said first breakpoint with said predetermined hash value at said second breakpoint, wherein

if said predetermined hash value of said first breakpoint is not the same as said predetermined hash value of said second breakpoint, replacing said predetermined hash value of said first breakpoint in said data storage, said predetermined hash value of said second breakpoint pointing to a corresponding portion of said second digital data sequence from said starting point to said second breakpoint; and

if said predetermined hash value of said first breakpoint is the same as said predetermined hash value of said second breakpoint, storing said predetermined hash value of said second breakpoint in said data storage, said predetermine hash value of said second breakpoint pointing to said predetermined hash value of said first breakpoint.

19. The computer program product of claim 18, wherein said numeric pattern comprises a bit pattern.

20. The computer program product of claim 18, wherein said computer readable program code devices configured to cause a computer to effect performing a hash function is carried out by means of a rolling hash function.

21. The computer program product of claim 18, further comprising:

computer readable program code devices configured to cause a computer to effect further performing a hash function on another subset group of said first digital sequence from said first breakpoint until said first predetermined numeric pattern in said hash value is again obtained; and

computer readable program code devices configured to cause a computer to effect marking another breakpoint in said first digital sequence when said first predetermined numeric pattern in said hash value is again obtained.

22. The computer program product of claim 21, wherein said computer readable program code devices configured to cause a computer to effect further performing said hash function is carried out by means of a rolling hash function.

23. The computer program product of claim 18, further comprising:

computer readable program code devices configured to cause a computer to effect determining a second predetermined numeric pattern in said hash value;

computer readable program code devices configured to cause a computer to effect continuing said step of performing said hash function on said subset group of said first digital sequence until an established threshold restriction has been met; and

computer readable program code devices configured to cause a computer to effect alternatively marking said first breakpoint when said second predetermined numeric pattern in said hash value is obtained.

24. A method for determining at least a first breakpoint in at least a first digital sequence comprising:

determining a subset group of said first digital sequence;

performing a hash function on said subset group of said first digital sequence beginning at a starting position in said first digital sequence until a first predetermined numeric pattern is found in the hash values from the said hash function is obtained, wherein the hash function is a 32-bit rolling hash function and the subset group is a 32-bit pattern derived directly or indirectly from the said first digital sequence combined with adjusting said hash value based on a length of a current partition of said first digital sequence to increase a likelihood of identifying said first breakpoint in said current partition as a potential length of said current partition increases, and the performing comprises shifting the 32-bit pattern over one bit, reading a character from the first digital sequence and deriving directly or indirectly another 32-bit pattern, and repeating the shifting and the reading, until there are 32-bits in sequence that can be hashed together to provide one said hash value;

marking said first breakpoint when said first predetermined numeric pattern in said hash value is obtained;

further performing a hash function on another subset group of said first digital sequence from said first breakpoint until said first predetermined numeric pattern in said hash value is again obtained; and

marking another breakpoint in said first digital sequence when said first predetermined numeric pattern in said hash value is again obtained.

25. The method of claim 24, wherein said step of further performing said hash function is carried out by means of a rolling hash function.

26. The method of claim 24, further comprising the steps of

storing said predetermined hash value of said first breakpoint in a data storage, said predetermined hash value of said first breakpoint pointing to a corresponding portion of said first digital data sequence from said starting point to said first breakpoint;

performing a hash function on a subset group beginning at a starting position in a second digital sequence until said first predetermined numeric pattern in said hash value is obtained;

marking a second breakpoint in said second digital sequence when said first predetermined numeric pattern in said hash value is obtained;

comparing said predetermined hash value at said first breakpoint with said predetermined hash value at said second breakpoint;

if said predetermined hash value of said first breakpoint is not the same as said predetermined hash value of said second breakpoint, replacing said predetermined hash value of said first breakpoint in said data storage, said predetermined hash value of said second breakpoint pointing to a corresponding portion of said second digital data sequence from said starting point to said second breakpoint; and

if said predetermined hash value of said first breakpoint is the same as said predetermined hash value of said second breakpoint, storing said predetermined hash value of said second breakpoint in said data storage, said predetermine hash value of said second breakpoint pointing to said predetermined hash value of said first breakpoint, thereby equating a corresponding portion of said first digital sequence from said starting point to said first breakpoint with a corresponding portion of said second digital sequence from said staffing position to said second breakpoint.

27. A computer program product comprising:

a computer usable medium having computer readable code embodied therein for determining a first breakpoint in a first digital sequence comprising;

computer readable program code devices configured to cause a computer to effect determining a subset group of said first digital sequence;

computer readable program code devices configured to cause a computer to effect performing a hash function on said subset group of said first digital sequence beginning at a starting position in said first digital sequence until a first predetermined numeric pattern in said hash value is obtained combined with adjusting said hash value based on a length of a current partition of said first digital sequence to increase a likelihood of identifying said first breakpoint in said current partition as a potential length of said current partition increases, wherein the hash function is a 32-bit rolling hash function and the subset group is a 32-bit pattern, and the performing comprises shifting the 32-bit pattern over one bit, reading a character from the first digital sequence, and repeating the shifting and the reading; and

computer readable program code devices configured to cause a computer to effect marking said first breakpoint when said first predetermined numeric pattern in said hash value is obtained.

28. The computer program product of claim 27, further comprising:

computer readable program code devices configured to cause a computer to effect further performing a hash function on another subset group of said first digital sequence from said first breakpoint until said first predetermined numeric pattern in said hash value is again obtained; and

computer readable program code devices configured to cause a computer to effect marking another breakpoint in said first digital sequence when said first predetermined numeric pattern in said hash value is again obtained.

29. The computer program product of claim 28, wherein said computer readable program code devices configured to cause a computer to effect further performing said hash function is carried out by means of a rolling hash function.

30. The computer program product of claim 27, further comprising:

computer readable program code devices configured to cause a computer to effect determining a second predetermined numeric pattern in said hash value;

computer readable program code devices configured to cause a computer to effect continuing said step of performing said hash function on said subset group of said first digital sequence until an established threshold restriction has been met; and

computer readable program code devices configured to cause a computer to effect alternatively marking said first breakpoint when said second predetermined numeric pattern in said hash value is obtained.

31. The computer program product of claim 27, further comprising:

computer readable program code devices configured to cause a computer to effect performing a hash function on a subset group beginning at a starting position in a second digital sequence until said first predetermined numeric pattern in said hash value is obtained;

computer readable program code devices configured to cause a computer to effect marking a second breakpoint in said second digital sequence when said first predetermined numeric pattern in said hash value is obtained;

computer readable program code devices configured to cause a computer to effect comparing said predetermined hash value at said first breakpoint with said predetermined hash value at said second breakpoint; and

computer readable program code devices configured to cause a computer to effect equating a corresponding portion of said first digital sequence from said starting point to said first breakpoint with a corresponding portion of said second digital sequence from said starting position to said second breakpoint.

32. A method for partitioning a digital sequence comprising:

performing a rolling hash function on at least a portion of a digital sequence to produce binary sequences, said hash function being combined with adjusting a hash value based on a length of a current partition of said digital sequence to increase a likelihood of identifying a breakpoint in said current partition as a potential length of said current partition increases;

monitoring said binary sequences produced by said hash function for a predetermined pattern of bits; and

marking said breakpoint in said digital sequence when said predetermined pattern occurs.

33. The method of claim 32, wherein the predetermined pattern of bits comprises a consecutive sequence of bits.

34. The method of claim 33, wherein the consecutive sequence of bits comprises a plurality of endmost bits.

35. The method of claim 32, wherein the performing of the hash function comprises performing a rolling hash function adapted to scan portions of said digital sequence.

36. A computer program product comprising:

computer readable program code devices configured to cause a computer to effect performing a rolling hash function on at least a portion of a digital sequence to produce binary sequences, said hash function being combined with adjusting said hash value based on a length of a current partition of said first digital sequence to increase a likelihood of identifying said first breakpoint in said current partition as a potential length of said current partition increases;

computer readable program code devices configured to cause a computer to effect monitoring said binary sequences produced by said hash function for a predetermined pattern of bits; and

computer readable program code devices configured to cause a computer to effect marking said breakpoint in said digital sequence when said predetermined pattern occurs.

37. A method for partitioning a digital sequence comprising:

performing a mathematical function that produces a statistically infrequent arrangement of n bytes on at least a portion of a digital sequence to produce binary sequences, said mathematical function that produces statistically infrequent arrangement of n bytes being combined with adjusting said mathematical function that produces statistically infrequent arrangement of n bytes based on a length of a current partition of said digital sequence to increase a likelihood of identifying a breakpoint in said current partition as a potential length of said current partition increases;

monitoring said binary sequences produced by the mathematical function that produces statistically infrequent arrangement of n bytes for a first predetermined pattern of bits; and

marking said breakpoint in the digital sequence when the first predetermined pattern is identified as occurring during the monitoring.

38. The method of claim 37, wherein said step of performing said mathematical function that produces statistically infrequent arrangement of n bytes function comprises a rolling hash function adapted to scan portions of said digital sequence.

39. The method of claim 37, further comprising:

determining a threshold restriction for said step of monitoring said binary sequences; and

increasing a probability of said marking of said breakpoint in said digital sequence.

40. The method of claim 39, wherein the increasing of said probability of said marking of said breakpoint in said digital sequence is carried out by the steps of:

utilizing a second predetermined numeric pattern for said step of monitoring said binary sequences; and

alternatively marking said breakpoint when said second predetermined numeric pattern occurs.

41. The method of claim 39, wherein the increasing of said probability of said marking of said breakpoint in said digital sequence is a function of some content portion of said sequence.

42. A computer program product comprising:

computer readable program code devices configured to cause a computer to effect performing a mathematical function that produces a statistically infrequent arrangement of n bytes on at least a portion of a digital sequence to produce binary sequences, said mathematical function that produces statistically infrequent arrangement of n bytes being combined with adjusting said mathematical function that produces statistically infrequent arrangement of n bytes based on a length of a current partition of said digital sequence to increase a likelihood of identifying a breakpoint in said current partition as a potential length of said current partition increases;

computer readable program code devices configured to cause a computer to effect monitoring said binary sequences produced by the mathematical function that produces statistically infrequent arrangement of n bytes for a first predetermined pattern of bits; and

computer readable program code devices configured to cause a computer to effect marking said breakpoint in the digital sequence when the first predetermined pattern is identified as occurring during the monitoring.

43. The computer program product of claim 42, wherein said performing said mathematical function that produces statistically infrequent arrangement of n bytes comprises performing a rolling hash function adapted to scan portions of said digital sequence.

44. The computer program product of claim 42, further comprising:

computer readable program code devices configured to cause a computer to effect determining a threshold restriction for said step of monitoring said binary sequences; and

computer readable program code devices configured to cause a computer to effect increasing a probability of said marking of said breakpoint in said digital sequence.

45. The computer program product of claim 44, wherein the increasing of said probability of said marking of said breakpoint in said digital sequence comprises:

utilizing a second predetermined numeric pattern for said step of monitoring said binary sequences; and

alternatively marking said breakpoint when said second predetermined numeric pattern occurs.

46. The computer program product of claim 42, wherein the increasing of said probability of said marking of said breakpoint in said digital sequence is a function of some content portion of said sequence.

47. A method for partitioning a digital sequence comprising:

performing a mathematical function that produces statistically infrequent arrangement of n bytes on at least a portion of a digital sequence to produce hash values, said mathematical function that produces statistically infrequent arrangement of n bytes being combined with adjusting said mathematical function that produces statistically infrequent arrangement of n bytes based on a length of a current partition of said digital sequence to increase a likelihood of identifying a breakpoint in said current partition as a potential length of said current partition increases;

monitoring said hash values produced by the mathematical function that produces statistically infrequent arrangement of n bytes for a numeric pattern selected from a range of numeric values; and

marking said breakpoint in the digital sequence when the numeric pattern occurs according to the monitoring.

48. A computer program product comprising:

computer readable program code devices configured to cause a computer to effect performing a mathematical function that produces statistically infrequent arrangement of n bytes on at least a portion of a digital sequence to produce hash values, said mathematical function that produces statistically infrequent arrangement of n bytes being combined with adjusting said mathematical function that produces statistically infrequent arrangement of n bytes based on a length of a current partition of said digital sequence to increase a likelihood of identifying a breakpoint in said current partition as a potential length of said current partition increases;

computer readable program code devices configured to cause a computer to effect monitoring hash values produced by the mathematical function that produces statistically infrequent arrangement of n bytes for a numeric pattern selected from a range of numeric values and

computer readable program code devices configured to cause a computer to effect marking said breakpoint in the digital sequence when the numeric pattern occurs according to the monitoring.

49. A method for partitioning a digital sequence comprising:

performing a mathematical function that produces statistically infrequent arrangement of n bytes on at least a portion of said digital sequence, the performing comprising;

indexing bytes from the digital sequence into an array of alternative pre-determined bit sequences;

performing a hash function on the pre-determined bit sequences, said hash function being combined with adjusting said hash function based on a length of a current partition of said digital sequence to increase a likelihood of identifying a breakpoint in said current partition as a potential length of said current partition increases;

monitoring the bit sequences produced by the said hash function for a first predetermined bit pattern; and

marking said breakpoint in said digital sequence when said first predetermined bit pattern occurs.

50. The method of claim 49, wherein said alternative pre-determined bit sequences are 32-bit sequences.

51. The method of claim 49, wherein said alternative pre-determined bit sequences are 32-bit sequences selected to normalize breakpoints around a certain data block size.

52. A computer program product comprising:

computer readable program code devices configured to cause a computer to effect performing a mathematical function that produces statistically infrequent arrangement of n bytes on at least a portion of said digital sequence, the computer readable program code devices comprising additional computer readable program code devices configured to cause a computer to effect;

indexing bytes from the digital sequence into an array of alternative pre-determined bit sequences;

performing a hash function on the pre-determined bit sequences, said has function being combined with adjusting said hash function based on a length of a current partition of said digital sequence to increase a likelihood of identifying a breakpoint in said current partition as a potential length of said current partition increases;

monitoring the bit sequences produced by the said hash function for a first predetermined bit pattern; and

marking said breakpoint in said digital sequence when said first predetermined bit pattern occurs.

53. A method for partitioning a digital sequence comprising:

processing at least a portion of a digital sequence to produce a transformation;

performing a rolling hash function on the transformation to produce binary sequences, said hash function being combined with adjusting said hash function based on a length of a current partition of said digital sequence to increase a likelihood of identifying a breakpoint in said current partition as a potential length of said current partition increases;

monitoring said binary sequences produced by the hash function for a pattern of bits; and

marking said breakpoint in the digital sequence when said first predetermined pattern occurs as determined by the monitoring.

54. The method of claim 53, wherein the processing to produce the transformation and the hash function are configured to produce a plurality of the breakpoints aggregating around a pre-determined data block size as opposed to a flat distribution of data block sizes.

55. The method of claim 53, wherein the transformation indexes the processed portion of the digital sequence into one of “

n”

pre-determined numbers or numeric sequences.

56. A computer program product comprising:

computer readable program code devices configured to cause a computer to effect processing at least a portion of a digital sequence to produce a transformation;

computer readable program code devices configured to cause a computer to effect performing a rolling hash function on the transformation to produce binary sequences, said hash function being combined with adjusting said hash function based on a length of a current partition of said digital sequence to increase a likelihood of identifying a breakpoint in said current partition as a potential length of said current partition increases;

computer readable program code devices configured to cause a computer to effect monitoring said binary sequences produced by the hash function for a pattern of bits; and

computer readable program code devices configured to cause a computer to effect marking said breakpoint in the digital sequence when said first predetermined pattern occurs as determined by the monitoring.

57. The computer program product of claim 56, wherein the processing to produce the transformation and the hash function are configured to produce a plurality of the breakpoints aggregating around a pre-determined data block size as opposed to a flat distribution of data block sizes.

58. The computer program product of claim 57, wherein the transformation indexes the processed portion of the digital sequence into one of “

n”

pre-determined numbers or numeric sequences.