Efficient algorithm for finding candidate objects for remote differential compression
First Claim
Patent Images
1. 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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
12 Claims
-
1. 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
-
Specification