Processing hierarchical data in a map-reduce framework

• US 8,959,519 B2
• Filed: 08/29/2012
• Issued: 02/17/2015
• Est. Priority Date: 05/31/2011
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Agarwal, Manoj K., Gupta, Himanshu, Gupta, Rajeev, Padmanabhan, Sriram K., Roy, Prasan
• Primary Examiner(s): Tang, Kenneth
• Application Number:
  US13/598,280
• Publication Number:
  US 20120324459A1
• Time in Patent Office: 902 Days
• Field of Search: None
• US Class Current: 718/102
• CPC Class Codes: G06F 9/46 Multiprogramming arrangements
• CPC Class Codes: G06F 9/5066 Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs mappping at compile time, see G06F8/451

Abstract

Methods and arrangements for processing hierarchical data in a map-reduce framework. Hierarchical data is accepted, and a map-reduce job is performed on the hierarchical data. This performing of a map-reduce job includes determining a cost of partitioning the data, determining a cost of redefining the job and thereupon selectively performing at least one step taken from the group consisting of: partitioning the data and redefining the job.

Claims

1. A method comprising:

accepting hierarchical data;

performing a map-reduce job on the hierarchical data;

said performing comprising;

determining a cost of partitioning the data;

determining a cost of redefining the job;

thereupon selectively performing at least one step taken from the group consisting of;

partitioning the data and redefining the job.

2. The method according to claim 1, wherein said determining of a cost of partitioning the data comprises determining costs associated with at least two different processes of partitioning the data.

3. The method according to claim 1, wherein said determining of a cost of redefining the job comprises determining a cost of copying data to a partition of data.

4. The method according to claim 1, wherein said accepting comprises accepting hierarchical data without restrictions on a number of levels of the hierarchical data.

5. The method according to claim 1, wherein:

said partitioning of data is performed, wherein the data is partitioned into at least two partitions; and

each of the at least two partitions is of a size less than or equal to a predetermined threshold size.

6. The method according to claim 1, wherein said performing of a map-reduce job comprises performing a multi-stage map-reduce job comprising a plurality of stages, the plurality of stages including an intermediate map-reduce job stage and a final map-reduce job stage.

7. The method according to claim 6, further comprising accepting new hierarchical input data at the intermediate map-reduce job stage.

8. The method according to claim 7, wherein said partitioning of data is performed.

9. The method according to claim 8, wherein said partitioning comprises copying a data portion to a partition of data if the portion is smaller than a size of the new hierarchical input data, wherein the size of the data portion times (N−

1) is less than the size of the new hierarchical input data, with N representing a total number of map-reduce jobs.

10. The method according to claim 8, wherein said redefining of the job is performed.

11. The method according to claim 10, further comprising introducing an element at the intermediate map-reduce stage which triggers said redefining of the job and said partitioning of data.

12. The method according to claim 8, wherein said partitioning of data comprises:

creating a matrix to store a status of each data path up to a current processing point; and

consulting the matrix in partitioning the data.