METHODS AND SYSTEMS FOR DATA MANAGEMENT USING MULTIPLE SELECTION CRITERIA

• US 20080133446A1
• Filed: 12/01/2006
• Published: 06/05/2008
• Est. Priority Date: 12/01/2006
• Status: Active Grant

• Current Assignee: NEC Corporation
• Original Assignee: NEC Laboratories America Inc (NEC Corporation)
• Inventors: Dubnicki, Cezary, Ungureanu, Cristian, Lichota, Krzysztof, Kruus, Erik
• Granted Patent: US 7,844,581 B2
• Time in Patent Office: Days
• US Class Current: 707/1
• CPC Class Codes: G06F 16/1752 based on file chunks

Abstract

Systems and methods for data management and data processing are provided. Embodiments may include systems and methods relating to fast data selection with reasonably high quality results, and may include a faster data selection function and a slower data selection function. Various embodiments may include systems and methods relating to data hashing and/or data redundancy identification and elimination for a data set or a string of data. Embodiments may include a first selection function is used to pre-select boundary points or data blocks/windows from a data set or data stream and a second selection function is used to refine the boundary points or data blocks/windows. The second selection function may be better at determining the best places for boundary points or data blocks/windows in the data set or data stream. In various embodiments, data may be processed by a first faster hash function and slower more discriminating second hash function.

Claims

1. A method of data management, comprising the steps of:

pre-selecting a portion of a plurality of windows of data in a data stream using a first selecting function; and

selecting a subset of the portion of the plurality of windows pre-selected using a second selecting function.

2. The method of claim 1, wherein the first selecting function is faster at selecting a data block boundary than is the second selecting function.

3. The method of claim 2, wherein the first selecting function is faster at window selection than is the second selecting function.

4. The method of claim 1, wherein the first selecting function includes a boxcar sum function, an MLCG function, or a rolN-xor function.

5. The method of claim 4, wherein the first selecting function is the boxcar sum function and the boxcar sum function is coupled with a selection criterion on the value of the boxcar sum.

6. The method of claim 1, wherein the second selecting function includes a Rabin fingerprint, a SHA-1 function, or a CRC32c function.

7. The method of claim 1, wherein the first selecting function includes a rolling, sliding or moving window function.

8. The method of claim 1, wherein the windows are utilized for defining data groups for hashing and speed of determining break points in the data stream is increased.

9. The method of claim 1, further comprising the step of:

generating a value for a data chunk size determined by one or more chunk points of the subset, wherein the generated value is indicative of underlying data contained in the data chunk.

10. The method of claim 9, further comprising the step of:

comparing the generated value with one or more previously generated values to determine if the generated value equals the one or more previously generated values.

11. The method of claim 10, further comprising the steps of:

determining that there is data duplication present; and

halting further processing of the data in a data chunk determined to have duplicate data.

12. The method of claim 10, further comprising the step of:

storing the generated value if there is no data duplication.

13. The method of claim 1, further comprising the step of comparing underlying data contained in a new window of data or data chunk selected by the second selection function with previously encountered underlying data from previously defined window(s) of data or data chunk(s).

14. The method of claim 13, further comprising the steps of:

outputting the underlying data contained in the new window of data if it does not equal the previously encountered underlying data; and

not outputting the underlying data contained in the new data chunk if it does equal the previously encountered underlying data.

15. The method of claim 1, further comprising the step of generating a value for a window of data or data chunk indicative of underlying data contained in the window of data or data chunk.

16. The method of claim 15, further comprising the step of comparing the generated value with previously generated or encountered value(s).

17. The method of claim 16, further comprising the steps of:

outputting the generated value if it does not equal the previously generated or encountered value(s); and

not outputting the generated value if it does equal the previously generated or encountered value(s).

18. A method of determining boundary points in a data stream for data management, comprising:

pre-selecting a portion of a plurality of boundary points in a data stream using a first selecting function;

selecting a subset of the portion of the plurality of boundary points pre-selected using a second selecting function; and

generating a value for a chunk of data as determined by the subset of the portion of the plurality of boundary points.

19. The method of claim 18, further comprising the step of comparing the generated value with one or more stored value(s), so as to detect a duplicate or store the generated value.

20. The method of claim 19, wherein generating a value is performed by hashing.

21. The method of claim 20, further comprising the step of eliminating duplicate data found by hashing the data contained in a chunk of data defined by the boundary point(s).

22. A data processing system, comprising:

a first selection function module configured to pre-select a first set of data break points or windows; and

a second selection function module configured to select a subset of the pre-selected data break points or windows, wherein the first selection function module processes the data break points or windows faster than the second selection function module.

23. The data processing system of claim 22, wherein the first selection function module includes a boxcar sum function and the second selection function module includes a Rabin function.

24. The data processing system of claim 23, wherein the data processing system is a hashing system and outputs content-defined data block(s) or chunk point(s).

25. A data processing system, comprising:

means for pre-selecting a first set of data break points or windows; and

means for selecting and outputting a subset of the pre-selected data break points or windows, wherein the means for pre-selecting processes the data break points or windows faster than the means for selecting.

26. The data processing system of claim 25, further comprising means for generating a value for each of the data break point(s) or window(s) of the subset.

27. The data processing system of claim 26, wherein the means for pre-selecting a first set of data break points or windows performs a rolling boxcar sum function, the means for selecting and outputting a subset of the pre-selected data break points or windows performs a Rabin function, and the means for generating a value performs a SHA-1 function.

28. The data processing system of claim 27, wherein the generated value is a hash value.

29. The data processing system of claim 25, wherein the data processing system is a hashing system and outputs content-defined data block(s) or chunk point(s).