×

Method and System for Optimizing Reduce-Side Join Operation in a Map-Reduce Framework

  • US 20150149437A1
  • Filed: 11/25/2014
  • Published: 05/28/2015
  • Est. Priority Date: 11/26/2013
  • Status: Active Grant
First Claim
Patent Images

1. A computer system for optimizing reduce-side join operation in a Map-reduce framework between a first data structure and a second data structure, the first data structure being sorted and divided into one or more regions, the system comprising:

  • a. one or more processors; and

    b. a non-transitory memory containing instructions that, when executed by said one or more processors, causes said one or more processors to perform a set of steps comprising;

    i. executing module for executing one or more map operations by one or more processors, wherein executing one or more map operation by one or more processors comprises;

    1. fetching input data of the second data structure;

    2. partitioning the data of the second data structure according to key-value pair;

    3. projecting the key-value pairs of the second data structure to a partitioner;

    4. maintaining one or more region key counters;

    wherein the region key counter being used for registering key count value of one or more regions of the second data structure; and

    5. emitting the key count value of one or more regions and corresponding data, wherein the key count values are emitted prior to the corresponding data;

    ii. grouping module for grouping mapped data corresponding to a single region of the second data structure;

    iii. accumulating module for providing the grouped data to a reducer; and

    iv. fetching module for retrieving descriptive metadata of one or more regions of the first data structure;

    v. selecting module for selecting one of a look-up approach and a scan approach to perform join operation by one or more reducers based on associated key count value and predefined criteria by the reducer, for performing the join operation.

View all claims
  • 2 Assignments
Timeline View
Assignment View
    ×
    ×