Efficient algorithm for finding candidate objects for remote differential compression
First Claim
Patent Images
1. 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.
2 Assignments
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
45 Claims
-
1. 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23)
-
-
24. 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. - View Dependent Claims (25, 26, 27, 28, 29, 30, 31, 32, 33)
-
-
34. 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 (35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45)
-
Specification