# US 2018/0024746 A1 · Methods of encoding and storing multiple versions of data, method of decoding encoded multiple versions of data and distributed storage system

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2018/0024746 A1
- Document ID: US20180024746A1
- Status: Published application
- Kind: A1
- Application number: 15/550,317
- Filed: 2016-02-12
- Published: 2018-01-25
- Earliest claimed: 2015-02-13
- Applicants: Nanyang Technological University
- Inventors: Harshan Jagadeesh; Anwitaman Datta; Frederique Oggier
- Web page: https://patentgrep.com/patent/US20180024746A1

## CPC

- G06F 3/064: {Management of blocks}
- G06F 3/0608: {Saving storage space on storage systems}
- G06F 3/0641: {De-duplication techniques}
- G06F 3/067: {Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]}
- G06F 11/1012: {using codes or arrangements adapted for a specific type of error (G06F11/1048 takes precedence)}
- H03M 13/154: {Error and erasure correction, e.g. by using the error and erasure locator or Forney polynomial}
- H03M 13/373: {with erasure correction and erasure determination, e.g. for packet loss recovery or setting of erasures for the decoding of Reed-Solomon codes}
- H03M 13/3761: {using code combining, i.e. using combining of codeword portions which may have been transmitted separately, e.g. Digital Fountain codes, Raptor codes or Luby Transform [LT] codes}
- G06F 11/2094: {Redundant storage or storage space (G06F11/2056 takes precedence)}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H03M: CODING; DECODING; CODE CONVERSION IN GENERAL (using fluidic means F15C4/00; optical analogue/digital converters G02F7/00; coding, decoding or code conversion, specially adapted for particular applications, see the relevant subclasses, e.g. G01D, G01R, G06F, G06T, G09G, G10L, G11B, G11C, H04B, H04L, H04M, H04N; ciphering or deciphering for cryptography or other purposes involving the need for secrecy G09C)

## Abstract

There is provided a method of encoding multiple versions of data. The method includes computing a difference between a version of a data object and a subsequent version of the data object to produce a difference object, determining a sparsity level of the difference 10 object; determining whether the sparsity level satisfies a predetermined condition; and compressing the difference object to produce a compressed difference object and erasure encoding the compressed difference object to produce a codeword if the sparsity level is determined to satisfy the predetermined condition. There is also provided a corresponding method of decoding encoded multiple versions of data, a method of storing multiple 15 versions of data in a distributed storage system, and a distributed storage system.

## Claims

### Claim 1

A method of encoding multiple versions of data, the method comprising:
computing a difference between a version of a data object and a subsequent version of the data object to produce a difference object;
determining a sparsity level of the difference object;
determining whether the sparsity level satisfies a predetermined condition; and
compressing the difference object to produce a compressed difference object and erasure encoding the compressed difference object to produce a codeword if the sparsity level is determined to satisfy the predetermined condition.

### Claim 2 (depends on 1)

The method according to claim 1, wherein compressing the difference object comprises applying compressed sensing to the difference object to produce the compressed difference object.

### Claim 3 (depends on 2)

The method according to claim 2, wherein applying compressed sensing to the difference object comprises applying a measurement matrix to the difference object to produce the compressed difference object, wherein the measurement matrix satisfies a condition that every of a number of columns of the measurement matrix are linearly independent, the number being two times the sparsity level of the difference object.

### Claim 4 (depends on 1)

The method according to claim 1, wherein the difference object comprises a matrix representing the difference between said version of the data object and said subsequent version of the data object.

### Claim 5 (depends on 1)

The method according to claim 1, wherein the predetermined condition relates to a sparsity level threshold.

### Claim 6 (depends on 1)

The method according to claim 1, wherein erasure encoding the compressed difference object comprises applying an erasure code to the compressed difference object, the erasure code being selected from a set of erasure codes based on the sparsity level of the difference object determined, the set of erasure codes comprising a plurality of erasure codes for a plurality of sparsity levels, respectively.

### Claim 7 (depends on 6)

The method according to claim 6, wherein the data object is divided into a plurality of data blocks and the predetermined condition is whether the sparsity level of the difference object is less than half of the number of the plurality of data chunks.

### Claim 8 (depends on 1)

The method according to claim 1, wherein one erasure code is provided for all sparsity levels that satisfy the predetermined condition, and erasure encoding the compressed difference object comprises applying said one erasure code to the compressed difference object.

### Claim 9 (depends on 8)

The method according to claim 8, wherein the predetermined condition is whether the sparsity level of the difference object is less than or equal to a predetermined threshold level.

### Claim 10 (depends on 8)

The method according to claim 8, wherein compressing the difference object comprises applying a Cauchy Matrix to the difference object to produce the compressed difference object.

### Claim 11 (depends on 1)

The method according to claim 1, wherein a plurality of erasure codes is provided for a plurality of sparsity levels, and erasure encoding the compressed difference object comprises applying one of the plurality of erasure codes to the compressed difference object.

### Claim 12 (depends on 1)

The method according to claim 1, further comprising erasure encoding the difference object to produce a codeword if the sparsity level of the difference object is determined to not satisfy the predetermined condition.

### Claim 13 (depends on 1)

The method according to claim 1, further comprising erasure encoding said subsequent version of the data object to produce a codeword if the sparsity level of the difference object is determined to not satisfy the predetermined condition.

### Claim 14 (depends on 1)

The method according to claim 1, wherein the codeword produced is for said subsequent version of the data object.

### Claim 15 (depends on 1)

The method according to claim 1, wherein the codeword produced is for said version of the data object.

### Claim 16 (depends on 15)

The method according to claim 15, further comprising erasure encoding said subsequent version of the data object to produce a codeword for said subsequent version of the data object.

### Claim 17 (depends on 1)

The method according to claim 1, further comprising distributing components of the codeword produced to a plurality of storage nodes for storage.

### Claim 18 (depends on 1)

The method according to claim 1, further comprising zero padding the data object with a plurality of zero pads such that the data object comprises file contents and the plurality of zero pads.

### Claim 19 (depends on 18)

The method according to claim 18, wherein the number of zero pads in said subsequent version of the data object increases or decreases with respect to the number of zero pads in said version of the data object based on a change in the size of the file contents in said subsequent version of the data object with respect to the size of the file contents in said version of the data object.

### Claim 20 (depends on 19)

The method according to claim 19, wherein:
the number of zero pads in said subsequent version of the data object decreases with respect to the number of zero pads in said version of the data object when the change results in an increase in the size of the file contents in the subsequent version of the data object with respect to the size of the file contents in said version of the data object, and
the number of zero pads in said subsequent version of the data object increases with respect to the number of zero pads in said version of the data object when the change results in a decrease in the size of the file contents in said subsequent version of the data object with respect to the size of the file contents in said version of the data object.

### Claim 21

A method of decoding encoded multiple versions of data, the encoded multiple versions of data comprising a plurality of codewords, each codeword corresponding a respective version of a data object, the method comprising:
erasure decoding a codeword corresponding to a version of the data object from the plurality of codewords to obtain a compressed difference object, the difference object representing a difference between said version of the data object and another version of the data object;
decompressing the compressed difference object to recover the difference object; and
recovering said version of the data object based on at least the recovered difference object and said another version of the data object.

### Claim 22

An encoder system for encoding multiple versions of data, the encoder comprising:
a difference object generator module configured to compute a difference between a version of a data object and a subsequent version of the data object to produce a difference object;
a sparsity level determination module configured to determine a sparsity level of the difference object;
a sparsity level comparator module configured to determine whether the sparsity level satisfies a predetermined condition;
a compression module configured to compress the difference object to produce a compressed difference object; and
an erasure encoder configured to encode the compressed difference object to produce a codeword,
wherein the compression module is configured to compress the difference object and the erasure encoder is configured to encode the compressed difference object if the sparsity level is determined by the sparsity level comparator module to satisfy the predetermined condition.

### Claim 23 (depends on 22)

The encoder system according to claim 22, wherein the predetermined condition relates to a sparsity level threshold.

### Claim 24

A distributed storage system, the system comprising:
a plurality of secondary servers, each secondary server configured to store codewords for multiple versions of a data object; and
a group server associated with the plurality of secondary servers, wherein
each secondary server comprises a difference object generator module configured to compute a difference between a version of the data object and a subsequent version of the data object to produce a difference object, and
the group server comprises:
a sparsity level determination module configured to determine a sparsity level of the difference object received from the secondary server;
a sparsity level comparator module configured to determine whether the sparsity level satisfies a predetermined condition;
a compression module configured to compress the difference object to produce a compressed difference object; and
an erasure encoder configured to encode the compressed difference object to produce a codeword for storing in the secondary server,
wherein the compression module is configured to compress the difference object and the erasure encoder is configured to encode the compressed difference object if the sparsity level is determined by the sparsity level comparator module to satisfy the predetermined condition.

### Claim 25 (depends on 24)

The distributed storage system according to claim 24, further comprising a master server configured for facilitating communication between a client and a plurality of the group servers for storing multiple versions of data in the plurality of secondary servers.

### Claim 26 (depends on 24)

The distributed storage system according to claim 24, wherein the predetermined condition relates to a sparsity level threshold.

### Claim 27

A method of storing multiple versions of data in a distributed storage system, the distributed storage system comprising:
a plurality of secondary servers, each secondary server configured to store codewords for multiple versions of a data object; and
a group server associated with the plurality of secondary servers,
the method comprising:
computing, at one of the plurality of secondary servers, a difference between a version of a data object and a subsequent version of the data object to produce a difference object;
determining, at the group server, a sparsity level of the difference object received from the secondary server;
determining, at the group server, whether the sparsity level satisfies a predetermined condition; and
compressing, at the group server, the difference object to produce a compressed difference object and erasure encoding, at the group server, the compressed difference object to produce a codeword for storage in the secondary server if the sparsity level is determined to satisfy the predetermined condition.

### Claim 28 (depends on 27)

The distributed storage system according to claim 27, wherein the predetermined condition relates to a sparsity level threshold.

### Claim 29

A computer program product, embodied in one or more non-transitory computer-readable storage mediums, comprising instructions executable by one or more computer processors to perform a method of encoding multiple versions of data, the method comprising:
computing a difference between a version of a data object and a subsequent version of the data object to produce a difference object;
determining a sparsity level of the difference object;
determining whether the sparsity level satisfies a predetermined condition; and
compressing the difference object to produce a compressed difference object and erasure encoding the compressed difference object to produce a codeword if the sparsity level is determined to satisfy the predetermined condition.