Granted Patent B2

US 8,225,060 · App. 12/581,046 · Granted Jul 17, 2012

Abstract

Claims (51)

1. A computer enabled method of storing an input dataset in a storage medium, the method comprising:

storing a copy for each of a plurality of repeatable blocks of data in an input dataset in a storage medium;

finding a location in the storage medium of the copy of a block of data in the input dataset, wherein finding the location comprises: determining a most likely location in the storage medium of the copy of the block of data from one or more blocks of data preceding the block of data based on statistics of past stored data; and if the determined most likely location contains a block of data that matches with the actual block of data, retrieving the location in the storage medium of the copy of the block of data; and

storing the location of the copy of the block of data,

wherein the copy for each of the plurality of repeatable blocks of data is associated with a corresponding set of metadata,

wherein determining the most likely location in the storage medium of the copy of the block of data comprises one of:

determining using an n th order Markov chain,

determining from a block of data preceding the block of data using a first order Markov chain, and

determining from two blocks of data preceding the block of data using a second order Markov chain.

2. The method of claim 1 , wherein the statistics of past stored data comprises statistics of the order of past stored data, and wherein the statistics is stored in one or more sets of metadata, and wherein the one or more sets of metadata are associated with the copy of the one or more blocks of data preceding the block of data.

3. The method of claim 1 , wherein retrieving the location in the storage medium of the copy of the block of data comprises accessing one or more sets of metadata, and wherein the one or more sets of metadata are associated with the copy of the one or more blocks of data preceding the block of data.

4. The method of claim 1 , wherein storing the location of the copy of the block of data comprises storing the location in a set of metadata representing the input dataset.

5. A non-transitory computer-readable storage medium comprising computer executable instructions for storing an input dataset in a storage medium, the instructions comprising:

storing a copy for each of a plurality of repeatable blocks of data in an input dataset in a storage medium;

finding a location in the storage medium of the copy of a block of data in the input dataset, wherein finding the location comprises:

determining a most likely location in the storage medium of the copy of the block of data from one or more blocks of data preceding the block of data based on statistics of past stored data; and

if the determined most likely location contains a block of data that matches with the actual block of data, retrieving the location in the storage medium of the copy of the block of data; and

storing location of the copy of the block of data,

wherein the copy for each of the plurality of repeatable blocks of data is associated with a corresponding set of metadata,

wherein determining the most likely location in the storage medium of the copy of the block of data comprises one of:

determining using an n th order Markov chain,

determining from a block of data preceding the block of data using a first order Markov chain, and

determining from two blocks of data preceding the block of data using a second order Markov chain.

6. The non-transitory computer-readable storage medium of claim 5 , wherein the statistics of past stored data comprises statistics of the order of past stored data, and wherein the statistics is stored in one or more sets of metadata, and wherein the one or more sets of metadata are associated with the copy of the one or more blocks of data preceding the block of data.

7. The non-transitory computer-readable storage medium of claim 5 , wherein retrieving the location in the storage medium of the copy of the block of data comprises accessing one or more sets of metadata, and wherein the one or more sets of metadata are associated with the copy of the one or more blocks of data preceding the block of data.

8. The non-transitory computer-readable storage medium of claim 5 , wherein storing the location of the copy of the block of data comprises storing the location in a set of metadata representing the input dataset.

9. A computer enabled method of storing an input dataset in a storage medium, the method comprising:

storing a copy for each of a plurality of repeatable blocks of data in an input dataset in a storage medium, wherein each copy is associated with one of a plurality of clusters;

finding a location in the storage medium of the copy of a block of data in the input dataset, wherein finding the location comprises:

determining a most likely location in the storage medium of a first cluster from a second at least one cluster based on statistics of past stored data, wherein the first cluster is associated with the block of data, and wherein the second at least one cluster is associated with the one or more blocks of data preceding the block of data; and

if the determined most likely location contains a first cluster associated with the block of data, retrieving the location in the storage medium of the copy of the block of data;

and storing the location of the copy of the block of data,

wherein each of the plurality of clusters is associated with a corresponding set of metadata,

wherein determining the most likely location in the storage medium of the first cluster comprises one of:

determining from a cluster associated with a block of data preceding the block of data using a first order Markov chain,

determining from one or more clusters associated with two blocks of data preceding the block of data using a second order Markov chain.

10. The method of claim 9 , wherein the statistics of past stored data comprises statistics of the order of past stored data, and wherein the statistics is stored in one or more sets of metadata associated with one or more clusters, and wherein the one or more clusters are associated with the copy of the one or more blocks of data preceding the block of data.

11. The method of claim 9 , wherein retrieving the location in the storage medium of the copy of the block of data comprises accessing one or more sets of metadata associated with one or more clusters, and wherein the one or more clusters are associated with the copy of the one or more blocks of data preceding the block of data.

12. Computer-readable storage medium comprising computer executable instructions for storing an input dataset in a storage medium, the instructions comprising:

storing a copy for each of a plurality of repeatable blocks of data in an input dataset in a storage medium, wherein each copy is associated with one of a plurality of clusters;

finding a location in the storage medium of the copy of a block of data in the input dataset, wherein finding the location comprises:

determining a most likely location in the storage medium of a first cluster from a second at least one cluster based on statistics of past stored data, wherein the first cluster is associated with the block of data and the second at least one cluster is associated with the one or more blocks of data preceding the block of data; and

if the determined most likely location contains a first cluster associated with the block of data, retrieving the location in the storage medium of the copy of the block of data;

and

storing the location of the copy of the block of data,

wherein each of the plurality of clusters is associated with a corresponding set of metadata,

wherein determining the most likely location in the storage medium of the first cluster comprises one of:

determining from a cluster associated with a block of data preceding the block of data using a first order Markov chain, and

determining from one or more clusters associated with two blocks of data preceding the block of data using a second order Markov chain.

13. The computer-readable storage medium of claim 12 , wherein the statistics of past stored data comprises statistics of the order of past stored data, and wherein the statistics is stored in one or more sets of metadata associated with one or more clusters, and wherein the one or more clusters are associated with the copy of the one or more blocks of data preceding the block of data.

14. The computer-readable storage medium of claim 12 , wherein retrieving the location in the storage medium of the copy of the block of data comprises accessing one or more sets of metadata associated with one or more clusters, and wherein the one or more clusters are associated with the copy of the one or more blocks of data preceding the block of data.

Assignments (14)