Parallel data redundancy removal

• US 8,332,367 B2
• Filed: 10/20/2010
• Issued: 12/11/2012
• Est. Priority Date: 10/20/2010
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Kothari, Ravi, Narang, Ankur, Bhattacherjee, Souvik
• Primary Examiner(s): LEROUX, ETIENNE PIERRE
• Application Number:
  US12/908,075
• Publication Number:
  US 20120102003A1
• Time in Patent Office: 783 Days
• Field of Search: 707/2, 707/713, 707/692, 370/392
• US Class Current: 707/692
• CPC Class Codes: G06F 16/24532 of parallel queries
• CPC Class Codes: G06F 16/24556 Aggregation; Duplicate elimination

Abstract

A method, system, and computer usable program product for parallel data redundancy removal are provided in the illustrative embodiments. A plurality of values is computed for a record in a plurality of records stored in a storage device. The plurality of values for the record is distributed to corresponding queues in a plurality of queues, wherein each of the plurality of queues is associated with a corresponding section of a Bloom filter. A determination is made whether each value distributed to the corresponding queues for the record is indicated by a corresponding value in the corresponding section of the Bloom filter. The record is identified as a redundant record in response to a determination that each value distributed to the corresponding queues for the record is indicated by a corresponding value in the corresponding section of the Bloom filter.

Claims

1. A computer implemented method for parallel data redundancy removal, the computer implemented method comprising:

computing a plurality of values for a record in a plurality of records stored in a storage device;

distributing the plurality of values for the record to corresponding queues in a plurality of queues, wherein each of the plurality of queues is associated with a corresponding section of a Bloom filter;

determining whether each value distributed to the corresponding queues for the record is indicated by a corresponding value in the corresponding section of the Bloom filter; and

identifying the record as a redundant record in response to a determination that each value distributed to the corresponding queues for the record is indicated by a corresponding value in the corresponding section of the Bloom filter.

2. The computer implemented method of claim 1, wherein the computing the plurality of values is performed in parallel by threads for multiple records in the plurality of records, and the distributing the plurality of values is performed in parallel by the threads for the multiple records to corresponding queues in the plurality of queues.

3. The computer implemented method of claim 1, further comprising:

determining whether the redundant record duplicates another record in a repository associated with the Bloom filter; and

removing the redundant record from the plurality of records in response to a determination that the redundant record duplicates another record in the repository.

4. The computer implemented method of claim 1, further comprising:

identifying the record as a unique record in response to a determination that each value distributed to the corresponding queues for the record is not indicated by the corresponding value in the corresponding section of the Bloom filter; and

storing the unique record in a repository associated with the Bloom filter.

5. The computer implemented method of claim 4, wherein storing the unique record in the repository comprises setting an indicator in the corresponding value in the corresponding section of the Bloom filter for each value distributed to the corresponding queues for the unique record.

6. The computer implemented method of claim 1, further comprising:

identifying any records in a preliminary plurality of records that are redundant relative to other records in the preliminary plurality of records;

removing any identified redundant records of the preliminary plurality of records from the preliminary plurality of records to create the plurality of records.

7. The computer implemented method of claim 6, wherein identifying any records in the preliminary plurality of records that are redundant relative to other records in the preliminary plurality of records comprises:

assigning a unique identifier to a record in the preliminary plurality of records;

computing a hash value for the record in the preliminary plurality of records based on the corresponding unique identifier;

storing the hash value to a corresponding hash table in a plurality of hash tables; and

merging the plurality of hash tables to identify at least one record of multiple records that correspond to values that are identical for the at least one record in different hash tables as redundant relative to other records in the preliminary plurality of records.

8. The computer implemented method of claim 6, further comprising:

computing a value for a record in an initial plurality of records based on a plurality of fields associated with each record in the initial plurality of records;

distributing the record in the initial plurality of records to a corresponding buffer in a plurality of buffers based on the value for the record in the initial plurality of records, wherein each of the plurality of buffers is associated with a corresponding Bloom filter;

assigning records of a buffer in the plurality of buffers as the preliminary plurality of records;

pre-fetching a second Bloom filter corresponding to the buffer to cache; and

assigning the second Bloom filter corresponding to the buffer as the Bloom filter.

9. A computer usable program product comprising a computer usable storage medium including computer usable code for parallel data redundancy removal, the computer usable code comprising:

computer usable code for computing a plurality of values for a record in a plurality of records stored in a storage device;

computer usable code for distributing the plurality of values for the record to corresponding queues in a plurality of queues, wherein each of the plurality of queues is associated with a corresponding section of a Bloom filter;

computer usable code for determining whether each value distributed to the corresponding queues for the record is indicated by a corresponding value in the corresponding section of the Bloom filter; and

computer usable code for identifying the record as a redundant record in response to a determination that each value distributed to the corresponding queues for the record is indicated by the corresponding value in the corresponding section of the Bloom filter.

10. The computer usable program product of claim 9, wherein the computing the plurality of values is performed in parallel by threads for multiple records in the plurality of records by threads, and the distributing the plurality of values is performed in parallel by the threads for the multiple records to corresponding queues in the plurality of queues by the threads.

11. The computer usable program product of claim 9, further comprising:

computer usable code for determining whether the redundant record duplicates one of the records in a repository associated with the Bloom filter; and

computer usable code for removing the redundant record from the plurality of records in response to a determination that the redundant record duplicates another record in the repository.

12. The computer usable program product of claim 9, further comprising:

computer usable code for identifying the record as a unique record in response to a determination that each value distributed to the corresponding queues for the record is not indicated by the corresponding value in the corresponding section of the Bloom filter; and

computer usable code for storing the unique record in a repository associated with the Bloom filter.

13. The computer usable program product of claim 12, wherein computer usable code for storing the unique record in the repository comprises computer usable code for setting an indicator in the corresponding value in the corresponding section of the Bloom filter for each value distributed to the corresponding queues for the unique record.

14. The computer usable program product of claim 9, further comprising:

computer usable code for identifying any records in a preliminary plurality of records that are redundant relative to other records in the preliminary plurality of records;

computer usable code for removing any identified redundant records in the preliminary plurality of records from the preliminary plurality of records to create the plurality of records.

15. The computer usable program product of claim 14, wherein computer usable code for identifying any records in the preliminary plurality of records that are redundant relative to other records of the preliminary plurality of records comprises:

computer usable code for assigning a unique identifier to a record in the preliminary plurality of records;

computer usable code for computing a hash value for the record in the preliminary plurality of records based on the corresponding unique identifier;

computer usable code for storing the hash value to a corresponding hash table in a plurality of hash tables; and

computer usable code for merging the plurality of hash tables to identify at least one record of multiple records that correspond to values that are identical for the at least one record in different hash tables as redundant relative to other records in the preliminary plurality of records.

16. The computer usable program product of claim 14, further comprising:

computer usable code for computing a value for a record in an initial plurality of records based on a plurality of fields associated with the record in the initial plurality of records;

computer usable code for distributing the record in the initial plurality of records to a corresponding buffer in a plurality of buffers based on the value for the record in the initial plurality of records, wherein each of the plurality of buffers is associated with a corresponding Bloom filter;

computer usable code for assigning records of a buffer in the plurality of buffers as the preliminary plurality of records;

computer usable code for pre-fetching a second Bloom filter corresponding to the buffer to cache; and

computer usable code for assigning the second Bloom filter corresponding to the buffer as the Bloom filter.

17. The computer usable program product of claim 9, wherein the computer usable code is stored in a computer readable storage medium in a data processing system, and wherein the computer usable code is transferred over a network from a remote data processing system.

18. The computer usable program product of claim 9, wherein the computer usable code is stored in a computer readable storage medium in a server data processing system, and wherein the computer usable code is downloaded over a network to a remote data processing system for use in a computer readable storage medium associated with the remote data processing system.

19. A data processing system for parallel data redundancy removal, the data processing system comprising:

a storage device including a storage medium, wherein the storage device stores computer usable program code; and

a processor, wherein the processor executes the computer usable program code, and wherein the computer usable program code comprises;

computer usable code for computing a plurality of values for a record in a plurality of records;

computer usable code for distributing the plurality of values for the record to corresponding queues in a plurality of queues, wherein each of the plurality of queues is associated with a corresponding section of a Bloom filter;

computer usable code for determining whether each value distributed to the corresponding queues for the record is indicated by a corresponding value in the corresponding section of the Bloom filter; and

computer usable code for identifying the record as a redundant record in response to a determination that each value distributed to the corresponding queues for the record is indicated by the corresponding value in the corresponding section of the Bloom filter.

20. The data processing system of claim 19, wherein the computing the plurality of values is performed in parallel by threads for multiple records in the plurality of records by threads, and the distributing the plurality of values is performed in parallel by the threads for the multiple records to corresponding queues in the plurality of queues by the threads.