Methods, systems, and media for forming linear combinations of data

• US 8,655,839 B2
• Filed: 03/05/2007
• Issued: 02/18/2014
• Est. Priority Date: 03/03/2006
• Status: Expired due to Fees

• Current Assignee: Trustees Of Columbia University In The City Of New York (Columbia University)
• Original Assignee: Trustees Of Columbia University In The City Of New York (Columbia University)
• Inventors: Kamra, Abhinav, Misra, Vishal, Feldman, Jon, Rubenstein, Daniel
• Primary Examiner(s): Boccio, Vincent F
• Application Number:
  US12/281,457
• Publication Number:
  US 20090222477A1
• Time in Patent Office: 2,542 Days
• Field of Search: 707/693, 707/687, 707/622, 707/706, 707/913, 707/999.003, 707/999.005, 707/999.007, 709/229, 709/230
• US Class Current: 707/622
• CPC Class Codes: G01V 1/003 Seismic data acquisition in general, e.g. survey design G01V1/3808, G01V1/42 take precedence
• CPC Class Codes: H04L 25/02 Details ; arrangements for supplying electrical power along data transmission lines systems for transmitting signals via power distribution lines H04B3/54

Abstract

Methods, systems, and media for forming linear combinations of data are provided. In some embodiments, methods for forming a linear combination of data include: receiving at a device a first codeword, wherein the first codeword comprises a linear combination of at least a first data unit including data, and a second data unit including data; encoding at the device the first codeword and a third data unit including data to form a second codeword, wherein the second codeword includes a linear combination of at least the first data unit, the second data unit, and the third data unit; and transmitting from the device the second codeword.

Claims

1. A method for forming a linear combination of sensor data collected by a plurality of sensor devices including a first sensor device, a second sensor device and a third sensor device, comprising:

receiving at the third sensor device a first codeword transmitted from the first sensor device, wherein the first codeword comprises a linear combination of at least a first data unit, comprising sensor data collected by the first sensor device, and a second data unit, comprising sensor data collected by the second sensor device and transmitted to the first sensor device, wherein the plurality of sensor devices is distributed across a geographical area in a peer-to-peer (P2P) sensor network and wherein each of the plurality of sensor devices in the P2P sensor network is configured for taking measurements of at least one of surrounding physical conditions;

encoding at the third sensor device the first codeword and a third data unit comprising sensor data collected by the third sensor device to form a second codeword, wherein the second codeword comprises a linear combination of at least the first data unit, the second data unit, and the third data unit; and

transmitting from the third sensor device the second codeword.

2. The method of claim 1, wherein the encoding comprises performing a bitwise exclusive-or (XOR) operation on the first codeword and the third data unit.

3. The method of claim 1, wherein the encoding further comprises compressing the third data unit to reduce a size of the third data unit.

4. The method of claim 1, wherein the receiving, the encoding and the transmitting are repeated at predetermined time intervals.

5. The method of claim 1, further comprising periodically acquiring new sensor data at one or more of the first sensor device, the second sensor device, and the third sensor device.

6. The method of claim 1, wherein the first data unit, the second data unit, and the third data unit comprise at least a portion of a file.

7. The method of claim 1, further comprising distributing the first data unit, the second data unit, and the third data unit to one or more additional computing devices in the peer-to-peer network.

8. The method of claim 1, wherein the second codeword further comprises identification information identifying the first data unit, the second data unit, and the third data unit.

9. The method of claim 8, further comprising:

determining a format for storing the identification information based on a number of data units encoded by the second codeword.

10. The method of claim 8, further comprising:

storing the first codeword and a third codeword at the third sensor device, wherein the first codeword and the third codeword share identification information that identifies data units encoded by the first codeword and the third codeword.

11. The method of claim 1, further comprising:

receiving the first codeword at a first point in time; and

decoding the first codeword to recover the first data unit.

12. The method of claim 11, further comprising:

receiving the second codeword at a second point in time that is subsequent to the first point in time; and

decoding the second codeword to recover the third data unit using the first data unit and the second data unit.

13. The method of claim 1, wherein the surrounding physical conditions include surrounding environmental conditions.

14. The method of claim 13, wherein the surrounding environmental conditions include at least one of floods, fires, earthquakes, and landslides.

15. A system for forming a linear combination of sensor data, comprising:

a plurality of sensor devices for collecting sensor data, wherein the plurality of sensor devices is distributed across a geographical area in a peer-to-peer (P2P) sensor network and includes a first sensor device, a second sensor device and a third sensor device and wherein each of the plurality of sensor devices in the P2P sensor network is configured for taking measurements of at least one of surrounding physical conditions,

wherein the first sensor device;

receives a first codeword transmitted from the second sensor device, wherein the first codeword comprises a linear combination of at least a first data unit, comprising sensor data collected by the second sensor device, and a second data unit, comprising sensor data collected by the third sensor device and transmitted to the second sensor device;

encodes the first codeword and a third data unit, comprising sensor data collected by the first sensor device, to form a second codeword, wherein the second codeword comprises a linear combination of at least the first data unit, the second data unit, and the third data unit; and

transmits the second codeword.

16. The system of claim 15, wherein in encoding, the first sensor device performs a bitwise exclusive-or (XOR) operation on the first codeword and the third data unit.

17. The system of claim 15, wherein in encoding, the first sensor device also compresses the third data unit to reduce a size of the third data unit.

18. The system of claim 15, wherein the first sensor device receives, encodes and transmits at predetermined time intervals.

19. The system of claim 15, wherein the first sensor device periodically acquires new sensor data.

20. The system of claim 15, wherein the first data unit, the second data unit, and the third data unit comprise at least a portion of a file.

21. The system of claim 15, wherein the second codeword further comprises information identifying the first data unit, the second data unit, and the third data unit.

22. The system of claim 21, wherein the first sensor device further determines a format for storing the identification information based on a number of data units encoded by the second codeword.

23. The system of claim 21, wherein the first sensor device further stores the first codeword and a third codeword, the first codeword and the third codeword share identification information that identifies data units encoded by the first codeword and the third codeword.

24. The system of claim 23, wherein the first sensor device also:

receives the second codeword at a second point in time that is subsequent to the first point in time; and

decodes the second codeword to recover the third data unit using the first data unit and the second data unit.

25. The system of claim 15, wherein the first sensor device also:

receives the first codeword at a first point in time; and

decodes the first codeword to recover the first data unit.

26. The system of claim 15, wherein the surrounding physical conditions include surrounding environmental conditions.

27. The system of claim 26, wherein the surrounding environmental conditions include at least one of floods, fires, earthquakes, and landslides.

28. A non-transitory computer-readable medium containing computer executable instructions that, when executed by a processor, cause the processor to perform a method for forming a linear combination of sensor data collected by a plurality of sensor devices including a first sensor device, a second sensor device and a third sensor device, the method comprising:

receiving at the third sensor device a first codeword transmitted from athe first sensor device, wherein the first codeword comprises a linear combination of at least a first data unit, comprising sensor data collected by the first sensor device, and a second data unit, comprising sensor data collected by the second sensor device and transmitted to the first sensor device, wherein the plurality of sensor devices is distributed across a geographical area in a peer-to-peer (P2P) sensor network and wherein each of the plurality of sensor devices in the P2P sensor network is configured for taking measurements of at least one of surrounding physical conditions;

encoding at the third sensor device the first codeword and a third data unit comprising sensor data collected by the third sensor device to form a second codeword, wherein the second codeword comprises a linear combination of at least the first data unit, the second data unit, and the third data unit; and

transmitting from the third sensor device the second codeword.

29. The medium of claim 28, wherein the encoding comprises performing a bitwise exclusive-or (XOR) operation on the first codeword and the third data unit.

30. The medium of claim 28, wherein the encoding further comprises compressing the third data unit to reduce a size of the third data unit.

31. The medium of claim 28, wherein the first data unit, the second data unit, and the third data unit comprise at least a portion of a file.

32. The medium of claim 28, wherein the second codeword further comprises identification information identifying the first data unit, the second data unit, and the third data unit.

33. The medium of claim 32, wherein the method further comprises:

determining a format for storing the identification information based on a number of data units encoded by the second codeword.

34. The medium of claim 32, wherein the method further comprises:

storing the first codeword and a third codeword at the third sensor device, wherein the first codeword and the third codeword share identification information that identifies data units encoded by the first codeword and the third codeword.

35. The medium of claim 28, wherein the method further comprises:

receiving the first codeword at a first point in time; and

decoding the first codeword to recover the first data unit.

36. The medium of claim 28, wherein the method further comprises:

receiving the second codeword at a second point in time that is subsequent to the first point in time; and

decoding the second codeword to recover the third data unit using the first data unit and the second data unit.

37. The medium of claim 28, wherein the surrounding physical conditions include surrounding environmental conditions.

38. The medium of claim 37, wherein the surrounding environmental conditions include at least one of floods, fires, earthquakes, and landslides.