Patent ID: 8762338

Claim:
A non-transitory computer-accessible storage medium comprising program instructions for analyzing backup objects maintained by a de-duplication server, wherein the program instructions are executable by a processor to: maintain a plurality of first backup objects, wherein each first backup object comprises one or more references to one or more second backup objects of a plurality of second backup objects, and wherein each second backup object comprises at least one reference back to a first backup object, wherein references comprise pointers to memory addresses of referenced backup objects, wherein the first backup objects are backup objects at a higher hierarchical level than the second backup objects in a data duplication system; for each respective first backup object of the plurality of first backup objects: analyze the respective first backup object to determine the one or more second backup objects referred to by the respective first backup object; generate a first command for each respective second backup object of the one or more second backup objects, wherein the first command is configured for use in verifying that the respective second backup object refers back to the respective first backup object; wherein the analyzing and the generating for each of the plurality of first backup objects produces a plurality of commands, each command of the plurality of commands being associated with a second backup object; sort the plurality of commands into a storage device access order, wherein the storage device access order is an order of sequential storage locations on the storage device for the second backup objects; and verify that each second backup object of the plurality of second backup objects refers back to one or more first backup objects that refer to the second backup object, wherein the verification implements the sorted plurality of commands in the storage device access order.