Method and apparatus for generating user-level difference information about two data sets

A computer implemented method of generating user-level difference information relating to a first data set and a second data set, the method comprising the steps of:

• A) acquiring difference information relating to the first and second data sets, the first and second data sets each structured as a hierarchy of nodes, each hierarchy of nodes including a root, each node being a file or a directory;
• B) identifying nodes which represent differences between the first and second data sets based on the change information;
• C) for each node which represents a difference between the first and second data sets,
• 1) indicating difference information for the node in a change map,
• 2) creating an entry representing the node in a traversal map,
• 3) creating an entry representing the parent of the node in the traversal map if such an entry does not already exist in the traversal map,
• 4) creating an entry in a child map, indicating that the node is a child of the parent, and
• 5) repeating steps 3) and 4) until reaching the root or a node already represented in the traversal map;
• and
• D) traversing trees representing the first and second data sets by successively examining nodes in the hierarchy to generate a human-readable or computer application-readable output including user-level difference information between the first and second data sets, while using the traversal map and a depth-first algorithm to avoid traversing at least some nodes of the trees during said traversing.

A processing system comprising:

• a processor;
• and
• a memory accessible to the processor and containing software which, when executed by the processor, causes the processing system to perform a process including
• generating user-level information that represents differences between a first data set and a second data set, the first and second data sets each structured as a hierarchy of nodes,
• building a traversal map that identifies nodes of one or both of the first and second data sets, each node in the traversal map being a node for which a difference has been detected between the first and second data sets,
• traversing a hierarchical structure by successively examining nodes in the hierarchy to generate and output user-level difference information representing differences between the first and second data sets, wherein said traversing includes referring to the traversal map during said traversing and ignoring nodes which are not represented in the traversal map,
• building a child map that includes information identifying parent-child relationships of nodes of the first and second data sets;
• and
• using the child map to prefetch nodes during said traversing.

A storage system comprising:

• means for servicing a request from a client to access data stored in a set of storage devices;
• means for acquiring information representing differences between a first data set and a second data set, at least one of the first and second data sets being stored in the set of storage devices, the first and second data sets each structured as a hierarchy of nodes;
• means for building a traversal map that identifies only nodes for which a difference has been detected between the first and second data sets;
• means for traversing a hierarchy of nodes representing the first or second data set by successively examining nodes in the hierarchy, to generate an output including user-level difference information about the first and second data sets, including using the traversal map to avoid traversing at least some nodes such that nodes not represented in the traversal map are skipped during said traversing;
• means for building a child map that includes information identifying parent-child relationships of nodes of the first and second data sets;
• and
• means for using the child map to prefetch nodes during said traversing.

A computer implemented method comprising:

• acquiring information representing differences between a first data set and a second data set, the first and second data sets each including a plurality of nodes;
• building a third data set that identifies only nodes for which a difference has been detected between the first and second data sets;
• processing a hierarchy of nodes by successively examining nodes in the hierarchy to generate an output including file path and file name information for the first and second data sets, including using the third data set to identify nodes in the hierarchy that do not need to be processed for the purpose of generating said output, and skipping the nodes that are not identified in said processing;
• building a child map that includes information identifying parent-child relationships of nodes of the first and second data sets;
• and
• using the child map to prefetch nodes during said processing.

A computer implemented method comprising:

• acquiring non-user-level difference information representing differences between a first data set and a second data set, the first and second data sets each including a plurality of nodes;
• building a traversal map that identifies only nodes for which a difference has been detected between the first and second data sets;
• and
• traversing a hierarchy of nodes by successively examining nodes in the hierarchy in a depth-first order, to generate an output including user-level difference information about the first and second data sets based on the non-user-level difference information, while skipping nodes not represented in the traversal map during said traversing;
• building a child map that includes information identifying parent-child relationships of nodes of the first and second data sets;
• and
• using the child map to prefetch nodes during said traversing.