System and method for navigating data

• US 20110184967A1
• Filed: 09/08/2010
• Published: 07/28/2011
• Est. Priority Date: 01/25/2010
• Status: Active Grant

• Current Assignee: Hitachi Vantara, LLC (Hitachi, Ltd.)
• Original Assignee: Sepaton Incorporated (Hitachi, Ltd.)
• Inventors: Kennedy, Jon Christopher, King, Stefan Merrill, McMaster, Carey Jay, Trimble, Ronald Ray, Reiter, Timmie G., Biernacki, David Michael
• Granted Patent: US 8,447,741 B2
• Time in Patent Office: Days
• US Class Current: 707/758
• CPC Class Codes: G06F 11/1453 using de-duplication of the data

Abstract

Described are computer-based methods and apparatuses, including computer program products, for removing redundant data from a storage system. In one example, a data delineation process delineates data targeted for de-duplication into regions using a plurality of markers. The de-duplication system determines which of these regions should be subject to further de-duplication processing by comparing metadata representing the regions to metadata representing regions of a reference data set. The de-duplication system identifies an area of data that incorporates the regions that should be subject to further de-duplication processing and de-duplicates this area with reference to a corresponding area within the reference data set.

Claims

1. A computer implemented method of identifying reference data likely to match target data, the method comprising:

reading a reference set of summaries of data included in a reference 5 data set, each member of the reference set of summaries including a plurality of summaries that indicate particular patterns of the reference data within the reference data set;

comparing the reference set of summaries to a target set of summaries associated with at least one target area of a plurality of target areas, each member of the target set of summaries including a plurality of summaries that indicate particular patterns of the target data included in the at least one target area, the plurality of target areas being included in a target data set; and

associating the at least one target area with the reference data set when a threshold number of members of the target set of summaries associated with the at least one target area match members of the reference set of summaries.

2. The method according to claim 1, wherein reading the reference set of summaries includes reading a set of hash values.

3. The method according to claim 1, wherein the reference data set includes a plurality of reference areas, each reference area of the plurality of reference areas being associated with at least one member of the reference set of summaries, the method further comprising selecting at least one reference area of the plurality of references areas based on a number of members of the target set of summaries associated with the at least one target area that match members of the reference set of summaries associated with the at least one reference area.

4. The method according to claim 3, wherein selecting the at least one reference area of the plurality of reference areas includes selecting at least one reference area of the plurality of references areas based on a number of members of the target set of summaries associated with the at least one target area that match members of the reference set of summaries associated with at least one neighboring reference area of the plurality of reference areas that neighbors the at least one reference area.

5. The method according to claim 4, further comprising adjusting the at least one reference area to include the at least one neighboring reference area 5 when at least one member of the target set of summaries associated with the at least one target area matches at least one member of the reference set of summaries associated with the at least one neighboring reference area.

6. The method according to claim 5, further comprising adjusting the at least one target area to include at least one neighboring target area when at least one member of the reference set of summaries associated with the at least one reference area matches at least one member of the target set of summaries associated with the at least one neighboring target area.

7. The method according to claim 6, further comprising de-duplicating the at least one target area with reference to the at least one reference area.

8. A system configured to identify reference data likely to match target data, the system comprising:

data storage storing a target data set; and

a processor coupled to the data storage and configured to;

read a reference set of summaries of data included in a reference data set, each member of the reference set of summaries including a plurality of summaries that indicate particular patterns of the reference data within the reference data set;

compare the reference set of summaries to a target set of summaries associated with at least one target area of a plurality of target areas, each member of the target set of summaries including a plurality of summaries that indicate particular patterns of the target data included in the at least one target area, the plurality of target areas being included in the target data set; and

associate the at least one target area with the reference data set when a threshold number of members of the target set of summaries associated with the at least one target area match members of the reference set of summaries.

9. The system according to claim 8, wherein the processor is configured 5 to read the reference set of summaries by reading a set of hash values.

10. The system according to claim 8, wherein the reference data set includes a plurality of reference areas, each reference area of the plurality of reference areas being associated with at least one member of the reference set of summaries, and the processor is further configured to select at least one reference area of the plurality of references areas based on a number of members of the target set of summaries associated with the at least one target area that match members of the reference set of summaries associated with the at least one reference area.

11. The system according to claim 10, wherein the processor is configured to select the at least one reference area of the plurality of reference areas by selecting at least one reference area of the plurality of references areas based on a number of members of the target set of summaries associated with the at least one target area that match members of the reference set of summaries associated with at least one neighboring reference area of the plurality of reference areas that neighbors the at least one reference area.

12. The system according to claim 11, wherein the processor is further configured to adjust the at least one reference area to include the at least one neighboring reference area when at least one member of the target set of summaries associated with the at least one target area matches at least one member of the reference set of summaries associated with the at least one neighboring reference area.

13. The system according to claim 12, wherein the processor is further configured to adjust the at least one target area to include at least one neighboring target area when at least one member of the reference set of summaries associated with the at least one reference area matches at least one member of the target set of summaries associated with the at least one neighboring target area.

14. The system according to claim 13, wherein the processor is further 5 configured to de-duplicate the at least one target area with reference to the at least one reference area.

15. A non-transitory computer readable medium storing computer readable instructions that, when executed by at least one processor, instruct the at least one processor to perform a method of identifying reference data likely to match target data, the method comprising:

reading a reference set of summaries of data included in a reference data set, each member of the reference set of summaries including a plurality of summaries that indicate particular patterns of the reference data within the reference data set;

comparing the reference set of summaries to a target set of summaries associated with at least one target area of a plurality of target areas, each member of the target set of summaries including a plurality of summaries that indicate particular patterns of the target data included in the at least one target area, the plurality of target areas being included in a target data set; and

associating the at least one target area with the reference data set when a threshold number of members of the target set of summaries associated with the at least one target area match members of the reference set of summaries.

16. The computer readable medium according to claim 15, wherein the reference data set includes a plurality of reference areas, each reference area of the plurality of reference areas being associated with at least one member of the reference set of summaries, and the instructions further instruct the processor to perform acts including selecting at least one reference area of the plurality of references areas based on a number of members of the target set of summaries associated with the at least one target area that match members of the reference set of summaries associated with the at least one reference area.

17. The computer readable medium according to claim 16, wherein the instructions for selecting the at least one reference area of the plurality of reference 5 areas instruct the processor to perform acts including selecting at least one reference area of the plurality of references areas based on a number of members of the target set of summaries associated with the at least one target area that match members of the reference set of summaries associated with at least one neighboring reference area of the plurality of reference areas that neighbors the at least one reference area.

18. The computer readable medium according to claim 17, wherein the instructions further instruct the processor to perform acts including comprising adjusting the at least one reference area to include the at least one neighboring reference area when at least one member of the target set of summaries associated with the at least one target area matches at least one member of the reference set of summaries associated with the at least one neighboring reference area.

19. The computer readable medium according to claim 18, wherein the instructions further instruct the processor to perform acts including adjusting the at least one target area to include at least one neighboring target area when at least one member of the reference set of summaries associated with the at least one reference area matches at least one member of the target set of summaries associated with the at least one neighboring target area.

20. The computer readable medium according to claim 19, wherein the instructions further instruct the processor to perform acts including de-duplicating the at least one target area with reference to the at least one reference area.