US6101507A
Expired / Lapsed
US
⏱️ 0.0 years remaining
File comparison for data backup and file synchronization
Assignee: Micro Focus LLC
•
Filing: 1998-02-10
•
Granted: 2000-08-08
•
Expires: 2018-02-10
Abstract
Abstract File comparison employs a single function F to calculate a digital signature from data in a sliding window. The digital signature is both incrementally computable and position sensitive. In particular, F is computable without reprocessing each byte in the array when the window is advanced and facilitates detection of such changes as transposed bytes of data. The function F is defined by two qualities. First, for F(A+B), where A is an array, F(A+B)=F(A)+F(B). Second, given a concatenation operator "!" such that "0!A" indicates an array A with 0 inserted before A, the function F has the property that there is a function G such that F(0!A)=G(F(A'0)). Both polynomials and cyclic redundancy checks ("CRC") may be used as that class of function.
Inventors
- 👤 David Cane
- 👤 David Hirschman
- 👤 Philip Speare
- 👤 Lev Vaitzblit
- 👤 Howard Marson
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-05 10:53
CPC Classifications
G; G06; G06F; G06F11/00; G06F11/07; G06F11/14; G06F11/1446; G06F11/1448; G06F11/1451; G06F16/00; G06F16/10; G06F16/17; G06F16/178; G06F21/00; G06F21/60; G06F21/62; G06F21/6218; G06F2221/00; G06F2221/21; G06F2221/2107; H; H03; H03M; H03M13/00; H03M13/03; H03M13/05; H03M13/09; Y; Y10; Y10S; Y10S707/00; Y10S707/99951; Y10S707/99952; Y10S707/99953; Y10S707/99955
Claims Analysis
Total Claims: 21
Claim 1
Independent Claim
126 words
A system for comparing a first data set on a first storage device with a second data set on a second storage device, comprising: a transmission medium for transmitting data between the first storage device and the second storage device; a control program that generates a first digital signature from the first data set and a second digital signature from the second data set, the control program including a function F that incrementally calculates position sensitive first and second digital signatures, wherein said first data set is defined by a sliding indexed window and said incremental calculation comprises data leaving the window, data entering the window, and a previous digital signature; and a comparator for determining whether the first digital signature matches the second digital signature.
Claim 2
Independent Claim
126 words
A system for comparing a first data set on a first storage device with a second data set on a second storage device, comprising: a transmission medium for transmitting data between the first storage device and the second storage device; a control program that generates a first digital signature from the first data set and a second digital signature from the second data set, the control program including a function F that incrementally calculates position sensitive first and second digital signatures, wherein said first data set is defined by a sliding indexed window and said incremental calculation comprises data leaving the window, data entering the window, and a previous digital signature; and a comparator for determining whether the first digital signature matches the second digital signature.
Claim 3
Dependent Claim
15 words
The comparing system of claim 1 wherein polynomials are used to implement the function F.
Claim 4
Dependent Claim
50 words
The comparing system of claim 2 wherein the function F is a polynomial: F(A n )=Sum (a i+n * N.sup.(w-1-i)) modulo 2 64 for i=0 to w-1, for an array A starting at index position n with a window size of w, where a i is an element of A.
Claim 5
Dependent Claim
38 words
The comparing system of claim 3 wherein, if the window is advanced in A, then a new function is computed as: F(A n=1 )=N * F(A n )-a n * N w-1 +a n+w modulo 2 64 .
Claim 6
Dependent Claim
18 words
The comparing system of claim 1 wherein a cyclic redundancy check is used to implement the function F.
Claim 7
Independent Claim
109 words
A method for calculating a position sensitive digital signature from data on a first storage medium for comparison with a digital signature that represents data on a second storage medium, comprising the steps of: selecting the data in the first system with an indexed sliding window; applying a function F to the data within the window to generate the incremental position sensitive digital signature, wherein said function of F comprises input from data leaving said sliding indexed window, data entering said sliding indexed window, and a previously generated digital signature; and comparing the position sensitive digital signature with at least one digital signature representing data in the second system.
Claim 8
Independent Claim
109 words
A method for calculating a position sensitive digital signature from data on a first storage medium for comparison with a digital signature that represents data on a second storage medium, comprising the steps of: selecting the data in the first system with an indexed sliding window; applying a function F to the data within the window to generate the incremental position sensitive digital signature, wherein said function of F comprises input from data leaving said sliding indexed window, data entering said sliding indexed window, and a previously generated digital signature; and comparing the position sensitive digital signature with at least one digital signature representing data in the second system.
Claim 9
Dependent Claim
18 words
The method of claim 6 including the further step of employing a polynomials to implement the function F.
Claim 10
Dependent Claim
55 words
The method of claim 7 including the further step of employing the function: F(A n )=Sum (a i+n * N.sup.(w-1-i)) modulo 2 64 for i=0 to w-1, for an array A starting at index position n with a window size of w, where a i is an element of A, to implement the function F.
Claim 11
Dependent Claim
42 words
The method of claim 8 including the further step of, if the window is advanced in A, computing a new position sensitive digital signature as: F(A n=1 )=N * F(A n )-a n * N w-1 +a n+w module 2 64 .
Claim 12
Dependent Claim
20 words
The method of claim 6 including the further step of employing a cyclic redundancy check to implement the function F.
Claim 13
Independent Claim
189 words
A method for providing an incremental backup of a first memory in a second memory wherein a set of different files have previously been stored in the second memory, comprising the steps of: selecting a file from the first memory for examination; generating a signature from a portion of the file defined by a sliding indexed window; comparing the generated signature with signatures generated from the set of previously stored files having different filenames; determining the closest matching previously stored file, relative to the file under examination, where the stored file and the file under examination have different filenames, by identifying at least some portions of the stored file and the file under examination which are different, wherein said determining comprises applying a function F to the data within said sliding indexed window to generate an incremental position sensitive digital signature, wherein said function of F comprises input from data leaving said sliding indexed window, data entering said sliding indexed window, and a previously generated digital signature; and storing the portions of the file under examination identified as being different from the closest matching file in the second memory.
Claim 14
Independent Claim
189 words
A method for providing an incremental backup of a first memory in a second memory wherein a set of different files have previously been stored in the second memory, comprising the steps of: selecting a file from the first memory for examination; generating a signature from a portion of the file defined by a sliding indexed window; comparing the generated signature with signatures generated from the set of previously stored files having different filenames; determining the closest matching previously stored file, relative to the file under examination, where the stored file and the file under examination have different filenames, by identifying at least some portions of the stored file and the file under examination which are different, wherein said determining comprises applying a function F to the data within said sliding indexed window to generate an incremental position sensitive digital signature, wherein said function of F comprises input from data leaving said sliding indexed window, data entering said sliding indexed window, and a previously generated digital signature; and storing the portions of the file under examination identified as being different from the closest matching file in the second memory.
Claim 15
Dependent Claim
25 words
The method of claim 11 including the further step of creating a match count table with a row corresponding to each respective previously stored file.
Claim 16
Dependent Claim
31 words
The method of claim 12 including the further step of comparing the generated signature with signatures generated for N blocks of the previously stored files, where N is a predetermined integer.
Claim 17
Independent Claim
232 words
A method for determining a minimum set of data compression units for restoring a file from a base copy and a plurality of revision elements, comprising the steps of: selecting the base copy and revision elements required to build the file; sorting the selected base copy and revision elements into a list with the most recently generated revision element at the list head and the base copy at the list tail; reading information for each selected revision element into an array with five columns: chunk, operation, data offset, data length, and target offset; creating an output array indicative of the reconstructed file with five columns: revision element pointer, chunk, data offset, data length, and target offset; calling a recursive function for the most recent revision, requesting data offset 0 and the final file length, and passing in target offset 0, the recursive function iterating through the array columns and comparing the requested data offset and length with the target of offset and data length of each item, and in the case of a match, writing an entry into the output array if the array item is a data operation; optimizing, via a block filter, an optimal set of array elements wherein elements not affecting said output array are ignored; and sorting the output array by revision element and chunk; and transmitting the array followed by the transmission blocks for each data block.
Claim 18
Independent Claim
232 words
A method for determining a minimum set of data compression units for restoring a file from a base copy and a plurality of revision elements, comprising the steps of: selecting the base copy and revision elements required to build the file; sorting the selected base copy and revision elements into a list with the most recently generated revision element at the list head and the base copy at the list tail; reading information for each selected revision element into an array with five columns: chunk, operation, data offset, data length, and target offset; creating an output array indicative of the reconstructed file with five columns: revision element pointer, chunk, data offset, data length, and target offset; calling a recursive function for the most recent revision, requesting data offset 0 and the final file length, and passing in target offset 0, the recursive function iterating through the array columns and comparing the requested data offset and length with the target of offset and data length of each item, and in the case of a match, writing an entry into the output array if the array item is a data operation; optimizing, via a block filter, an optimal set of array elements wherein elements not affecting said output array are ignored; and sorting the output array by revision element and chunk; and transmitting the array followed by the transmission blocks for each data block.
Claim 19
Dependent Claim
34 words
The method of claim 14 wherein the recursive function operates by iterating through the array items, and comparing the requested data offset and length with the target offset and data length of each item.
Claim 20
Dependent Claim
68 words
The method of claim 15 wherein, if a match or partial match is found, either writing an entry into the output array item or calling the recursive function again for the next list element with the offset equal to the item's data offset minus the target offset of each item plus the requested data offset, and the length equal to the remaining requested length and the item length.
Claim 21
Dependent Claim
29 words
The method of claim 16 wherein, if a partial match was found, incrementing the requested data offset and target offset and decrementing the requested length and continuing to iterate.
References Cited (Backward Citations)
US4897785A
Cited
US5454099A
Cited
US5276867A
Cited
US5276860A
Cited
US5479654A
Cited
US5893117A
Cited
US5210866A
Cited
US5428629A
Cited
US5438661A
Cited
US5347652A
Cited
US5214696A
Cited
US5263154A
Cited
US5642496A
Cited
US5721907A
Cited
US5668897A
Cited
US5647017A
Cited
US5818955A
Cited
US5848422A
Cited
US5737763A
Cited
US5628012A
Cited
US5900000A
Cited
US5720026A
Cited
US5745906A
Cited
US5893113A
Cited
US5909677A
Cited
US5881292A
Cited
US5802521A
Cited
US5794254A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-08-08 | 2004-02-07 | 2004-08-08 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-08-08 | 2008-02-07 | 2008-08-08 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-08-08 | 2012-02-07 | 2012-08-08 | $7700.00 | Window Closed / Lapsed |