STRATIFIED SAMPLING USING ADAPTIVE PARALLEL DATA PROCESSING

• US 20150186493A1
• Filed: 12/27/2013
• Published: 07/02/2015
• Est. Priority Date: 12/27/2013
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Balmin, Andrey, Ercegovac, Vuk, Haas, Peter J., Sismanis, John, Peng, Liping
• Granted Patent: US 9,697,274 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2237 Vectors, bitmaps or matrices
• CPC Class Codes: G06F 16/24554 Unary operations; Data partitioning operations
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/2462 Approximate or statistical queries
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation

Abstract

Stratified sampling of a plurality of records is performed. A plurality of records are partitioned into a plurality of splits, wherein each split includes at least a portion of the plurality of records. The split of the plurality of splits is provided to a mapper. The mapper assigns at least a portion the records of the at least one split to a group based on a strata of the assigned records, and filters the records of the group based on a comparison of the weights of the records to a local threshold of the mapper. The mapper updates the local threshold of the mapper by communicating with a coordinator. The mapper shuffles the group to a reducer, where the reducer filters the records of the group based on the weights of the records. The reducer provides a stratified sampling of the plurality of records based on the group.

Claims

1. A method for stratified sampling of a plurality of records, the method comprising:

partitioning a plurality of records into a plurality of splits, wherein each split includes at least a portion of the plurality of records;

providing at least one split of the plurality of splits to a mapper;

assigning at least a portion the records of the at least one split to a group, wherein each assignment to the group is based on a strata of the assigned record;

filtering the records of the group, wherein each filtering is based on a comparison of a weight of a record to a local threshold of the mapper;

shuffling the group to a reducer; and

providing a stratified sampling of the plurality of records based on the group.

2. The method of claim 1, further comprising assigning a weight to each record of the plurality of records, wherein each assigned weight is a uniform random weight.

3. The method of claim 1, further comprising filtering the records of the group in the reducer, wherein each filtering is based on the weight of a record.

4. The method of claim 1, further comprising updating the local threshold of the mapper by receiving a group threshold from a coordinator.

5. The method of claim 1, further comprising updating the group threshold of a coordinator.

6. The method of claim 5, wherein the updating the group threshold of the coordinator includes transmitting the local threshold to the coordinator.

7. The method of claim 1, further comprising receiving a plurality of local thresholds including the local threshold of the mapper from a respective plurality of mappers including the mapper.

8. A computer program product for stratified sampling of a plurality of records, the computer program product comprising a computer readable storage medium having program code embodied therewith, the program code executable by a processor to:

partition a plurality of records into a plurality of splits, wherein each split includes at least a portion of the plurality of records;

provide at least one split of the plurality of splits to a mapper;

assign at least a portion the records of the at least one split to a group, wherein each assignment to the group is based on a strata of the assigned record;

filter the records of the group, wherein each filtering is based on a comparison of a weight of a record to a local threshold of the mapper;

shuffle the group to a reducer; and

provide a stratified sampling of the plurality of records based on the group.

9. The computer program product of claim 8, the program code further executable to assign a weight to each record of the plurality of records, wherein each assigned weight is a uniform random weight.

10. The computer program product of claim 8, the program code further executable to filter the records of the group in the reducer, wherein each filtering is based on the weight of a record.

11. The computer program product of claim 8, the program code further executable to update the local threshold of the mapper by receiving a group threshold from a coordinator.

12. The computer program product of claim 8, the program code further executable to update the group threshold of a coordinator.

13. The computer program product of claim 12, wherein the updating the group threshold of the coordinator includes transmitting the local threshold to the coordinator.

14. The computer program product of claim 8, the program code further executable to receive a plurality of local thresholds including the local threshold of the mapper from a respective plurality of mappers including the mapper.

15. A system for stratified sampling of a plurality of records, the system comprising:

a memory having computer readable computer instructions; and

a processor for executing the computer readable computer instructions, the instructions executable by the processor to;

partition a plurality of records into a plurality of splits, wherein each split includes at least a portion of the plurality of records;

provide at least one split of the plurality of splits to a mapper;

assign at least a portion the records of the at least one split to a group, wherein each assignment to the group is based on a strata of the assigned record;

filter the records of the group, wherein each filtering is based on a comparison of a weight of a record to a local threshold of the mapper;

shuffle the group to a reducer; and

provide a stratified sampling of the plurality of records based on the group.

16. The system of claim 15, the instructions further executable to assign a weight to each record of the plurality of records, wherein each assigned weight is a uniform random weight.

17. The system of claim 15, the instructions further executable to filter the records of the group in the reducer, wherein each filtering is based on the weight of a record.

18. The system of claim 15, the instructions further executable to update the local threshold of the mapper by receiving a group threshold from a coordinator.

19. The system of claim 15, the instructions further executable to update the group threshold of a coordinator.

20. The system of claim 19, wherein the updating the group threshold of the coordinator includes transmitting the local threshold to the coordinator.