# US 2012/0254193 A1 · Processing Data in a Mapreduce Framework

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2012/0254193 A1
- Document ID: US20120254193A1
- Status: Published application
- Kind: A1
- Application number: 13/078,500
- Filed: 2011-04-01
- Published: 2012-10-04
- Earliest claimed: 2011-04-01
- Assignees: Google Inc.
- Inventors: Biswapesh Chattopadhyay; Liang Lin; Weiran Liu; Marián Dvorský
- Web page: https://patentgrep.com/patent/US20120254193A1

## CPC

- G06F 16/90335: {Query processing}
- G06F 16/245: Query processing
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A computer-implemented method for processing input data in a mapreduce framework includes: receiving, in the mapreduce framework, a data processing request for input data; initiating, based on the data processing request, a map operation on the input data by multiple mappers in the mapreduce framework, each of the mappers using an aggregator to partially aggregate the input data into one or more intermediate key/value pairs; initiating a reduce operation on the intermediate key/value pairs by multiple reducers in the mapreduce framework, wherein, without sorting the intermediate key/value pairs, those of the intermediate key/value pairs with a common key are handled by a same one of the reducers, each of the reducers using the aggregator to aggregate the intermediate key/value pairs into one or more output values; and providing the output values in response to the data processing request.

## Claims

### Claim 1

A computer-implemented method for processing input data in a mapreduce framework, the method comprising:
receiving, in the mapreduce framework, a data processing request for input data;
initiating, based on the data processing request, a map operation on the input data by multiple mappers in the mapreduce framework, each of the mappers using an aggregator to partially aggregate the input data into one or more intermediate key/value pairs;
initiating a reduce operation on the intermediate key/value pairs by multiple reducers in the mapreduce framework, wherein, without sorting the intermediate key/value pairs, those of the intermediate key/value pairs with a common key are handled by a same one of the reducers, each of the reducers using the aggregator to aggregate the intermediate key/value pairs into one or more output values; and
providing the output values in response to the data processing request.

### Claim 2 (depends on 1)

The computer-implemented method of claim 1, wherein the data processing request identifies a number of keys in the input data, the method further comprising performing a size evaluation of the identified number of keys with regard to a size of the input data, wherein the map and reduce operations using the aggregator are selected for initiation based on the size evaluation.

### Claim 3 (depends on 2)

The computer-implemented method of claim 2, wherein the mappers and reducers are implemented using a cluster of machines, and wherein the size evaluation takes into account memory space of one or more of the machines.

### Claim 4 (depends on 2)

The computer-implemented method of claim 2, wherein the size evaluation takes into account whether the identified number of keys is three orders of magnitude smaller than the size of the input data.

### Claim 5 (depends on 1)

The computer-implemented method of claim 1, wherein the aggregator in the map and reduce operations uses a hash table.

### Claim 6 (depends on 1)

The computer-implemented method of claim 1, wherein the aggregator is based on a commutative and associative aggregate function.

### Claim 7

A computer program product tangibly embodied in a computer-readable storage device and comprising instructions that when executed by a processor perform a method for processing input data in a mapreduce framework, the method comprising:
receiving, in the mapreduce framework, a data processing request for input data;
initiating, based on the data processing request, a map operation on the input data by multiple mappers in the mapreduce framework, each of the mappers using an aggregator to partially aggregate the input data into one or more intermediate key/value pairs;
initiating a reduce operation on the intermediate key/value pairs by multiple reducers in the mapreduce framework, wherein, without sorting the intermediate key/value pairs, those of the intermediate key/value pairs with a common key are handled by a same one of the reducers, each of the reducers using the aggregator to aggregate the intermediate key/value pairs into one or more output values; and
providing the output values in response to the data processing request.

### Claim 8 (depends on 7)

The computer program product of claim 7, wherein the data processing request identifies a number of keys in the input data, the method further comprising performing a size evaluation of the identified number of keys with regard to a size of the input data, wherein the map and reduce operations using the aggregator are selected for initiation based on the size evaluation.

### Claim 9 (depends on 8)

The computer program product of claim 8, wherein the mappers and reducers are implemented using a cluster of machines, and wherein the size evaluation takes into account memory space of one or more of the machines.

### Claim 10 (depends on 8)

The computer program product of claim 8, wherein the size evaluation takes into account whether the identified number of keys is three orders of magnitude smaller than the size of the input data.

### Claim 11 (depends on 7)

The computer program product of claim 7, wherein the aggregator in the map and reduce operations uses a hash table.

### Claim 12 (depends on 7)

The computer program product of claim 7, wherein the aggregator is based on a commutative and associative aggregate function.

### Claim 13

A system comprising:
at least one processor; and
at least one computer-readable storage device comprising instructions that when executed cause performance of a method for processing input data in a mapreduce framework, the method comprising:
receiving, in the mapreduce framework, a data processing request for input data;
initiating, based on the data processing request, a map operation on the input data by multiple mappers in the mapreduce framework, each of the mappers using an aggregator to partially aggregate the input data into one or more intermediate key/value pairs;
initiating a reduce operation on the intermediate key/value pairs by multiple reducers in the mapreduce framework, wherein, without sorting the intermediate key/value pairs, those of the intermediate key/value pairs with a common key are handled by a same one of the reducers, each of the reducers using the aggregator to aggregate the intermediate key/value pairs into one or more output values; and
providing the output values in response to the data processing request.

### Claim 14 (depends on 13)

The system of claim 13, wherein the data processing request identifies a number of keys in the input data, the method further comprising performing a size evaluation of the identified number of keys with regard to a size of the input data, wherein the map and reduce operations using the aggregator are selected for initiation based on the size evaluation.

### Claim 15 (depends on 14)

The system of claim 14 wherein the mappers and reducers are implemented using a cluster of machines, and wherein the size evaluation takes into account memory space of one or more of the machines.

### Claim 16 (depends on 14)

The system of claim 14, wherein the size evaluation takes into account whether the identified number of keys is three orders of magnitude smaller than the size of the input data.

### Claim 17 (depends on 13)

The system of claim 13, wherein the aggregator in the map and reduce operations uses a hash table.

### Claim 18 (depends on 13)

The system of claim 13, wherein the aggregator is based on a commutative and associative aggregate function.
