Patent ID: 8396839

Claim:
A method comprising: receiving an indication of an input identifying a subset of data to be provided as output, wherein the subset of data has been stored in de-duplicated form; identifying a plurality of containers that includes one or more data segments comprising the subset of data, wherein each of the plurality of containers may include one or more segments not included in the subset of data; determining, for each of the plurality of containers, whether corresponding container data has already been included in an output stream based at least in part on a data structure comprising for each of at least a subset of container stored on the de-duplicated storage system an indication of whether or not the corresponding container data has been included in the output stream; retrieving a corresponding de-duplicated container data for each container that is determined to comprise container data that has not been previously included in the output stream; providing to the output stream the retrieved container data for each container that includes container data that has not been previously included in the output stream; and for each container from which corresponding container data is included in the output, updating the corresponding value in the data structure.