Source: http://www.google.com/patents/US8117173?dq=%E2%80%9Cconfiguration+using+structure+and+rules+to+provide+a+user+interface.%E2%80%9D&ei=ANUpTrT8BsTm0QHVpJX-Cg
Timestamp: 2016-07-30 06:27:30
Document Index: 330745837

Matched Legal Cases: ['Application No. 2005201386', 'Application No. 200510055107', 'Application No. 200510108958', 'Application No. 200510055107', 'Application No. 200510108958', 'Application No. 200510055107', 'Application No. 05108288', 'Application No. 05', 'Application No. 05102664', 'Application No. 05108288', 'Application No. 167467', 'Application No. 2005', 'Application No. 2005', 'Application No. 2005', 'Application No. 538839', 'Application No. 1', 'Application No. 05108288', 'Application No. 20051045759', 'Application No. 2005105759', 'Application No. 200501089', 'Application No. 94107741']

Patent US8117173 - Efficient chunking algorithm - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inPatentsThe present invention provides a method for chunking an object. The method is arranged to provide efficient chunking of objects such that objects can be efficiently updated between a remote machine and a local machine over a network. The chunking algorithm is applicable in networked application such...http://www.google.com/patents/US8117173?utm_source=gb-gplus-sharePatent US8117173 - Efficient chunking algorithmAdvanced Patent SearchPublication numberUS8117173 B2Publication typeGrantApplication numberUS 12/431,483Publication dateFeb 14, 2012Filing dateApr 28, 2009Priority dateApr 15, 2004Fee statusPaidAlso published asUS20060047855, US20090271528Publication number12431483, 431483, US 8117173 B2, US 8117173B2, US-B2-8117173, US8117173 B2, US8117173B2InventorsYuri Gurevich, Nikolaj S. Bjorner, Dan TeodosiuOriginal AssigneeMicrosoft CorporationExport CitationBiBTeX, EndNote, RefManPatent Citations (195), Non-Patent Citations (145), Referenced by (10), Classifications (7), Legal Events (2) External Links: USPTO, USPTO Assignment, EspacenetEfficient chunking algorithm
US 8117173 B2Abstract
The present invention provides a method for chunking an object. The method is arranged to provide efficient chunking of objects such that objects can be efficiently updated between a remote machine and a local machine over a network. The chunking algorithm is applicable in networked application such as file synchronization using remote differential compression (RDC) techniques. The chunking algorithm provides enhanced efficiencies by locating chunk boundaries around local maxima.
1. A method for partitioning an object into chunks, comprising:
calculating fingerprint values at each position within the object;
evaluating an offset associated with each possible cut-point location;
evaluating the fingerprint values located within a horizon around each position within the object;
identifying a cut-point location in response to the evaluated fingerprint values; and
partitioning the object into chunks based on the identified cut-point locations.
2. The method of claim 1, wherein calculating the fingerprint values at each position within the object further comprises applying a fingerprint function to object data contained within a small window around each position.
3. The method of claim 2, wherein applying the fingerprint function further comprises using at least one of: a Rabin polynomial; an Adler hash; and a random hash with cyclic shifting.
4. The method of claim 2, further comprising adjusting the size of the small window based on at least one of: a data type associated with the object; the size of the object; an environmental constraint; and a usage model associated with the object.
5. The method of claim 2, wherein evaluating the fingerprint values located within the horizon further comprises: applying a mathematical function on fingerprint values; and identifying a cut-point location at a given offset when the mathematical function attains a pre-determined value at a given offset and attains other pre-determined values at a predetermined number of previous offsets.
6. The method of claim 5, wherein the mathematical function comprises at least one of: a predicate; and a function that partitions fingerprint values into a suitable small domain.
7. The method of claim 2, wherein applying the mathematical function further comprises determining a local maximum fingerprint value within the horizon.
8. The method of claim 7, further comprising: allocating a first flag array and a second flag array of length equal to the horizon and initializing the flag arrays to Boolean false; allocating a first fingerprint array and a second fingerprint array of length equal to the horizon and initializing the fingerprint array to zero; allocating a first offset array and a second offset array of length equal to the horizon and initializing the offset arrays to zero; initializing an index l to zero; initializing an index k to zero; and initializing a current offset into the object to zero.
9. The method of claim 8, further comprising: traversing the object in intervals batches of size h and within each interval: setting the value of the first index into the first flag array to true; setting the value of the first index into the first offset array to the last offset of the current interval batch; setting the value of the first index into the fingerprint arrays to the fingerprint at the last offset of the current interval; and decrementing the offset to the last position of the current interval.
10. The method of claim 9, further comprising: as long as the current value of the last offset of the current interval is greater than the value of the second offset array at index l plus the value of h, then updating the value of the first flag array at position k to false provided the fingerprint value at the current value of the last offset is equal to the value of the first fingerprint array at position k; if the fingerprint value at the current value of the last offset is greater than the value of the first fingerprint array at position k, then incrementing k and setting the value of the first offset array at index k to the value of the current last offset; setting the value of the first flag array at index k to true, and setting the value of the first hash array at index k to the current value of the last offset; and decrementing the offset to the last position of the current interval.
11. The method of claim 9, further comprising: as long as the current value of the offset is not less than the offset to the beginning of the current interval then updating the value of the first flag array at position k to false, provided the fingerprint value at the current value of the last offset is equal to the value of the first fingerprint array at position k; if the fingerprint value at the current value of the last offset is greater than the value of the first fingerprint array at position k, then incrementing k and setting the value of the first offset array at index k to the value of the current last offset, setting the value of the first flag array at index k to true, and setting the value of the first hash array at index k to the current value of the last offset; if the value of the second fingerprint array at index l is no larger than the fingerprint value at the current value of the last offset, then setting the value of the second flag array at index l to false and decrementing the offset to the last position of the current interval.
12. The method of claim 11, further comprising updating the value of the first flag array at index k to false if it is already false or when there exists an index j between 0 and l, inclusive, where the value of the second offset array at index j plus the value of h is at least as big as the value of the first offset array at index k, and the value of the second fingerprint array at index j is at least the value of the first fingerprint array at index k.
13. The method of claim 12, further comprising setting the value of the second offset array at index l to a cut-point if the value of the second flag array at position l is true.
14. The method of claim 13, further comprising exchanging the reference to the first and second offset, fingerprint arrays, and flag arrays before the next interval is processed.
15. The method of claim 7, further comprising: allocating a flag array of length equal to the horizon and initializing the flag array to Boolean false; allocating a fingerprint array of length equal to the horizon and initializing the fingerprint array to zero; allocating an offset array of length equal to the horizon and initializing the offset array to zero; initializing a min index to zero; initializing a max index to zero; and initializing a current offset into the object to zero.
16. The method of claim 1, further comprising adjusting the size of the horizon based on at least one of: a data type associated with the object; the size of the object; an environmental constraint; and a usage model associated with the object.
17. The method of claim 1, wherein evaluating the fingerprint values located within the horizon, further comprises applying a mathematical function to the fingerprint values and identifying a cut-point location when the mathematical function is satisfied.
18. The method of claim 17, wherein applying the mathematical function further comprises: using a predicate to map fingerprint values into Boolean values; partitioning fingerprint values into a small domain; determining a maximum value within the horizon; determining a minimum value within the horizon; evaluating differences between fingerprint values within the horizon; and summing fingerprint values within the horizon.
19. A computer-readable storage medium having computer executable instructions for partitioning an object into chunks, comprising:
20. The computer-readable storage medium of claim 19, wherein calculating the fingerprint values at each position within the object further comprises applying a fingerprint function to object data contained within a small window around each position.
This application is a continuation of and claims priority to prior U.S. application Ser. No. 10/844,893, abandoned, filed on May 13, 2004, and is also a continuation of and claims priority to prior U.S. Application Ser. No. 10/825,735, U.S. Pat. No. 7,555,531, filed Apr. 15, 2004. Both applications are hereby incorporated by reference
The present invention relates generally to a method of chunking an object. More particularly, the present invention relates to a system and method for efficient chunking of objects such that objects can be efficiently updated between a remote machine and a local machine over a network. The chunking algorithm is applicable in networked application such as file synchronization using remote differential compression techniques. The chunking algorithm provides enhanced efficiencies by locating chunk boundaries around local maxima.
Briefly stated, the present invention is related to a method and system for chunking an object. A method and system are arranged to provide efficient chunking of objects such that objects can be efficiently updated between a remote machine and a local machine over a network. The chunking algorithm is applicable in networked application such as file synchronization using remote differential compression (RDC) techniques. The chunking algorithm provides enhanced efficiencies by locating chunk boundaries around local maxima.
FIGS. 10A and 10B are diagrams of another example instruction code for another example chunking procedure, arranged according to at least one aspect of the present invention.
FIG. 11 is a diagram of example instruction code for an example chunking procedure.
The present invention is described in the context of local and remote computing devices (or “devices”, for short) that have one or more commonly associated objects stored thereon. The terms “local” and “remote” refer to one instance of the method. However, the same device may play both a “local” and a “remote” role in different instances. Remote Differential Compression (RDC) methods are used to efficiently update the commonly associated objects over a network with limited-bandwidth. When a device having a new copy of an object needs to update a device having an older copy of the same object, or of a similar object, the RDC method is employed to only transmit the differences between the objects over the network. An example described RDC method uses (1) a recursive approach for the transmission of the RDC metadata, to reduce the amount of metadata transferred for large objects, and (2) a local maximum-based chunking method to increase the precision associated with the object differencing such that bandwidth utilization is minimized. Some example applications that benefit from the described RDC methods include: peer-to-peer replication services, file-transfer protocols such as SMB, virtual servers that transfer large images, email servers, cellular phone and PDA synchronization, database server replication, to name just a few.
FIG. 1 is a diagram illustrating an example operating environment for the present invention. As illustrated in the figure, devices are arranged to communicate over a network. These devices may be general purpose computing devices, special purpose computing devices, or any other appropriate devices that are connected to a network. The network 102 may correspond to any connectivity topology including, but not limited to: a direct wired connection (e.g., parallel port, serial port, USB, IEEE 1394, etc), a wireless connection (e.g., IR port, Bluetooth port, etc.), a wired network, a wireless network, a local area network, a wide area network, an ultra-wide area network, an internet, an intranet, and an extranet.
In an example interaction between device A (100) and device B (101), different versions of an object are locally stored on the two devices: object OA on 100 and object OB on 101. At some point, device A (100) decides to update its copy of object OA with the copy (object OB) stored on device B (101), and sends a request to device B (101) to initiate the RDC method. In an alternate embodiment, the RDC method could be initiated by device B (101).
Computing device 200 also contains communications connection(s) 216 that allow the device to communicate with other computing devices 218, such as over a network. Communications connection(s) 216 is an example of communication media. Communication media typically embodies computer readable instructions, data structures, program modules or other data in a modulated data signal such as a carrier wave or other transport mechanism and includes any information delivery media. The term “modulated data signal” means a signal that has one or more of its characteristics set or changed in such a manner as to encode information in the signal. By way of example, and not limitation, communication media includes wired media such as a wired network or direct-wired connection, and wireless media such as acoustic, RF, microwave, satellite, infrared and other wireless media. The term computer readable media as used herein includes both storage media and communication media.
1. Device A sends device B a request to transfer Object OB using the RDC protocol. In an alternate embodiment, device B initiates the transfer; in this case, the protocol skips step 1 and starts at step 2 below. 2. Device A partitions Object OA into chunks 1-k, and computes a signature SigAi and a length (or size in bytes) LenAi for each chunk 1 . . . k of Object OA. The partitioning into chunks will be described in detail below. Device A stores the list of signatures and chunk lengths ((SigA1, LenA1) . . . (SigAk, LenAk)). 3. Device B partitions Object OB into chunks 1-n, and computes a signature SigBi and a length LenBi for each chunk 1 . . . n of Object OB. The partitioning algorithm used in step 3 must match the one in step 2 above. 4. Device B sends a list of its computed chunk signatures and chunk lengths ((SigB1, LenB1) . . . (SigBn, LenBn)) that are associated with Object OB to device A. The chunk length information may be subsequently used by device A to request a particular set of chunks by identifying them with their start offset and their length. Because of the sequential nature of the list, it is possible to compute the starting offset in bytes of each chunk Bi by adding up the lengths of all preceding chunks in the list.
In another embodiment, the list of chunk signatures and chunk lengths is compactly encoded and further compressed using a lossless compression algorithm before being sent to device A. 5. Upon receipt of this data, device A compares the received signature list against the signatures SigA1 . . . . SigAk that it computed for Object OA in step 2, which is associated with the old version of the content. 6. Device A sends a request to device B for all the chunks whose signatures received in step 4 from device B failed to match any of the signatures computed by device A in step 2. For each requested chunk Bi, the request comprises the chunk start offset computed by device A in step 4 and the chunk length. 7. Device B sends the content associated with all the requested chunks to device A. The content sent by device B may be further compressed using a lossless compression algorithm before being sent to device A. 8. Device A reconstructs a local copy of Object OB by using the chunks received in step 7 from device B, as well as its own chunks of Object OA that matched signatures sent by device B in step 4.
The order in which the local and remote chunks are rearranged on device A is determined by the list of chunk signatures received by device A in step 4. The partitioning steps 2 and 3 may occur in a data-dependent fashion that uses a fingerprinting function that is computed at every byte position in the associated object (OA and OB, respectively). For a given position, the fingerprinting function is computed using a small data window surrounding that position in the object; the value of the fingerprinting function depends on all the bytes of the object included in that window. The fingerprinting function can be any appropriate function, such as, for example, a hash function or a Rabin polynomial.
After the reconstruction step is completed by device A, Object OA can be deleted and replaced by the copy of Object OB that was reconstructed on device A. In other embodiments, device A may keep Object OA around for potential “reuse” of chunks during future RDC transfers.
4.2. Device A performs a recursive chunking of its signature and chunk length list ((SigA1, LenA1) . . . (SigAk, LenAk)) into recursive signature chunks, obtaining another list of recursive signatures and recursive chunk lengths ((RSigA1, RLenA1) . . . (RSigAs, RLenAs)), where s<<k. 4.3. Device B recursively chunks up the list of signatures and chunk lengths ((SigB1, LenB1) . . . (SigBn, LenBn)) to produce a list of recursive signatures and recursive chunk lengths ((RSigB1, RLenB1) . . . (RSigBr, RLenBr)), where r<<n. 4.4. Device B sends an ordered list of recursive signatures and recursive chunk lengths ((RSigB1, RLenB1) . . . (RSigBr, RLenBr)) to device A. The list of recursive chunk signatures and recursive chunk lengths is compactly encoded and may be further compressed using a lossless compression algorithm before being sent to device A. 4.5. Device A compares the recursive signatures received from device B with its own list of recursive signatures computed in Step 4.2. 4.6. Device A sends a request to device B for every distinct recursive signature chunk (with recursive signature RSigBk) for which device A does not have a matching recursive signature in its set (RSigA1 . . . RSigAs). 4.7. Device B sends device A the requested recursive signature chunks. The requested recursive signature chunks may be further compressed using a lossless compression algorithm before being sent to device A. 4.8. Device A reconstructs the list of signatures and chunk information ((SigB1, LenB1) . . . (SigBn, LenBn)) using the locally matching recursive signature chunks, and the recursive chunks received from device B in Step 4.7. After step 4.8 above is completed, execution continues at step 5 of the basic RDC protocol described above, which is illustrated in FIG. 3A.
In steps 501 and 551, both the local device A and remote device B independently compute recursive fingerprints of their signature and chunk length lists ((SigA1,LenA1), . . . (SigAk,LenAk)) and ((SigB1,LenB1), . . . (SigBn,LenBn)), respectively, that had been computed in steps 402/403 and 452/453, respectively. In steps 502 and 552 the devices divide their respective signature and chunk length lists into recursive chunks, and in steps 503 and 553 compute recursive signatures (e.g., SHA) for each recursive chunk, respectively.
The local device receives and decompresses the requested recursive chunk data at step 512. Using the local copy of the signature and chunk length list ((SigA1,LenA1), . . . (SigAk,LenAk)) and the received recursive chunk data, the local devices reassembles a local copy of the signature and chunk length list ((SigB1,LenB1), . . . (SigBk,LenBn)) at step 513. Execution then continues at step 405 in FIG. 4A.
FIG. 7 is a diagram illustrating the interaction of a client and server application using an example RDC procedure that is arranged according to at least one aspect of the present invention. The original file on both the server and the client contained text “The quick fox jumped over the lazy brown dog. The dog was so lazy that he didn't notice the fox jumping over him.”
At a subsequent time, the file on the server is updated to: “The quick fox jumped over the lazy brown dog. The brown dog was so lazy that he didn't notice the fox jumping over him.”
As described previously, the client periodically requests the file to be updated. The client and server both chunk the object (the text) into chunks as illustrated. On the client, the chunks are: “The quick fox jumped”, “over the lazy brown dog.”, “The dog was so lazy that he didn't notice”, and “the fox jumping over him.”; the client signature list is generated as: SHA11, SHA12, SHA11, and SHA14. On the server, the chunks are: “The quick fox jumped”, “over the lazy brown dog.”, “The brown dog was”, “so lazy that he didn't notice”, and “the fox jumping over him.”; the server signature list is generated as: SHA21, SHA22, SHA23, SHA24, and SHA25.
The server transmits the signature list (SHA21-SHA25) using a recursive signature compression technique as previously described. The client recognizes that the locally stored signature list (SHA11-SHA14) does not match the received signature list (SHA21-SHA25), and requests the missing chunks 3 and 4 from the server. The server compresses and transmits chunks 3 and 4 (“The brown dog was”, and “so lazy that he didn't notice”). The client receives the compressed chunks, decompresses them, and updates the file as illustrated in FIG. 7.
(S2) Σchunk_length, where (signature, chunk_length)∈ Signatures from B,
and signature ∉ Signatures from A
1. Slack: The number of bytes required for chunks to reconcile between file differences. Consider sequences s1, s2, and s3, and form the two sequences s1s3, s2s3 by concatenation. Generate the chunks for those two sequences Chunks 1, and Chunks2. If Chunks1′ and Chunks2′ are the sums of the chunk lengths from Chunks1 and Chunks2, respectively, until the first common suffix is reached, the slack in bytes is given by the following formula:
All chunking algorithms use a fingerprinting function, or hash, that depends on a small window, that is, a limited sequence of bytes. The execution time of the hash algorithms used for chunking is independent of the hash window size when those algorithms are amenable to finite differencing (strength reduction) optimizations. Thus, for a hash window of size k it is should be easy (require only a constant number of steps) to compute the hash #[b1, . . . , bk-1,bk] using b0, bk, and #[b0,b1, . . . , bk-1] only. Various hashing functions can be employed such as hash functions using Rabin polynomials, as well as other hash functions that appear computationally more efficient based on tables of pre-computed random numbers.
where 1=k % 64 and u=64−1 In still another example, other shifting methods may be employed to provide fingerprinting. Straight forward cyclic shifting produces a period of limited length, and is bounded by the size of the hash value. Other permutations have longer periods. For instance, the permutation given by the cycles (1 2 3 0)(5 6 7 8 9 10 11 12 13 14 4)(16 17 18 19 20 21 15)(23 24 25 26 22)(28 29 27)(31 30) has a period of length 4*3*5*7*11=4620. The single application of this example permutation can be computed using a right shift followed by operations that patch up the positions at the beginning of each interval.
CutPoint(hash)≡0==(hash&((1<<c)−1)),
C=m+2c A rough estimate of the expected slack is obtained by considering streams s1s3 and s2s3. Cut points in s1 and s2 may appear at arbitrary places. Since the average chunk length is C=m+2c, about (2c/C)2 of the last cut-points in s1 and S2 will be beyond distance m. They will contribute to slack at around 2c. The remaining 1−(2c/C)2 contribute with slack of length about C. The expected slack will then be around (2c/C)3+(1−(2c/C)2)*(C/C)=(2c/C)3+1−(2c/C)2, which has global minimum for m=2c-1, with a value of about 23/27=0.85. A more precise analysis gives a somewhat lower estimate for the remaining 1−(2c/C)2 fraction, but will also need to compensate for cuts within distance m inside s3, which contributes to a higher estimate.
0!=(hash&((1<<c)−1))
0==(hash&((1<<c)−1)).
The probability for matching this filter is given by (1−p)m−1 p where p is 2−c. One may compute that the expected chunk length is given by the inverse of the probability for matching a filter (it is required that the filter not allow a sequence to match both a prefix and suffix), thus the expected length of the example filter is (1−p)−m+1p−1. This length is minimized when setting p:=1/m, and it turns out to be around (e*m). The average slack hovers around 0.77, or about 1−e−1+e−2, as can be verified by those skilled in the art. An alternative embodiment of this method uses a pattern that works directly with the raw input and does not use rolling hashes.
Chunking at Local Maxima is based on choosing as cut points positions that are maximal within a bounded horizon. In the following, we shall use h for the value of the horizon. We say that the hash at position offset is an h-local maximum if the hash values at offsets offset−h, . . . , offset−1, as well as offset+1, . . . , offset+h are all smaller than the hash value at offset. In other words, all positions h steps to the left and h steps to the right have lesser hash values. Those skilled in the art will recognize that local maxima may be replaced by local minima or any other metric based comparison (such as “closest to the median hash value”).
The set of local maxima for an object of size n may be computed in time bounded by 2�n operations such that the cost of computing the set of local maxima is close to or the same as the cost of computing the cut-points based on independent chunking. Chunks generated using local maxima always have a minimal size corresponding to h, with an average size of approximately 2h+1. A CutPoint procedure is illustrated in FIGS. 8 and 9, and is described as follows below:
1. Allocate an array M of length h whose entries are initialized with the record {isMax=false, hash=0, offset=0}. The first entry in each field (is Max) indicates whether a candidate can be a local maximum. The second field entry (hash) indicates the hash value associated with that entry, and is initialized to 0 (or alternatively, to a maximal possible hash value). The last field (offset) in the entry indicates the absolute offset in bytes to the candidate into the fingerprinted object. 2. Initialize offsets min and max into the array M to 0. These variables point to the first and last elements of the array that are currently being used. 3. CutPoint(hash, offset) starts at step 800 in FIG. 8 and is invoked at each offset of the object to update M and return a result indicating whether a particular offset is a cutpoint.
The procedure starts by setting result=false at step 801. At step 803, the procedure checks whether M[max].offset+h+1=offset. If this condition is true, execution continues at step 804 where the following assignments are performed: result is set to M[max].isMax, and max is set to max−1% h. Execution then continues at step 805. If the condition at step 803 is false, execution continues at step 805. At step 805, the procedure checks whether M[min].hash>hash. If the condition is true, execution continues at step 806, where min is set to (min−1) % h. Execution the continues at step 807 where M[min] is set to {isMax=false, hash=hash, offset=offset}, and to step 811, where the computed result is returned. If the condition at step 805 is false, execution continues to step 808, where the procedure checks for whether M[min].hash=hash. If this condition is true, execution continues at step 807. If the condition at step 808 is false, execution continues at step 809, where the procedure checks whether min=max. If this condition is true, execution continues at step 810, where M[min] is set to {isMax=true, hash=hash, offset=offset} Execution then continues at step 811, where the computed result is returned. If the condition at step 809 is false, execution continues at step 811, where min is set to (min+1) % h. Execution then continues back at step 805. 4. When CutPoint(hash, offset) returns true, it will be the case that the offset at position offset−h−1 is a new cut-point.
Since the hash values from the elements form a descending chain between min and max, we will see that the average distance between min and max (|min−max|% h) is given by the natural logarithm of h. Offsets not included between two adjacent entries in M have hash values that are less than or equal to the two entries. The average length of such chains is given by the recurrence equation f(n)=1+1/n*Σk<nf(k). The average length of the longest descending chain on an interval of length n is 1 greater than the average length of the longest descending chain starting from the position of the largest element, where the largest element may be found at arbitrary positions with a probability of 1/n. The recurrence relation has as solution corresponding to the harmonic number Hn=1+�+⅓+�+ . . . +1/n, which can be validated by substituting Hn into the equation and performing induction on n. Hn is proportional to the natural logarithm of n. Thus, although array M is allocated with size h, only a small fraction of size ln(h) is ever used at any one time.
Approximating using integration ∫0≦x<m1/m (x/m)2hdx=1/(2h+1) indicates the probability when m is sufficiently large.
(1/m)2h+1Σ0≦k<mk2h,
(1/m)2h+11/(2h+1)Σ0≦k<2h(2h+1)!/k!(2h+1−k)!Bkm2h+1-k The only odd Bernoulli number that is non-zero is B1, which has a corresponding value of −�. The even Bernoulli numbers satisfy the equation:
H ∞ (2n)=(−1)n-122n-1π2n B 2n/(2n)!
When m is much larger than h, all of the terms, except for the first can be ignored, as we saw by integration. They are given by a constant between 0 and 1 multiplied by a term proportional to hk-1/mk. The first term (where B0=1) simplifies to 1/(2h+1). (the second term is −1/(2m), the third is h/(6 m2)).
For a rough estimate of the expected slack consider streams s1s3 and s2s3. The last cut points inside s1 and s2 may appear at arbitrary places. Since the average chunk length is about 2h+1 about �′th of the last cut-points will be within distance h in both s1 and s2. They will contribute to cut-points at around ⅞ h. In another � of the cases, one cut-point will be within distance h the other beyond distance h. These contribute with cut-points around �h. The remaining �′th of the last cut-points in s1 and s2 will be in distance larger than h. The expected slack will therefore be around �*⅞+�*�+�*�=0.66.
In the alternate procedure (see FIGS. 10 and 11), we assume for simplicity that a stream of hashes is given as a sequence. The subroutine CutPoint gets called for each subsequence of length h (expanded to “horizon” in the Figures). It returns zero or one offsets which are determined to be cut-points. Only ln(h) of the calls to Insert will pass the first test.
The loop that updates both A[k] and B[k].isMax can be optimized such that in average only one test is performed in the loop body. The case B[l].hash <=A[k].hash and B[l].isMax is handled in two loops, the first checks the hash value against B[l].hash until it is not less, the second updates A[k]. The other case can be handled using a loop that only updates A[k] followed by an update to B[l].isMax.
The particular mathematical function described previously for local maxima is a binary predicate “_>_”. For the case where p is an offset in the object, p is chosen as a cut-point if hashp>hashk, for all k, where p−horizon≦k<p, or p<k≦p+horizon. However, the binary predicate > can be replaced with any other mathematical function without deviating from the spirit of the invention.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS4845614Aug 10, 1987Jul 4, 1989Hitachi, Ltd.Microprocessor for retrying data transferUS4853842Feb 19, 1988Aug 1, 1989Texas Instruments IncorporatedComputer memory system having persistent objectsUS5446888Jan 14, 1994Aug 29, 1995Pyne; Charles F.Remote file transfer method and apparatusUS5486826May 19, 1994Jan 23, 1996Ps Venture 1 LlcMethod and apparatus for iterative compression of digital dataUS5488364Feb 28, 1994Jan 30, 1996Sam H. EulmiRecursive data compressionUS5592618Oct 3, 1994Jan 7, 1997International Business Machines CorporationRemote copy secondary data copy validation-audit functionUS5592661Jul 16, 1992Jan 7, 1997International Business Machines CorporationDetection of independent changes via change identifiers in a versioned database management systemUS5596710Oct 25, 1994Jan 21, 1997Hewlett-Packard CompanyMethod for managing roll forward and roll back logs of a transaction objectUS5673382May 30, 1996Sep 30, 1997International Business Machines CorporationAutomated management of off-site storage volumes for disaster recoveryUS5721907May 22, 1995Feb 24, 1998Traveling Software, Inc.Remote file transfer method and apparatusUS5724323Jan 29, 1996Mar 3, 1998Sanyo Electric Co., Ltd.Recording and reproducing apparatus for recording mediaUS5758359Oct 24, 1996May 26, 1998Digital Equipment CorporationMethod and apparatus for performing retroactive backups in a computer systemUS5933104Nov 22, 1995Aug 3, 1999Microsoft CorporationMethod and system for compression and decompression using variable-sized offset and length fieldsUS5987022Dec 27, 1996Nov 16, 1999Motorola, Inc.Method for transmitting multiple-protocol packetized dataUS5987432Dec 29, 1997Nov 16, 1999Reuters, Ltd.Fault-tolerant central ticker plant system for distributing financial market dataUS5990810Feb 15, 1996Nov 23, 1999Williams; Ross NeilMethod for partitioning a block of data into subblocks and for storing and communcating such subblocksUS6006016Oct 18, 1996Dec 21, 1999Bay Networks, Inc.Network fault correlationUS6014669Oct 21, 1997Jan 11, 2000Sun Microsystems, Inc.Highly-available distributed cluster configuration databaseUS6044475Jun 16, 1995Mar 28, 2000Lucent Technologies, Inc.Checkpoint and restoration systems for execution controlUS6049874Mar 12, 1998Apr 11, 2000Fairbanks Systems GroupSystem and method for backing up computer files over a wide area computer networkUS6061733Oct 16, 1997May 9, 2000International Business Machines Corp.Method and apparatus for improving internet download integrity via client/server dynamic file sizesUS6101507Feb 10, 1998Aug 8, 2000Connected CorporationFile comparison for data backup and file synchronizationUS6157931Dec 3, 1997Dec 5, 2000Connected CorporationDatabase/template driven file selection for backup programsUS6166735Dec 3, 1997Dec 26, 2000International Business Machines CorporationVideo story board user interface for selective downloading and displaying of desired portions of remote-stored video data objectsUS6205449Mar 20, 1998Mar 20, 2001Lucent Technologies, Inc.System and method for providing hot spare redundancy and recovery for a very large database management systemUS6226629Feb 28, 1998May 1, 2001Compaq Computer CorporationMethod and apparatus determining and using hash functions and hash valuesUS6240511Dec 14, 1998May 29, 2001Emc CorporationMethod and apparatus for detecting system configuration changesUS6269362Dec 19, 1997Jul 31, 2001Alta Vista CompanySystem and method for monitoring web pages by comparing generated abstractsUS6272547May 19, 1995Aug 7, 2001British Telecommunications Public Limited CompanyHigh level control of file transfer protocol with capability for repeated transfer attemptsUS6317754Jul 3, 1998Nov 13, 2001Mitsubishi Electric Research Laboratories, IncSystem for user control of version /Synchronization in mobile computingUS6374250Feb 3, 1997Apr 16, 2002International Business Machines CorporationSystem and method for differential compression of data from a plurality of binary sourcesUS6377974Jan 19, 2000Apr 23, 2002Speedbit Ltd.Methods and apparatus for downloading a file from a serverUS6381709Apr 3, 2000Apr 30, 2002Steven M. CasagrandeProcess and apparatus for downloading data from a server computer to a client computerUS6434568Aug 31, 1999Aug 13, 2002Accenture LlpInformation services patterns in a netcentric environmentUS6449612Jun 30, 2000Sep 10, 2002Microsoft CorporationVarying cluster number in a scalable clustering system for use with large databasesUS6453325Feb 3, 1997Sep 17, 2002International Business Machines CorporationMethod and means for backup and restoration of a database system linked to a system for filing dataUS6477629Nov 17, 2000Nov 5, 2002Adaptec, Inc.Intelligent backup and restoring system and method for implementing the sameUS6496901 *Sep 22, 1999Dec 17, 2002Storage Technology CorporationMapping variable size data blocks into a fixed block structureUS6505228Jul 22, 1998Jan 7, 2003Cisco Technology, Inc.Dynamic determination of execution sequenceUS6571282Aug 31, 1999May 27, 2003Accenture LlpBlock-based communication in a communication services patterns environmentUS6574618Dec 28, 2000Jun 3, 2003Appstream, Inc.Method and system for executing network streamed applicationUS6574657May 3, 1999Jun 3, 2003Symantec CorporationMethods and apparatuses for file synchronization and updating using a signature listUS6594677Dec 22, 2000Jul 15, 2003Simdesk Technologies, Inc.Virtual tape storage system and methodUS6604236Jun 28, 1999Aug 5, 2003Iora, Ltd.System and method for generating file updates for files stored on read-only mediaUS6618758Feb 18, 2000Sep 9, 2003Lucent Technologies Inc.System for downloading only a portion of a file from a server through a computer network utilizing a client menu downloaded periodically from the serverUS6633512Feb 22, 2001Oct 14, 2003Fujitsu LimitedMagneto-optical information storage apparatus and information storage method with function of updating default value of applied magnetic fieldUS6640244Aug 31, 1999Oct 28, 2003Accenture LlpRequest batcher in a transaction services patterns environmentUS6651249Dec 22, 1999Nov 18, 2003Symantec CorporationMulti-tiered incremental software updatingUS6665780Oct 6, 2000Dec 16, 2003Radiant Data CorporationN-way data mirroring systems and methods for using the sameUS6671802Apr 13, 2000Dec 30, 2003Hewlett-Packard Development Company, L.P.Performance optimization of computer system by dynamically and immediately updating a configuration setting based on detected change in preferred useUS6728711May 2, 2001Apr 27, 2004Hewlett-Packard Development Company, L.P.Automatic backup/recovery processUS6751753Feb 27, 2001Jun 15, 2004Sun Microsystems, Inc.Method, system, and program for monitoring system componentsUS6766314Apr 5, 2001Jul 20, 2004International Business Machines CorporationMethod for attachment and recognition of external authorization policy on file system resourcesUS6771826Nov 19, 2001Aug 3, 2004Matsushita Electric Industrial Co., Ltd.Digital image encoding and decoding method and digital image encoding and decoding device using the sameUS6772302Nov 12, 1999Aug 3, 2004International Business Machines CorporationVirtual copy method for data spanning storage boundariesUS6791982Sep 29, 1999Sep 14, 2004Telefonaktiebolaget Lm EricssonSegmentation protocol that supports compressed segmentation headersUS6799206Mar 31, 1998Sep 28, 2004Qualcomm, IncorporatedSystem and method for the intelligent management of archival data in a computer networkUS6819271Jan 11, 2002Nov 16, 2004Quickshift, Inc.Parallel compression and decompression system and method having multiple parallel compression and decompression enginesUS6842777Oct 3, 2000Jan 11, 2005Raja Singh TuliMethods and apparatuses for simultaneous access by multiple remote devicesUS6865598Jun 8, 2001Mar 8, 2005Hewlett-Packard Development Company, L.P.Utilization of unused disk space on networked computersUS6910071Apr 2, 2001Jun 21, 2005The Aerospace CorporationSurveillance monitoring and automated reporting method for detecting data changesUS6925540May 2, 2002Aug 2, 2005Intel CorporationSystems and methods for chassis identificationUS6938045Jan 18, 2002Aug 30, 2005Seiko Epson CorporationImage server synchronizationUS6947604Jan 17, 2002Sep 20, 2005Intel CorporationMethod and hardware to implement two-dimensional compressionUS6952823Aug 27, 2001Oct 4, 2005Pkware, Inc.Software patch generator using compression techniquesUS6963923Feb 10, 1997Nov 8, 2005International Business Machines CorporationMethod for file transfer restarts using standard internet protocolUS6965916Dec 14, 2000Nov 15, 2005Bellsouth Intellectual Property Corp.System and method for data distribution and recoveryUS6993686Apr 30, 2002Jan 31, 2006Cisco Technology, Inc.System health monitoring and recoveryUS7003554Mar 20, 2000Feb 21, 2006Netscape Communications Corp.System and method for downloading portions of a remotely located network object to produce a completely downloaded local copy of the network objectUS7054912Mar 8, 2002May 30, 2006Kabushiki Kaisha ToshibaData transfer scheme using caching technique for reducing network loadUS7054960Nov 18, 2003May 30, 2006Veritas Operating CorporationSystem and method for identifying block-level write operations to be transferred to a secondary site during replicationUS7058941Nov 14, 2000Jun 6, 2006Microsoft CorporationMinimum delta generator for program binariesUS7096392May 7, 2004Aug 22, 2006Asempra Technologies, Inc.Method and system for automated, no downtime, real-time, continuous data protectionUS7099884Dec 24, 2002Aug 29, 2006Innopath SoftwareSystem and method for data compression and decompressionUS7158972Nov 21, 2002Jan 2, 2007Sun Microsystems, Inc.Methods and apparatus for managing multiple user systemsUS7174479Sep 10, 2003Feb 6, 2007Microsoft CorporationMethod and system for rollback-free failure recovery of multi-step proceduresUS7178140May 31, 2002Feb 13, 2007Sun Microsystems, Inc.Speeding up application downloading from a remote serverUS7191441Aug 6, 2002Mar 13, 2007International Business Machines CorporationMethod and apparatus for suspending a software virtual machineUS7281124Jun 17, 2004Oct 9, 2007Intel CorporationEstablishing a virtual drive accessible to pre-boot and operating system runtime phasesUS7299360 *Dec 16, 2003Nov 20, 2007Precise BiometricsMethod and system for fingerprint template matchingUS7299376Aug 25, 2004Nov 20, 2007International Business Machines CorporationApparatus, system, and method for verifying backup dataUS7310654Jan 31, 2002Dec 18, 2007Mirapoint, Inc.Method and system for providing image incremental and disaster recoveryUS7318073May 31, 2002Jan 8, 2008Microsoft CorporationSystem and method for downloading information to a mobile deviceUS7334023Mar 26, 2003Feb 19, 2008Kabushiki Kaisha ToshibaData transfer scheme for reducing network load using general purpose browser on client sideUS7353355Dec 28, 2004Apr 1, 2008Acronis Inc.System and method for rapid restoration of server from backupUS7356679Oct 1, 2004Apr 8, 2008Vmware, Inc.Computer image capture, customization and deploymentUS7360093Jul 22, 2002Apr 15, 2008Xerox CorporationSystem and method for authentication of JPEG image dataUS7362758Jan 14, 2005Apr 22, 20081E LimitedData distribution apparatus and methodUS7363538May 31, 2002Apr 22, 2008Oracle International CorporationCost/benefit based checkpointing while maintaining a logical standby databaseUS7370120Dec 7, 2001May 6, 2008Propel Software CorporationMethod and system for reducing network latency in data communicationUS7461319Apr 4, 2003Dec 2, 2008Sun Microsystems, Inc.System and method for downloading files over a network with real time verificationUS7477166Aug 22, 2006Jan 13, 2009Riverbed Technology, Inc.Content-based segmentation scheme for data compression in storage and transmission including hierarchical segment representationUS7487169Nov 24, 2004Feb 3, 2009International Business Machines CorporationMethod for finding the longest common subsequences between files with applications to differential compressionUS7519635 *Mar 31, 2008Apr 14, 2009International Business Machines CorporationMethod of and system for adaptive selection of a deduplication chunking techniqueUS7523098 *Sep 15, 2004Apr 21, 2009International Business Machines CorporationSystems and methods for efficient data searching, storage and reductionUS7523348May 2, 2005Apr 21, 2009Microsoft CorporationMethod and system for monitoring and managing archive operationsUS7555531 *Apr 15, 2004Jun 30, 2009Microsoft CorporationEfficient algorithm and protocol for remote differential compressionUS7574459May 17, 2005Aug 11, 2009Microsoft CorporationMethod and system for verifying data in a data protection systemUS7613787 *Nov 3, 2009Microsoft CorporationEfficient algorithm for finding candidate objects for remote differential compressionUS7756833Sep 22, 2004Jul 13, 2010Microsoft CorporationMethod and system for synthetic backup and restoreUS7849462Dec 7, 2010Microsoft CorporationImage serverUS20020010702Feb 3, 1997Jan 24, 2002Miklos AjtaiSystem and method for differential compression of data from a plurality of binary sourcesUS20020015336Jun 8, 2001Feb 7, 2002Watkins Mark RobertUtilization of unused disk space on networked computerUS20020083182Dec 18, 2000Jun 27, 2002Alvarado Juan C.Real-time streamed data download system and methodUS20020107877Dec 29, 1997Aug 8, 2002Douglas L. WhitingSystem for backing up files from disk volumes on multiple nodes of a computer networkUS20020147733Apr 6, 2001Oct 10, 2002Hewlett-Packard CompanyQuota management in client side data storage back-upUS20020152219Apr 16, 2001Oct 17, 2002Singh Monmohan L.Data interexchange protocolUS20020169867Jan 4, 1999Nov 14, 2002Joe MannRemote system administration and seamless service integration of a data communication network management systemUS20020199040Jun 26, 2001Dec 26, 2002Irwin David S.High speed communications device/systemUS20030005102Jun 28, 2001Jan 2, 2003Russell Lance W.Migrating recovery modules in a distributed computing environmentUS20030018657Jul 18, 2001Jan 23, 2003Imation Corp.Backup of data on a networkUS20030028736Jul 24, 2001Feb 6, 2003Microsoft CorporationSystem and method for backing up and restoring dataUS20030028867Aug 27, 2001Feb 6, 2003Kryloff Sergey A.Software patch generatorUS20030033344Aug 6, 2002Feb 13, 2003International Business Machines CorporationMethod and apparatus for suspending a software virtual machineUS20030046415Jan 30, 2002Mar 6, 2003Takahiro KaijyuFile transmitting method and systemUS20030061287May 31, 2002Mar 27, 2003Chee YuMethod and system for delivering files in digital file marketplaceUS20030110296Dec 7, 2001Jun 12, 2003Kirsch Steven T.Method and system for reducing network latency in data communicationUS20030120772Oct 21, 2002Jun 26, 2003Husain Syed Mohammad AmirData fail-over for a multi-computer systemUS20030120920Dec 20, 2001Jun 26, 2003Svensson Sven Anders BorjeRemote device authenticationUS20030133616Jan 17, 2002Jul 17, 2003Lippincott Louis A.Method and hardware to implement two-dimensional compressionUS20030140050Jan 18, 2002Jul 24, 2003Chia-Hsin LiImage server synchronizationUS20030154220Jan 22, 2002Aug 14, 2003David Maxwell CannonCopy process substituting compressible bit pattern for any unqualified data objectsUS20030163506May 31, 2002Aug 28, 2003Sun Microsystems, Inc., A Delaware CorporationSpeeding up application downloading from a remote serverUS20030167287Apr 11, 2001Sep 4, 2003Karl ForsterInformation protection systemUS20030167419Aug 20, 2002Sep 4, 2003Moshe YanaiRemote data mirroring system having a remote link adapterUS20030177485Dec 22, 1999Sep 18, 2003Ray Soon WaldinMulti-tiered incremental software updatingUS20030187960Mar 26, 2003Oct 2, 2003Kabushiki Kaisha ToshibaData transfer scheme for reducing network load using general purpose browser on client sideUS20030217033May 17, 2002Nov 20, 2003Zigmund SandlerDatabase system and methodsUS20030217083Jun 17, 2003Nov 20, 2003Taylor Kenneth J.Method and apparatus for storage and retrieval of very large databases using a direct pipeUS20030225800Nov 25, 2002Dec 4, 2003Srinivas KavuriSelective data replication system and methodUS20040012808Jun 4, 2001Jan 22, 2004Payne David M.Network-based technical support and diagnosticsUS20040015697Jul 22, 2002Jan 22, 2004Xerox CorporationSystem and method for authentication of JPEG image dataUS20040039716Aug 22, 2003Feb 26, 2004Thompson Dean S.System and method for optimizing a computer programUS20040054700Aug 18, 2003Mar 18, 2004Fujitsu LimitedBackup method and system by differential compression, and differential compression methodUS20040093555Sep 10, 2003May 13, 2004Therrien David G.Method and apparatus for managing data integrity of backup and disaster recovery dataUS20040098637Nov 15, 2002May 20, 2004Duncan Kurt A.Apparatus and method for enhancing data availability by leveraging primary/backup data storage volumesUS20040133606Jan 2, 2003Jul 8, 2004Z-Force Communications, Inc.Directory aggregation for files distributed over a plurality of servers in a switched file systemUS20040133607Jan 2, 2003Jul 8, 2004Z-Force Communications, Inc.Metadata based file switch and switched file systemUS20040153458Oct 30, 2003Aug 5, 2004Noble Brian D.Peer-to-peer method and system for performing and managing backups in a network of nodesUS20040199815Apr 2, 2003Oct 7, 2004Sun Microsystems, Inc.System and method for measuring performance with distributed agentsUS20040230377May 16, 2003Nov 18, 2004Seawest Holdings, Inc.Wind power management system and methodUS20040260973May 4, 2004Dec 23, 2004Cascade Basic Research Corp.Method and system for reciprocal data backupUS20040267836Jun 25, 2003Dec 30, 2004Philippe ArmangauReplication of snapshot using a file system copy differentialUS20050004979Jul 30, 2004Jan 6, 2005Microsoft CorporationMethod and system for transporting data content on a storage area networkUS20050010593Jul 10, 2003Jan 13, 2005International Business Machines CorporationSystem and method for performing predictive file storage managementUS20050015685Sep 11, 2003Jan 20, 2005Masayuki YamamotoFailure information management method and management server in a network equipped with a storage deviceUS20050055578Jul 21, 2004Mar 10, 2005Michael WrightAdministration of protection of data accessible by a mobile deviceUS20050071390Sep 30, 2003Mar 31, 2005Livevault CorporationSystems and methods for backing up data filesUS20050091247Nov 24, 2004Apr 28, 2005Microsoft CorporationSystem and method for backing up and restoring dataUS20050114363Nov 26, 2003May 26, 2005Veritas Operating CorporationSystem and method for detecting and storing file identity change information within a file systemUS20050131939 *Dec 16, 2003Jun 16, 2005International Business Machines CorporationMethod and apparatus for data redundancy elimination at the block levelUS20050160118Feb 14, 2005Jul 21, 2005Microsoft CorporationSystem and method for backing up and restoring dataUS20050165868Aug 23, 2004Jul 28, 2005Vivek PrakashSystems and methods of information backupUS20050198303Jan 2, 2004Sep 8, 2005Robert KnauerhaseDynamic virtual machine service provider allocationUS20050216633Mar 26, 2004Sep 29, 2005Cavallo Joseph STechniques to manage critical region interruptsUS20050228836Apr 8, 2005Oct 13, 2005Bacastow Steven VApparatus and method for backing up computer filesUS20050235043Apr 15, 2004Oct 20, 2005Microsoft CorporationEfficient algorithm and protocol for remote differential compressionUS20050256826May 13, 2004Nov 17, 2005International Business Machines CorporationComponent model for batch computing in a distributed object environmentUS20050256974May 13, 2004Nov 17, 2005Microsoft CorporationEfficient algorithm and protocol for remote differential compression on a remote deviceUS20050262167May 13, 2004Nov 24, 2005Microsoft CorporationEfficient algorithm and protocol for remote differential compression on a local deviceUS20060031547May 7, 2004Feb 9, 2006Wyse Technology Inc.System and method for integrated on-demand delivery of operating system and applicationsUS20060041761Aug 17, 2004Feb 23, 2006Neumann William CSystem for secure computing using defense-in-depth architectureUS20060047716Jun 2, 2005Mar 2, 2006Keith Robert O JrTransaction based virtual file system optimized for high-latency network connectionsUS20060047720Aug 30, 2004Mar 2, 2006Ravi KulkarniDatabase backup, refresh and cloning system and methodUS20060047855May 13, 2004Mar 2, 2006Microsoft CorporationEfficient chunking algorithmUS20060053088Jun 30, 2005Mar 9, 2006Microsoft CorporationMethod and system for improving management of media used in archive applicationsUS20060053178Sep 9, 2004Mar 9, 2006Microsoft CorporationMethod, system, and apparatus for creating an archive routine for protecting data in a data protection systemUS20060053181May 2, 2005Mar 9, 2006Microsoft CorporationMethod and system for monitoring and managing archive operationsUS20060053214Jun 29, 2004Mar 9, 2006International Business Machines CorporationMethod and system of detecting a change in a server in a server systemUS20060064444Sep 22, 2004Mar 23, 2006Microsoft CorporationMethod and system for synthetic backup and restoreUS20060085561Sep 24, 2004Apr 20, 2006Microsoft CorporationEfficient algorithm for finding candidate objects for remote differential compressionUS20060112113Nov 8, 2005May 25, 2006Jinsheng GuStatic file system differencing and updatingUS20060150001Feb 24, 2006Jul 6, 2006Yoshiaki EguchiData restoring method and an apparatus using journal data and an identification informationUS20060155674Jan 7, 2005Jul 13, 2006Microsoft CorporationImage serverUS20060155735Jan 7, 2005Jul 13, 2006Microsoft CorporationImage serverUS20060184652Feb 16, 2005Aug 17, 2006Microsoft CorporationApplications for remote differential compresssionUS20060218435Mar 24, 2005Sep 28, 2006Microsoft CorporationMethod and system for a consumer oriented backupUS20060259526Jul 26, 2006Nov 16, 2006International Business Machines CorporationNested Recovery Scope Management For Stateless Recovery AgentsUS20070094348Oct 6, 2006Apr 26, 2007Microsoft CorporationBITS/RDC integration and BITS enhancementsUS20070162521Jan 9, 2006Jul 12, 2007International Business Machines CorporationMethod and system for sharing files among different virtual machine imagesUS20070180490Jul 1, 2004Aug 2, 2007Renzi Silvio JSystem and method for policy managementUS20090113241Dec 30, 2008Apr 30, 2009Microsoft CorporationMethod, system, and apparatus for providing alert synthesis in a data protection systemUS20090216798Apr 30, 2009Aug 27, 2009Microsoft CorporationConfiguring a data protection systemUS20100064141Jul 31, 2009Mar 11, 2010Microsoft CorporationEfficient algorithm for finding candidate objects for remote differential compressionEP1587007A2Apr 5, 2005Oct 19, 2005Microsoft CorporationEfficient algorithm and protocol for remote differential compressionEP1641219A2Sep 9, 2005Mar 29, 2006Microsoft CorporationEfficient algorithm for finding candidate objects for remote differential compressionJP11259387A Title not availableRU2192039C2 Title not availableTW508929B Title not availableTW510107B Title not availableTW511021B Title not availableTW514810B Title not availableTW533723B Title not availableTW550490B Title not availableTW580656B Title not available* Cited by examinerNon-Patent CitationsReference1"How Do the ‘Verify’ and ‘Write Checksums to Media’ Processes Work and Why are They Necessary?"; Veritas Software; Sep. 29, 2004; http://seer.support.veritas.com/docs/24517.htm; Retrieved May 6, 2005; 6 pages.2"How Do the 'Verify' and 'Write Checksums to Media' Processes Work and Why are They Necessary?"; Veritas Software; Sep. 29, 2004; http://seer.support.veritas.com/docs/24517.htm; Retrieved May 6, 2005; 6 pages.3"Ultrabac: Overview"; Raxco Software Europe; n. d.; http://www.raxco.co.uk/product.asp?ProductID=100; Retrieved May 6, 2005.4"Vertitas(TM) NetBackup & Data Domain DD200 Restorer: Highly Reliable, High-Performance Disk-Based Data Protection at the Cost of Tape"; Copyright 2004 Veritas Software Corporation; http://www.datadomain.com/pdf/Veritas-NetBackup-and-DataDomainDD200.pdf; Retrieved May 6, 2005.5"Vertitas™ NetBackup & Data Domain DD200 Restorer: Highly Reliable, High-Performance Disk-Based Data Protection at the Cost of Tape"; Copyright 2004 Veritas Software Corporation; http://www.datadomain.com/pdf/Veritas-NetBackup-and-DataDomainDD200.pdf; Retrieved May 6, 2005.63wGet-Powerful HTTP/FTP Download Manager and Websites Downloader, http://www.popularshareware.com/3wGet-download-9099.ht20060085561m1, 2 pages.7ActiveFile, http://www.15seconds.com/component/pg000024.htm, 2006, 4 pages.8Advisory Action dated Sep. 12, 2008 issued in U.S. Appl. No. 11/090,586, 3 pages.9Ajtai et al.; "Compactly Encoding: Unstructured Inputs with Differential Compression"; Journal of ACM, vol. 49, No. 3, May, 2002; pp. 318-367.10Amendment after Notice of Allowance dated Nov. 24, 2009 filed in U.S. Appl. No. 11/031,133, 6 pages.11Appeal Brief dated Nov. 15, 2010 filed in U.S. Appl. No. 11/090,586, 15 pages.12Australian Examiner's first report dated Jan. 22, 2010 regarding Application No. 2005201386, 1 page.13Australian Notice of Allowance; AU Application 2005201386, mailed Jun. 2, 2010, 3 pgs..14Bj�ner et al., "Content-Dependent Chunking for Differential Compression, The Local Maxim Approach," TR-2007-102; 93 pgs.15Broder, "On the resemblance and containment of documents," IEEE, 1997 Proceedings on Compression and Complexity of Sequences Conference Jun. 11-13, 1997 (11 pgs.).16Broder, A.Z., "Identifying and Filtering Near-Duplicate Documents", Sequences 1997, 10 pages.17Broder, Identifying and Filtering Near-Duplicate Documents, Combinatorial Pattern Matching, 11th Annual Symposium, CPM 2000, Montreal, Canada, Jun. 21-23, 2000 Proceedings, Springer, (10 pgs).18Burns et al., "Efficient Distributed Backup with Delta Compression"; Proceedings of the Fifth Workshop on I/O in Parallel and Distributed 1997; pp. 27-36.19Burns et al.; "A Linear Time, Constant Space Differencing Algorithm"; 8 pgs.20Burns, Randal C., "Differential Compression: A Generalized Solution for Binary Files", University of California Santa Cruz, Dec. 1996, 69 pages.21Chang, et al., Mimic: Raw Activity Shipping for File Synchronization in Mobile File Systems, 2004 ACM, pp. 165-176.22Chien, Jet Propulsion Laboratory, Gratch, Beckman Institute, "Producing satisfactory solutions to Scheduling problems: An Iterative Constraint Relaxation Approach," 6 pgs.23Chinese 1st Office Action in Application 201101507683, mailed Nov. 16, 2011, 6 pgs.24Chinese 2nd Office Action dated Aug. 24, 2010, Application No. 200510055107.7.25Chinese Notice of Allowance dated Jan. 8, 2010, Application No. 200510108958.3, 2 pgs.26Chinese Notice of Allowance dated Mar. 18, 2011, Application No. 200510055107.7, 4 pgs.27Chinese Office Action dated Aug. 1, 2008, Application No. 200510108958.3.28Chinese Office Action dated Jul. 24, 2009, Application No. 200510055107.7.29Communication from the Examining Division dated Aug. 27, 2007 regarding EP Application No. 05108288.1, 1 page.30Decision on Petition to Withdraw from Issue dated Jun. 24, 2010 issued in U.S. Appl. No. 11/031,133, 2 pages.31Decision on Pre-Brief Conference Request dated Oct. 15, 2010 filed in U.S. Appl. No. 11/090,586, 2 pages.32Douglis, Fred; Iyengar, Arun. "Application-specific Delta-encoding via Resemblance Detection," USENIX Annual Technical Conference, 2003, [14 pages].33EP Examination Report dated Dec. 4, 2009, Application No. 05 102 664.9.34Eshghi, "Intrinsic References in Distributed Systems," Hewlett-Packard Company, 2002, pp. 1-8.35European Search Report dated Mar. 2, 2007, Application No. 05102664.9-1225.36European Search Report dated Nov. 3, 2006, Application No. 05108288.1-1225.37Examiner's Answer to Appeal Brief dated Dec. 7, 2010 filed in U.S. Appl. No. 11/090,586, 21 pages.38File2Pack 2.0, Mental9Production, Dec. 24, 2005, http://www.freedomloadmanager.org/downloads/archiving software, 4 pages.39Fisher, "Iterative Optimization and Simplification of Hierarchical Clusterings" TR CS95-01, pp. 1-33.40Giancarlo, et al., Combinatorial Pattern Matching, 11th Annual Symposium, CPM 2000, Springer (13 pgs.).41Hamilton et al, "Design and Implementation of a Storage Repository Using Commonality Factoring," IEEE 2003 (6 pgs).42Israeli Office Action dated Jul. 12, 2009 Application No. 167467, 2 pages.43Japanese Final Rejection in Application 2005277831 mailed Sep. 22, 2011, 4 pgs.44Japanese Notice of Rejection dated Apr. 15, 2011, Application No. 2005-277831, 7 pages.45Japanese Notice of Rejection dated Dec. 14, 2010, Application No. 2005-073985, 8 pages.46Japanese Patent Application No. 2005-073985, Notice of Allowance mailed Jul. 22, 2011, 6 pgs.47Kotz, "I/O in Parallel and Distributed Systems"; Department of Computer Science, Dartmouth College, 10 pgs.48Kotz, et al., "I/O in Parallel and Distributed Systems," Mar. 1, 1998, (last viewed Mar. 14, 2007) pp. 1-29, http://72.14.253.104/search?q=cache:OZiK-nQxc2sJ:www/cs/dart,pitj/edi/~dfk/papers.49Kotz, et al., "I/O in Parallel and Distributed Systems," Mar. 1, 1998, (last viewed Mar. 14, 2007) pp. 1-29, http://72.14.253.104/search?q=cache:OZiK—nQxc2sJ:www/cs/dart,pitj/edi/˜dfk/papers.50Kozuch et al., "Efficient State Transfer for Internet Suspend/Resume," May 2002, p. 5 Pure-Demand fetch, 12 pages.51Kulkarni, et al., "Redundancy Elimination Within Large Collection of Files," USENIX Association, 2004, pp. 59-72.52Langford, "Multiround Rsync," Jan. 31, 2001, pp. 1-11.53Malaysian Notice of Allowance in Application PI20051086 mailed Oct. 31, 2011, 2 pgs.54Manber, "Finding Similar Files in a Large File System," University of Arizona Technical report; TR-93-33, 11 pgs.55Mexican Notice of Allowance; Application No. PAa2005002949, mailed Jul. 9, 2010, 2 pgs.56Miyashita, Kazuo, Electrotechnical Laboratory, and Sycara, Katia, Carnegie Mellon University, "Improving System Performance in Case-Based Iterative Optimization through Knowledge Filtering," 6 pp.57Muthitacharoen et al., "A low-bandwidth network file system," Proceedings of the eighteenth ACM symposium on Operating systems principles, 2001, pp. 174-187.58Muthitacharoen, et. al., Low-Bandwidth File System (LBFS), http://pdos.csail.mit.edu/papers/lbfs:sosp01/lbfs.pdf; 2 pgs.59New Zealand Examination Report dated Mar. 15, 2005, Application No. 538839.60Notice of Allowance dated Aug. 7, 2011 issued in U.S. Appl. No. 11/031,133, 7 pages.61Notice of Allowance dated Oct. 13, 2009 issued in U.S. Appl. No. 11/031,133, 13 pages.62Notice of Allowance dated Oct. 15, 2008 filed in U.S. Appl. No. 10/948,980, 7 pages.63Notice of Allowance dated Sep. 24, 2009 cited in U.S. Appl. No. 10/937,204, 6 pages.64Office Action dated Apr. 17, 2008 cited in U.S. Appl. No. 10/937,060, 18 pages.65Office Action dated Apr. 26, 2010 cited in U.S. Appl. No. 10/937,061, 32 pages.66Office Action dated Apr. 3, 2009 issued in U.S. Appl. No. 11/031,133, 9 pages.67Office Action dated Apr. 9, 2008 issued in U.S. Appl. No. 11/031,133, 11 pages.68Office Action dated Aug. 10, 2007 issued in U.S. Appl. No. 11/090,586, 5 pages.69Office Action dated Dec. 10, 2007 cited in U.S. Appl. No. 10/937,204, 12 pages.70Office Action dated Feb. 18, 2011 issued in U.S. Appl. No. 11/031,133, 10 pages.71Office Action dated Feb. 19, 2009 issued in U.S. Appl. No. 11/090,586, 13 pages.72Office Action dated Jun. 25, 2008 cited in U.S. Appl. No. 10/937,204, 14 pages.73Office Action dated Jun. 8, 2010 issued in U.S. Appl. No. 11/544,485, 12 pages.74Office Action dated Mar. 11, 2009 cited in U.S. Appl. No. 10/937,204, 8 pages.75Office Action dated Mar. 11, 2010 issued in U.S. Appl. No. 11/090,586, 23 pages.76Office Action dated Mar. 19, 2009 cited in U.S. Appl. No. 10/937,060, 20 pages.77Office Action dated May 29, 2008 issued in U.S. Appl. No. 11/090,586, 17 pages.78Office Action dated Nov. 1, 2007 cited in U.S. Appl. No. 10/937,060, 12 pages.79Office Action dated Nov. 12, 2009 cited in U.S. Appl. No. 10/937,060, 21 pages.80Office Action dated Nov. 25, 2009 issued in U.S. Appl. No. 11/090,586, 17 pages.81Office Action dated Oct. 15, 2008 issued in U.S. Appl. No. 11/031,133, 10 pages.82Office Action dated Oct. 2, 2007 issued in U.S. Appl. No. 11/090,586, 11 pages.83Office Action dated Oct. 9, 2008 cited in U.S. Appl. No. 10/937,060, 17 pages.84Petition to Withdraw from Issue dated Jun. 21, 2010 issued in U.S. Appl. No. 11/031,133, 9 pages.85Philippine Office Action dated Nov. 14, 2007, Application No. 1-2005-000140.86Philippine Official Action dated Oct. 6, 2009 regarding Application No. Jan. 2005-000140, 2 pages.87Pre-Brief Conference Request dated Sep. 13, 2010 filed in U.S. Appl. No. 11/090,586, 5 pages.88Reply Brief dated Feb. 7, 2011 filed in U.S. Appl. No. 11/090,586, 9 pages.89Response to Amendment after Notice of Allowance dated Dec. 16, 2009 issued in U.S. Appl. No. 11/031,133, 2 pages.90Response to Communication from the Examining Division dated Feb. 11, 2008 regarding EP Application No. 05108288.1, 17 pages.91Response to Office Action dated Aug. 18, 2009 filed in U.S. Appl. No. 11/090,586, 11 pages.92Response to Office Action dated Aug. 29, 2008 filed in U.S. Appl. No. 11/090,586, 13 pages.93Response to Office Action dated Feb. 1, 2008 filed in U.S. Appl. No. 11/090,586, 13 pages.94Response to Office Action dated Feb. 14, 2007 filed in U.S. Appl. No. 10/844,907, 17 pages.95Response to Office Action dated Feb. 25, 2010 filed in U.S. Appl. No. 11/090,586, 10 pages.96Response to Office Action dated Jul. 6, 2009 filed in U.S. Appl. No. 11/031,133, 8 pages.97Response to Office Action dated Jul. 9, 2008 filed in U.S. Appl. No. 11/031,133, 9 pages.98Response to Office Action dated Jun. 6, 2008 filed in U.S. Appl. No. 10/948,980, 15 pages.99Response to Office Action dated May 18, 2011 issued in U.S. Appl. No. 11/031,133, 11 pages.100Response to Office Action dated Nov. 16, 2007 filed in U.S. Appl. No. 10/844,907, 21 pages.101Response to Office Action dated Sep. 10, 2007 filed in U.S. Appl. No. 11/090,586, 1 pages.102Response to Office Action dated Sep. 19, 2008 filed in U.S. Appl. No. 10/948,980, 11 pages.103Rivest, R., "The MD4 Message-Digest Algorithm," MIT Laboratory for Computer Science and RSA Data Security, Inc., Apr. 1992, Network Working Group, RFC 1320, 20 pp.104Russian Application No. 20051045759, Notice of Atlowance mailed Aug. 28, 2009, 11 pgs.105Russian Office Action dated Apr. 13, 2009, Application No. 2005105759.106Samba documentation http://rsync.samba.org/documentation.html; 1 pg.107ScriptUtilities and Huge ASP File Upload, http://www.motobit.com/help/aspupload/upload.asp, 1996-2006,5 pages.108Singapore Patent Application No. 200501089-7, Examination report and Allowance mailed Nov. 13, 2006, 4 pgs.109Spring, Neil T.; Wetherall, David. "A protocol-independent technique for eliminating redundant network traffic," Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication; 2000, pp. 87-95.110Suel et al., "Algorithms for Delta Compression and Remote File Synchronization," {suel,memon}@poly.edu Academic Press, Aug. 2002, 24 pgs.111Suel et al.; "Improved File Synchronization Techniques for Maintaining Large Replicated Collections over Slow Networks," in Proceedings: IEEE 20 International Conference on Data Engineering, Mar. 30 to Apr. 2, 2004, pp. 153 to 164, available from Massey University in 2004.112Taiwan Application No. 94107741 Office Action and Search Report mailed Jul. 5, 2011, 4 pgs.113Taiwan Notice of Allowance in Application 94107741, mailed Nov. 21, 2011, 4 pgs.114Teodosiu, Dan; Gjorner Nikolaj; Gurevich , Yuri; Manasse, Mark; and Porka, Joe, "Optimizing File Replication over Limited-Bandwidth Networks using Remote Differential Compression," pp. 1-16.115Tridgell et al.; "The Rsync Algorithm", http://www.infoscience.co.jp/technical/sync/tech-report/index.html; Nov. 9, 1998; 1 pg.116Tridgell et al.; "The Rsync Algorithm", http://www.infoscience.co.jp/technical/sync/tech—report/index.html; Nov. 9, 1998; 1 pg.117Tridgell et al.; "The Rsync Algorithm", The Australian National University; TR-CS-96-05; Jun. 1996; 8 pgs.118Tridgell, "Efficient Algorithms for Sorting and Synchronization," Thesis—The Australian National University; Feb. 1999; 115 pages.119Tridgell; "The Rsync Algorithm", http://olstrans.sourceforge.net/release/OLS2000-rsync/OLS2000-rsync.html; Jul. 21, 2000; 27 pgs.120Tridgell; "The Rsync Algorithm", Nov. 9, 1998 (last viewed Oct. 11, 2006); http://www.infoscience.co.jp/technical/rsynch/tech-report/index.html; 10 pgs.121Tridgell; "The Rsync Algorithm", Nov. 9, 1998 (last viewed Oct. 11, 2006); http://www.infoscience.co.jp/technical/rsynch/tech—report/index.html; 10 pgs.122Tridgell; Efficient Algorithms for Sorting and Synchronization; Feb. 1999; 115 pgs.123U.S. Appl. No. 10/825,735 filed Apr. 15, 2004, Amendment and Response filed Feb. 23, 2009, 3 pgs.124U.S. Appl. No. 10/825,735 filed Apr. 15, 2004, Amendment and Response mailed Feb. 25, 2009, 2 pgs.125U.S. Appl. No. 10/825,735 filed Apr. 15, 2004, Notice of Allowance mailed Dec. 16, 2008, 17 pgs.126U.S. Appl. No. 10/948,980, Notice of Allowance mailed Apr. 17, 2009, 5 pgs.127U.S. Appl. No. 10/948,980, Notice of Allowance mailed Oct. 15, 2008, 7 pgs.128U.S. Appl. No. 11/031,133, Amendment and Response filed Sep. 15, 2011, 3 pgs.129U.S. Appl. No. 11/031,158, Advisory Action mailed Jul. 9, 2008, 3 pgs.130U.S. Appl. No. 11/031,158, Amendment after Final filed Jun. 17, 2008, 8 pgs.131U.S. Appl. No. 11/031,158, Amendment and Response filed Apr. 5, 2010, 8 pgs.132U.S. Appl. No. 11/031,158, Amendment and Response filed Aug. 18, 2008, 7 pgs.133U.S. Appl. No. 11/031,158, Amendment and Response filed Dec. 21, 2007, 11 pgs.134U.S. Appl. No. 11/031,158, Amendment and Response filed Sep. 11, 2009, 7 pgs.135U.S. Appl. No. 11/031,158, Final Office Action mailed Jan. 4, 2010, 13 pgs.136U.S. Appl. No. 11/031,158, Final Office Action mailed Mar. 17, 2008, 12 pgs.137U.S. Appl. No. 11/031,158, Notice of Allowance mailed Jul. 30, 2010, 11 pgs.138U.S. Appl. No. 11/031,158, Office Action mailed Aug. 29, 2007, 9 pgs.139U.S. Appl. No. 11/031,158, Office Action mailed Jun. 19, 2009, 12 pgs.140U.S. Appl. No. 12/533,437, Amendment after allowance filed Dec. 20, 2011, 2 pgs.141U.S. Appl. No. 12/533,437, Notice of Allowance mailed Sep. 20, 2011, 9 pgs.142U.S. Official Action dated Feb. 2, 2010 cited in U.S. Appl. No. 10/844,893.143U.S. Official Action dated May 18, 2007 cited in U.S. Appl. No. 10/844,907.144U.S. Official Action dated Nov. 14, 2006 cited in U.S. Appl. No. 10/844,907.145U.S. Official Action dated Sep. 3, 2008 cited in U.S. Appl. No. 10/948,980.Referenced byCiting PatentFiling datePublication dateApplicantTitleUS8452732 *May 17, 2012May 28, 2013International Business Machines CorporationIdentifying modified chunks in a data set for storageUS8612392 *May 9, 2011Dec 17, 2013International Business Machines CorporationIdentifying modified chunks in a data set for storageUS8631052Dec 22, 2011Jan 14, 2014Emc CorporationEfficient content meta-data collection and trace generation from deduplicated storageUS8667032Dec 22, 2011Mar 4, 2014Emc CorporationEfficient content meta-data collection and trace generation from deduplicated storageUS8914338 *Dec 22, 2011Dec 16, 2014Emc CorporationOut-of-core similarity matchingUS9037545Sep 19, 2011May 19, 2015Hybir Inc.Group based complete and incremental computer file backup system, process and apparatusUS9110603Dec 11, 2013Aug 18, 2015International Business Machines CorporationIdentifying modified chunks in a data set for storageUS9137331Jul 15, 2011Sep 15, 2015Metalogix International GmbhAdaptive replicationUS20120047284 *Apr 30, 2009Feb 23, 2012Nokia CorporationData Transmission OptimizationUS20120303582 *Nov 29, 2012Syntergy, Inc.Local differential compression* Cited by examinerClassifications U.S. Classification707/693, 707/802International ClassificationG06F17/30Cooperative ClassificationH04L63/123, G06F17/30194European ClassificationH04L63/12A, G06F17/30F8DLegal EventsDateCodeEventDescriptionDec 9, 2014ASAssignmentOwner name: MICROSOFT TECHNOLOGY LICENSING, LLC, WASHINGTONFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:MICROSOFT CORPORATION;REEL/FRAME:034564/0001Effective date: 20141014Jul 29, 2015FPAYFee paymentYear of fee payment: 4RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services