Identifying characteristics in sets of organized items

• US 7,908,254 B2
• Filed: 06/10/2005
• Issued: 03/15/2011
• Est. Priority Date: 06/10/2005
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Suermondt, Henri Jacques, Eshghi, Kave
• Primary Examiner(s): Rones; Charles
• Assistant Examiner(s): KUDDUS, DANIEL A
• Application Number:
  US11/149,509
• Publication Number:
  US 20060282475A1
• Time in Patent Office: 2,104 Days
• Field of Search: None
• US Class Current: 707/698
• CPC Class Codes: G06F 16/20 of structured data, e.g. relational data

Abstract

A system and method is provided for determining characteristics of sets of organized items.

In an illustrative implementation, a first set of organized items as a compare-from location is identified, and a second set of organized items as a compare-to location is also identified. In an illustrative operation, a recursive intrinsic reference representing the first set of organized items is determined so that the recursive intrinsic reference is an intrinsic reference to an item containing a second intrinsic reference. A discrepancy is determined between the first set of organized items and the second set of organized items using the recursive intrinsic reference.

Claims

1. A computer implemented method to determine characteristics of sets of organized items comprising:

identifying, by a computer, a first set of organized items as a compare-from location;

identifying, by the computer, a second set of organized items as a compare-to location;

determining, by the computer, a first recursive intrinsic reference representing the first set of organized items;

determining, by the computer, a second recursive intrinsic reference representing the second set of organized items, wherein each of the first and second recursive intrinsic references is an intrinsic reference to an item containing another intrinsic reference, wherein each of the first and second recursive intrinsic references is a reference to a node in a corresponding hash directed-acyclic graph (HDAG), and wherein the HDAG is an acyclic graph in which higher-level nodes include references to lower-level nodes that are based on hashes of content within said respective lower-level nodes; and

determining, by the computer, a discrepancy between the first set of organized items and the second set of organized items using the first and second recursive intrinsic references, wherein determining the discrepancy comprises using one or more algorithms to process pairs of HDAGs.

2. The method of claim 1 further comprising generating a first HDAG of intrinsic references, including recursive intrinsic references, that represents the first set of organized items, and generating a second HDAG of intrinsic references, including recursive intrinsic references, that represents the second set of organized items, wherein using the one or more algorithms to process pairs of HDAGs comprises using the one or more algorithms to process the first HDAG and the second HDAG.

3. The method as recited in claim 2 wherein each of the first and second recursive intrinsic references is a result of a hash function applied to a node in a corresponding one of the first and second HDAGs.

4. The method as recited in claim 2, further comprising generating a mapping from first node in the first HDAG to a second node in the second HDAG.

5. The method of claim 2 wherein each intrinsic reference is based on content of a referenced item and each recursive intrinsic reference references a target item that includes a target intrinsic reference.

6. The method of claim 5 wherein the discrepancy is determined by searching for nodes in the first HDAG that match nodes in the second HDAG.

7. The method of claim 6 wherein the searching is performed by collecting a first set of nodes in the first HDAG and a second set of nodes in the second HDAG, and performing a selected cross check on the first set of nodes and the second set of nodes.

8. The method as recited in claim 1 wherein the items in each of the first and second sets are organized as directories.

9. The method as recited claim 1 wherein determining the discrepancy comprises identifying an item in the first set that is not also in the second set.

10. The method as recited in claim 1 wherein determining the discrepancy comprises identifying an item in the second set that is not also in the first set.

11. The method as recited in claim 1 wherein determining the discrepancy comprises determining a difference in organization of the items in the first and second sets.

12. The method as recited in claim 1, further comprising computing a metric representing the discrepancy.

13. The method as recited in claim 12 where computing the metric comprises computing a degree to which an organization of the items in the first and second sets is different.

14. The method as recited in claim 12, further comprising obtaining an attribute of a given one of the items, wherein the computing the metric makes use of the attribute.

15. The method as recited in claim 14 wherein the attribute is a size of the given item.

16. The method as recited in claim 1, further comprising creating a visualization of the discrepancy.

17. The method as recited in claim 1 wherein the discrepancy is identified through a selected cross check on all recursive intrinsic references from the compare-to and compare-from locations.

18. The method as recited in claim 1 wherein the discrepancy comprises identification of a file in the “

compare-from”

location that partially overlaps a file in the “

compare-to”

location.

19. The method as recited in claim 1, further comprising determining each of the first and second recursive intrinsic references using a chunking algorithm.

20. The method as recited in claim 1 wherein determining the discrepancy comprises determining the discrepancy between digital picture files on a laptop computer and digital picture files on a personal computer.

21. The method as recited in claim 1 wherein determining the discrepancy comprises determining the discrepancy between a back-up of data found on a back-up storage device and data found in a computing environment.

22. The method as recited in claim 21 further comprising recovering the data found on the back-up storage device and not found in the computing environment onto the computing environment.

23. The method of claim 1 wherein each of the first and second recursive intrinsic references is based on content of a particular item containing another intrinsic reference and the another intrinsic reference is based on content of a second item referenced by the another intrinsic reference.

24. The method of claim 23 wherein the first and second recursive intrinsic references comprises a hash of content of the particular item containing the another intrinsic reference and the another intrinsic reference comprises a hash of content of the second item.

25. A computer readable storage medium having computer readable instructions to instruct a computer to perform a method comprising:

identifying a first set of organized items from a compare-from location;

identifying a second set of organized items from a compare-to location;

determining a first recursive intrinsic reference representing the first set of organized items;

determining a second recursive reference representing the second set of organized items, wherein each of the first and second recursive intrinsic references is a reference to a node in a corresponding hash directed-acyclic graph (HDAG), and wherein the HDAG is an acyclic graph in which higher-level nodes include references to lower-level nodes that are based on hashes of content within respective lower-level nodes; and

determining discrepancies between the first set of organized items and the second set of organized items using the first and second recursive intrinsic references, wherein determining the discrepancies comprises using one or more algorithms to process pairs of HDAGs.

26. The computer readable storage medium as claimed in claim 25, wherein the instructions upon execution are to further instruct the computer to perform:

generating a first HDAG of intrinsic references, including recursive intrinsic references, that represents the first set of organized items, and generating a second HDAG of intrinsic references, including recursive intrinsic references, that represents the second set of organized items, wherein using the one or more algorithms to process pairs of HDAGs comprises using the one or more algorithms to process the first HDAG and the second HDAG.

27. A computer implemented method to determine characteristics of sets of organized items comprising:

identifying, by a computer, a first set of organized items from a compare-from location;

identifying, by the computer, a second set of organized items from a compare-to location;

determining, by the computer, a first hash based directed acyclic graphs (HDAG) for the items from the compare-from location and a second HDAG for the items from the compare-to location;

determining, by the computer, overlap between the items in the compare-from location and the compare-to location using the first HDAG and the second HDAG;

determining, by the computer, discrepancies in organization between the first set of organized items and the second set of organized items using the first HDAG and the second HDAG; and

visualizing results of the overlap and discrepancy determinations in a graphical representation,

wherein each of the first HDAG and the second HDAG is an acyclic graph in which higher-level nodes include references to lower-level nodes that are based on hashes of content within said respective lower-level nodes.

28. The method of claim 27 wherein the discrepancies are determined by searching for nodes in the first HDAG that match nodes in the second HDAG, and wherein the searching is performed by collecting a first set of nodes in the first HDAG and a second set of nodes in the second HDAG and performing a selected cross check on the first set of nodes and the second set of nodes.

29. A computer readable storage medium storing instructions, executable by a computer system to identify characteristics of sets of organized items, comprising:

receiving a first set of organized items and a second set of organized items as input;

generating a first hash based directed acyclic graph (HDAG) for the first set and a second HDAG for the second set;

generating a mapping between nodes of the first HDAG and the second HDAG;

computing overlap and discrepancies between the first set of organized items and the second set of organized items based on the mapping between HDAG nodes in the first and second HDAGs;

generating a graphical representation of the computed overlap and discrepancies,

wherein each of the first HDAG and the second HDAG is an acyclic graph in which higher-level nodes include references to lower-level nodes that are based on hashes of content within said respective lower-level nodes; and

computing a first recursive intrinsic reference based on an HDAG node of the first HDAG, and computing a second recursive intrinsic reference based on an HDAG node of the second HDAG, wherein computing the overlap and discrepancies is based on comparing the first and second recursive intrinsic references, wherein each of the first and second recursive intrinsic references is an intrinsic reference to an item containing another intrinsic reference.

30. A computer system comprising:

storage media to store a first set of organized items and a second set of organized items; and

a processor configured to;

determine a first hash based directed acyclic graph (HDAG) for the first set and a second HDAG for the second set;

compute overlap and discrepancies between the first set of organized items and the second set of organized items based on the first HDAG and the second HDAG; and

generate a graphical representation of the computed overlap and discrepancies,

wherein each of the first HDAG and the second HDAG is an acyclic graph in which higher-level nodes include references to lower-level nodes that are based on hashes of content within said respective lower-level nodes; and

compute a first recursive intrinsic reference based on an HDAG node of the first HDAG, and compute a second recursive intrinsic reference based on an HDAG node of the second HDAG, wherein computing the overlap and discrepancies is based on comparing the first and second recursive intrinsic references, wherein each of the first and second recursive intrinsic references is an intrinsic reference to an item containing another intrinsic reference.

31. The system of claim 30,

wherein the processor is configured to further generate a mapping between nodes of the first HDAG and the second HDAG.

32. A computer system having a processor and a computer program cooperating with the processor to perform:

identifying a first set of organized items as a compare-from location;

identifying a second set of organized items as a compare-to location;

determining a recursive intrinsic reference representing the first set of organized items;

determining a second recursive intrinsic reference representing the second set of organized items, wherein each of the first and second recursive intrinsic references is an intrinsic reference to an item containing another intrinsic reference, wherein each of the first and second recursive intrinsic references is a reference to a node in a corresponding hash directed-acyclic graph (HDAG), and wherein the HDAG is an acyclic graph in which higher-level nodes include references to lower-level nodes that are based on hashes of content within said respective lower-level nodes; and

determining a discrepancy between the first set of organized items and the second set of organized items using the recursive intrinsic reference.