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

• US 6,810,398 B2
• Filed: 02/05/2001
• Issued: 10/26/2004
• Est. Priority Date: 11/06/2000
• Status: Expired due to Term

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: Avamar Technologies, Inc. (Dell Technologies Inc.)
• Inventors: Moulton, Gregory Hagan
• Primary Examiner(s): Wassum, Luke S
• Application Number:
  US09/777,149
• Publication Number:
  US 20020152218A1
• Time in Patent Office: 1,359 Days
• Field of Search: 707/6
• 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;

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

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

establishing at least a second predetermined numeric pattern found in a range of numeric values for said step of monitoring when said threshold restriction is met, wherein said second predetermined numeric pattern is a bit pattern and is a subset of said first predetermined numeric pattern; and

alternatively marking said breakpoint in said digital seguence when said second predetermined numeric pattern occurs.

2. The method of claim 1 wherein said step of performing said hash function is carried out by means of a rolling hash function, the rolling hash function scanning portions of said digital sequence and progressively reducing an impact of more distant bits in said digital sequence.

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

4. The method of claim 1 wherein said step of performing said hash function is carried out by means of a rolling hash function.

5. The method of claim 4 wherein said rolling hash function comprises a 32-bit hash function.

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

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

8. The method of claim 7 wherein said plurality of endmost bits comprises eleven bits.

9. The method of claim 8 wherein said eleven bits are “

0”

.

10. The method of claim 1 wherein said first predetermined numeric pattern comprises a consecutive sequence of eleven bits and said second predetermined numeric pattern comprises ten of said eleven bits.

11. The method of claim 10 wherein said first predetermined numeric pattern comprises eleven consecutive “

0”

'"'"'s and said second predetermined numeric pattern comprises ten consecutive “

0”

'"'"'s.

12. 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.

13. The method of claim 12 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.

14. The method of claim 12 wherein said step of increasing said probability of said marking of said breakpoint in said digital sequence is a function of at least a length of a current portion of said digital sequence.

15. The method of claim 12 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.

16. The method of claim 12 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.

17. The method of claim 1 wherein said hash function is selected to produce preferential hashsums that do not uniformly cover the range of possible output values.

18. The method of claim 17, wherein said hash function selected to produce preferential hashsums uses an array of predetermined values indexed by the digital sequence to generate a distribution of hash values having a level of indirection from direct influence of the digital sequence.

19. The method of claim 1 wherein said hash function is modified dynamically during the execution of said hash function.

20. The method of claim 1 wherein said hash function includes the relative or absolute value of the current location as an input value in said hash function resulting in hash values that are affected by the relative or absolute value of the current location.

21. A computer program product comprising:

a computer usable medium having computer readable code embodied therein for partitioning a digital sequence comprising;

computer readable program code devices configured to cause a computer to effect performing a hash function on at least a portion of said digital sequence;

computer readable program code devices configured to cause a computer to effect monitoring hash values produced by said hash function for a first predetermined numeric pattern found in a range of numeric values;

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

computer readable program code devices configured to cause a computer to effect determining a threshold restriction for said step of monitoring said hash values;

computer readable program code devices configured to cause a computer to effect establishing at least a second predetermined numeric pattern found in a range of numeric values for said step of monitoring when said threshold restriction is met, wherein said second predetermined numeric pattern is a bit pattern and is a subset of said first predetermined numeric pattern; and

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

22. The computer program product of claim 21 wherein said computer readable program code devices configured to cause a computer to effect performing said hash function is carried out by means of a rolling hash function, the rolling hash function scanning portions of said digital sequence and progressively reducing the impact of more distant bits in said digital sequence.

23. The computer program product of claim 21 wherein said first predetermined numeric pattern is a bit pattern.

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

25. The computer program product of claim 24 wherein said rolling hash function comprises a 32-bit hash function using an array of predetermined values indexed by the said digital sequence to generate a distribution of hash values.

26. The computer program product of claim 21 wherein said first predetermined numeric pattern comprises a consecutive sequence of bits.

27. The computer program product of claim 26 wherein said consecutive sequence of bits comprises a plurality of endmost bits.

28. The computer program product of claim 27 wherein said plurality of endmost bits comprises eleven bits.

29. The computer program product of claim 28 wherein said eleven bits are “

0”

.

30. The computer program product of claim 21 wherein said first predetermined numeric pattern comprises a consecutive sequence of eleven bits and said second predetermined numeric pattern comprises ten of said eleven bits.

31. The computer program product of claim 30 wherein said first predetermined numeric pattern comprises eleven consecutive “

0”

'"'"'s and said second predetermined numeric pattern comprises ten “

0”

'"'"'s.

32. The computer program product of claim 21 further comprising:

computer readable program code devices configured to cause a computer to effect determining a threshold restriction for said step of monitoring said hash values; 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.

33. The computer program product of claim 32 wherein said computer readable program code devices configured to cause a computer to effect increasing said probability of said marking of said breakpoint in said digital sequence is a function of at least a desired chunk size.

34. The computer program product of claim 32 wherein said computer readable program code devices configured to cause a computer to effect increasing said probability of said marking of said breakpoint in said digital sequence is a function of at least a length of a current portion of said digital sequence.

35. The computer program product of claim 32 wherein said computer readable program code devices configured to cause a computer to effect increasing said probability of said marking of said breakpoint in said digital sequence is carried out by:

computer readable program code devices configured to cause a computer to effect utilizing a second predetermined numeric pattern found in a range of numeric values for said step of monitoring said hash values; and

computer readable program code devices configured to cause a computer to effect alternatively marking said breakpoint when said second predetermined numeric pattern occurs.

36. 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;

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

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

establishing at least a second predetermined numeric pattern for said step of monitoring when said threshold restriction is met; and

alternatively marking said breakpoint in said digital sequence when said second predetermined numeric pattern occurs, wherein said second predetermined numeric pattern is a bit pattern and a subset of said first predetermined numeric pattern.

37. The method of claim 36 wherein said first predetermined numeric pattern is a bit pattern.

38. The method of claim 36 wherein said step of performing said hash function is carried out by means of a rolling hash function.

39. The method of claim 38 wherein said rolling hash function comprises a 32-bit hash function.

40. The method of claim 36 wherein said first predetermined numeric pattern comprises a consecutive sequence of bits.

41. The method of claim 40 wherein said consecutive sequence of bits comprises a plurality of endmost bits.

42. The method of claim 41 wherein said plurality of endmost bits comprises eleven bits.

43. The method of claim 42 wherein said eleven bits are “

0”

.

44. The method of claim 36 wherein said first predetermined numeric pattern comprises a consecutive sequence of eleven bits and said second predetermined numeric pattern comprises ten of said eleven bits.

45. The method of claim 44 wherein said first predetermined numeric pattern comprises eleven consecutive “

0”

'"'"'s and said second predetermined numeric pattern comprises ten consecutive “

0”

'"'"'s.

46. The method of claim 36 further including increasing a probability of said marking of said breakpoint in said digital sequence, 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.

47. A computer program product comprising:

a computer usable medium having computer readable code embodied therein for partitioning a digital sequence comprising;

computer readable program code devices configured to cause a computer to effect performing a hash function on at least a portion of said digital sequence;

computer readable program code devices configured to cause a computer to effect monitoring hash values produced by said hash function for a first predetermined numeric pattern;

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

computer readable program code devices configured to cause a computer to effect determining a threshold restriction for said step of monitoring said hash values;

computer readable program code devices configured to cause a computer to effect establishing at least a second predetermined numeric pattern for said step of monitoring when said threshold restriction is met; and

computer readable program code devices configured to cause a computer to effect alternatively marking said breakpoint in said digital sequence when said second predetermined numeric pattern occurs, wherein said second predetermined numeric pattern is a bit pattern and a subset of said first predetermined numeric pattern.

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

49. The computer program product of claim 48 wherein said rolling hash function comprises a 32-bit hash function.

50. The computer program product of claim 47 wherein said first predetermined numeric pattern comprises a consecutive sequence of bits.

51. The computer program product of claim 50 wherein said consecutive sequence of bits comprises a plurality of endmost bits.

52. The computer program product of claim 51 wherein said plurality of endmost bits comprises eleven bits.

53. The computer program product of claim 52 wherein said eleven bits are “

0”

.

54. The computer program product of claim 47 wherein said first predetermined numeric pattern comprises a consecutive sequence of eleven bits and said second predetermined numeric pattern comprises ten of said eleven bits.

55. The computer program product of claim 54 wherein said first predetermined numeric pattern comprises eleven consecutive “

0”

'"'"'s and said second predetermined numeric pattern comprises ten “

0”

'"'"'s.

56. The computer program product of claim 47 further comprising:

computer readable program code devices configured to cause a computer to effect determining a threshold restriction for said step of monitoring said hash values; 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.

57. The computer program product of claim 56 wherein said computer readable program code devices configured to cause a computer to effect increasing said probability of said marking of said breakpoint in said digital sequence is a function of at least a desired chunk size.

58. The computer program product of claim 56 wherein said computer readable program code devices configured to cause a computer to effect increasing said probability of said marking of said breakpoint in said digital sequence is a function of at least a length of a current portion of said digital sequence.

59. The computer program product of claim 56 wherein said computer readable program code devices configured to cause a computer to effect increasing said probability of said marking of said breakpoint in said digital sequence is carried out by:

computer readable program code devices configured to cause a computer to effect utilizing a second predetermined numeric pattern for said step of monitoring said hash values; and

computer readable program code devices configured to cause a computer to effect alternatively marking said breakpoint when said second predetermined numeric pattern occurs.

60. 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;

wherein said hash function is selected to produce preferential hashsums that do not uniformly cover a range of possible output values.

61. The method of claim 60, wherein said hash function selected to produce preferential hashsums uses an array of predetermined values indexed by the digital sequence to generate a distribution of hash values having a level of indirection from direct influence of the digital sequence.

62. The method of claim 60 wherein said step of performing said hash function is carried out by means of a rolling hash function, the rolling hash function scanning portions of said digital sequence and progressively reducing an impact of more distant bits in said digital sequence.

63. The method of claim 60 wherein said first predetermined numeric pattern is a bit pattern.

64. The method of claim 60 wherein said first predetermined numeric pattern comprises a consecutive sequence of bits.

65. The method of claim 64 wherein said consecutive sequence of bits comprises a plurality of endmost bits.

66. The method of claim 64 wherein said plurality of endmost bits comprises eleven bits.

67. A method for partitioning a digital sequence comprising:

performing a hash function on at least a portion of said digital sequence, wherein said hash function is modified dynamically during the execution of said hash function;

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.

68. The method of claim 67 wherein said step of performing said hash function is carried out by means of a rolling hash function, the rolling hash function scanning portions of said digital sequence and progressively reducing an impact of more distant bits in said digital sequence.

69. The method of claim 67 said first predetermined numeric pattern is a bit pattern.

70. The method of claim 67 wherein said first predetermined numeric pattern comprises a consecutive sequence of bits.

71. The method of claim 70 wherein said consecutive sequence of bits comprises a plurality of endmost bits.

72. The method of claim 71 wherein said plurality of endmost bits comprises eleven bits.

73. 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;

wherein said hash function includes the relative or absolute value of the current location as an input value in said hash function resulting in hash values that are affected by the relative or absolute value of the current location.

75. The method of claim 73 wherein said first predetermined numeric pattern is a bit pattern.

76. The method of claim 73 wherein said first predetermined numeric pattern comprises a consecutive sequence of bits.

77. The method of claim 76 wherein said consecutive sequence of bits comprises a plurality of endmost bits.

78. The method of claim 77 wherein said plurality of endmost bits comprises eleven bits.

74. The method of claim wherein said step of performing said hash function is carried out by means of a rolling hash function, the rolling hash function scanning portions of said digital sequence and progressively reducing an impact of more distant bits in said digital sequence.