Identifying characteristics in sets of organized items

• US 20060282475A1
• Filed: 06/10/2005
• Published: 12/14/2006
• 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
• Granted Patent: US 7,908,254 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 method to determine characteristics of sets of organized items comprising:

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,

wherein the recursive intrinsic reference is an intrinsic reference to an item containing a second intrinsic reference; and

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

2. The method of claim 1 further comprising:

determining whether the recursive intrinsic reference corresponds to an organized set of items in the compare-to location;

using the recursive intrinsic reference to determine a second recursive intrinsic reference representing an organized subset of the first set of organized items;

determining whether the second recursive intrinsic reference corresponds to an organized set of items in the compare-to location.

3. The method as recited in claim 2 wherein the recursive intrinsic reference is a reference to a node in a hash based directed-acyclic graph (HDAG).

4. The method as recited in claim 3 wherein the recursive intrinsic reference is a result of a hash function applied to a node in the HDAG.

5. The method as recited in claim 3, further comprising generating a mapping from the node in the HDAG to a second node in a second HDAG representing organized items in the compare-to location.

6. The method as recited in claim 1 wherein the items include a data file and where the items are organized as directories.

7. The method as recited claim 1 wherein the discrepancies include identification of an item in the first set that is not also in the second set.

8. The method as recited in claim 1 wherein the discrepancies include identification of an item in the second set that is not also in the first set.

9. The method as recited in claim 1 wherein the discrepancies include a difference in organization of items.

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

11. The method as recited in claim 10 where computing the metric comprises computing the degree to which the organization of the items is different.

12. The method as recited in claim 10, further comprising obtaining an attribute of an item and wherein the computing the metric makes use of the attribute.

13. The method as recited in claim 12 wherein the attribute is the size of the item.

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

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

16. The method as recited in claim 1 wherein a discrepancy of interest comprising the identification of a file in the “

compare-from”

location that partially overlaps a file in the “

compare-to”

location is determined.

17. The method as claim 14 where the visualization results from a computation on the compare-from and compare-to data comprising any of overlap computation, structural overlap computation, and content size computation.

18. The method as recited in claim 17 further comprising providing two hash directed acyclic graph (HDAG) nodes H and H′

.

19. The method as recited in claim 18 further comprising calculating overlap in the instance that H is a descendant of H′

by determining the data size of the collection represented by the HDAG node H.

20. The method as recited in claim 18 further comprising calculating overlap in the instance that H is not a descendant of H′

by summing the overlap H′ and

each of the children of H.

21. The method as recited in claim 18 further comprising the structural overlap by determining the number of descendants of H that are also descendants of H′

to identify shared descendants and dividing the value of the shared descendants by the number of descendants of H.

22. The method as recited in claim 1, further comprising determining a recursive intrinsic reference to an item using a chunking algorithm.

23. The method as recited in claim 1, further comprising determining a recursive reference to a n item using one or more algorithms to process pairs of hash directed acyclic graphs (HDAGs).

24. The method as recited in claim 23 where the discrepancies further include a discrepancy between a first item in the compare-from location and a second item in the compare-to location such that the first item and the second item share a plurality of chunks.

25. The method as recited in claim 23 where the intrinsic references of chunks are represented in the recursive intrinsic reference.

26. The method as recited in claim 1 further comprising identifying the discrepancies between digital picture files on a laptop computer and digital picture files on a personal computer.

27. The method as recited in claim 1 further comprising identifying discrepancies between a back-up of data found on a back-up storage device and data found on a computing environment.

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

29. The method as recited in claim 1 further comprising identifying similar structure data directory between two sets of digital image files.

30. A computer readable 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 recursive intrinsic reference representing the organized items in the compare-from location;

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

31. A method to determine characteristics of sets of organized items comprising:

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 one or more HDAGs for the items from the first location and for the items from the second location;

determining overlap between the items in the compare-from location and the compare-to location using the one or more HDAGs;

determining discrepancies in organization between the first set of organized items and the second set of organized items using the one or more HDAGs;

visualizing results of the overlap and discrepancy computations in a graphical representation.

32. Application instructions on a computer-usable medium where the instructions, when executed, identify characteristics of sets of organized items, comprising:

receiving sets of organized items as input;

generating one or more HDAGs for the organized items;

generating a mapping between HDAG nodes in the data;

computing common characteristics, organization, and discrepancies between the sets of organized items based on the mapping between HDAG nodes; and

generating a graphical representation of the computed overlap and discrepancies.

33. A system for identifying characteristics of sets of organized items, comprising:

a first means for identifying sets of organized items in a computing environment;

a second means operable to determine one or more HDAGs for the sets of organized items;

a third means for computing common characteristics, organization, and discrepancies between the sets of organized items based on the one or more HDAGs; and

a fourth means for generating a graphical representation of the computed overlap and discrepancies.

34. The system of claim 33, further comprising:

a fifth means for generating a mapping between HDAG nodes.

35. A computer system having a processor and a computer program cooperating with the processor to perform a method comprising:

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,

wherein the recursive intrinsic reference is an intrinsic reference to an item containing a second intrinsic reference; and

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