Efficient algorithm for finding candidate objects for remote differential compression
AssigneeMicrosoft Corporation
InventorsMark Manasse, Dan Teodosiu, Akhil Wable
Life of this patent
Estimating the term…
Abstract
The present invention finds candidate objects for remote differential compression. Objects are updated between two or more computing devices using remote differential compression (RDC) techniques such that required data transfers are minimized. An algorithm provides enhanced efficiencies for allowing the receiver to locate a set of objects that are similar to the object that needs to be transferred from the sender. Once this set of similar objects has been found, the receiver may reuse any chunks from these objects during the RDC algorithm.
Claims45
A method for identifying objects for remote differential compression, comprising:
- calculating traits for an object;
- using the traits to identify candidate objects that are at least somewhat similar to the object;
- and
- selecting final objects from the identified candidate objects.
A computer-readable medium having computer executable instructions for identifying objects for remote differential compression, comprising:
- partitioning an object into chunks;
- computing signatures for each of the object chunks;
- grouping the signatures into shingles;
- computing at least one shingle signature for each of the shingles;
- mapping the shingle signatures into image sets;
- calculating pre-traits from the image sets;
- and
- computing the traits using the pre-traits, wherein the traits are smaller in size as compared to the pre-traits using the traits to identify candidate objects that are at least somewhat similar to the object;
- and
- selecting final objects from the identified candidate objects.
A system for identifying objects for remote differential compression, comprising:
- a remote device configured to perform steps, comprising:
- receive a request for an Object OB;
- send a set of traits of Object OB to a local device;
- partition Object OB into chunks and compute signatures for each of the chunks;
- send the list of chunk signatures to the local device;
- and
- provide requested chunks when requested;
- and
- the local device configured to perform steps, comprising:
- request Object OB from the remote device;
- receive the set of traits of Object OB from the remote device;
- use the set of traits of Object OB to identify similar objects that it already stores on the local device;
- partition the similar objects into chunks;
- compute signatures for each of the similar object chunks;
- receive the list of chunk signatures from the remote device;
- compare the received signatures against the locally computed signatures;
- request chunks from the remote device that did not match in the comparison;
- receive the requested chunks;
- and
- reconstruct Object OB using the received chunks and chunks reused from the similar objects.
Dependencies are inferred from the claim text.