TECHNIQUES FOR DATA SYNCHRONIZATION USING COMPRESSIVE SENSING

• US 20150234908A1
• Filed: 09/24/2013
• Published: 08/20/2015
• Est. Priority Date: 09/24/2012
• Status: Abandoned Application

• Current Assignee: President and Fellows of Harvard College (Harvard Corporation)
• Original Assignee: President and Fellows of Harvard College (Harvard Corporation)
• Inventors: Kung, Hsiang-Tsung, Lin, Chit-Kwan
• Application Number:
  US14/429,108
• Publication Number:
  US 20150234908A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/1744 using compression, e.g. sparse files
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: G06F 16/955 using information identifiers, e.g. uniform resource locators [URL]
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes

Abstract

Techniques for data synchronization between a first computing device coupled to at least one memory storing current data and a second computing device coupled to at least a second memory storing first encoded data and a copy of prior data. The first device may perform a method comprising: encoding the current data using a compressive sensing encoding technique to obtain second encoded data; and transmitting the second encoded data to the second computing device. The second device may perform a method comprising receiving second encoded data from the first computing device; decoding the second encoded data using a compressive sensing decoding technique to obtain decoded data; and obtaining a copy of the current data by using the decoded data and the copy of prior data.

Claims

1. A method for data synchronization between a first computing device coupled to at least one memory storing current data and a second computing device, the method performed by the first computing device, the method comprising:

encoding the current data using a compressive sensing encoding technique to obtain first encoded data; and

transmitting the first encoded data to the second computing device.

2. The method of claim 1, further comprising:

in response to determining that at least a threshold number of changes have been made to the current data to produce updated data, encoding the updated data using the compressive sensing encoding technique to obtain second encoded data; and

transmitting the second encoded data to the second computing device.

3. The method of claim 1, wherein the current data comprises a plurality of bits, the first encoded data comprises a plurality of encoded bits, and wherein encoding the current data using the compressive sensing encoding technique comprises:

calculating a plurality of random linear combinations of bits in the plurality of bits to obtain the plurality of encoded bits.

4. The method of claim 3, wherein calculating the plurality of random linear combinations of bits comprises:

calculating at least one weighted sum of bits in the first plurality of bits, with bits being weighted by weights obtained at least in part by using at least one probability distribution.

5. The method of claim 4, wherein the at least one probability distribution comprises a distribution of a Bernoulli random variable and/or a distribution of a Gaussian random variable.

6. The method of claim 4, further comprising:

transmitting the weights obtained at least in part by using at least one probability distribution to at least the second computing device.

7. The method of claim 1, wherein the first computing device is a mobile device.

8-9. -9. (canceled)

10. A system for data synchronization, comprising:

at least one computing device; and

at least one memory storing processor-executable instructions that, when executed by the at least one computing device, cause the at least one computing device to;

encode current data using a compressive sensing encoding technique to obtain first encoded data; and

transmit the first encoded data to at least a second computing device.

11. The system of claim 10, wherein the at least one computing device is further configured to:

in response to determining that at least a threshold number of changes have been made to the current data to produce updated data, encode the updated data using the compressive sensing encoding technique to obtain second encoded data; and

transmit the second encoded data to at least the second computing device.

12. The system of claim 10, wherein the current data comprises a plurality of bits, the first encoded data comprises a plurality of encoded bits, and wherein the at least one computing device is configured to encode the current data using the compressive sensing encoding technique at least in part by:

calculating a plurality of random linear combinations of bits in the plurality of bits to obtain the plurality of encoded bits.

13. The system of claim 12, wherein calculating the plurality of random linear combinations of bits comprises:

calculating at least one weighted sum of bits in the first plurality of bits, with bits being weighted by weights obtained at least in part by using at least one probability distribution.

14. The system of claim 13, wherein the at least one probability distribution comprises a distribution of a Bernoulli random variable and/or a distribution of a Gaussian random variable.

15. The system of claim 13, wherein the at least one computing device is further configured to:

transmit the weights obtained at least in part by using at least one probability distribution to at least the second computing device.

16. The system of claim 10, wherein the at least one computing device comprises a mobile device.

17-27. -27. (canceled)

28. A method for data synchronization between a first computing device coupled to at least a first memory storing current data and at least a second computing device coupled to at least a second memory storing first encoded data and a copy of prior data, the method performed by the second computing device, the method comprising:

receiving second encoded data from the first computing device;

decoding the second encoded data using a compressive sensing decoding technique to obtain decoded data; and

obtaining a copy of the current data by using the decoded data and the copy of prior data.

29. The method of claim 28, wherein decoding the second encoded data further comprises using the first encoded data to perform the decoding.

30. The method of claim 29, wherein decoding the second encoded data comprises:

applying the compressive sensing decoding technique to a difference between the second encoded data and the first encoded data.

31. The method of claim 28, further comprising:

receiving a plurality of weights from the first computing device, wherein the plurality of weights were used to obtain the first encoded data and the second encoded data.

32. The method of claim 28, further comprising:

storing the second encoded data in at least the second memory.

33. The method of claim 28, wherein the first computing device is a mobile device.

34-48. -48. (canceled)