Patent ID: 8321454

Claim:
A computer-implemented method for performing a sorted map-reduce job on a cluster comprising: (A) defining a cluster of two or more computers by: (1) installing a map-reduce framework onto each of the two or more computers; and (2) formatting the cluster by: (i) identifying the two or more computers in the cluster; (ii) establishing communication between the two or more computers; and (iii) enabling the cluster of two or more computers to function as a unit; (B) placing data into the cluster, wherein: (1) the data is distributed onto the two or more computers in the cluster; and (2) each of the two or more computers in the cluster contains a portion of the data; (C) obtaining a map-reduce function to be executed by the map-reduce framework on the cluster; (D) performing a first map function of the map-reduce function, wherein the first map function comprises: (1) each of the two or more computers sorting the portion of the data stored on that computer; (2) each of the two or more computers creating an abstraction comprising a representation of the sorted portion of data stored on that computer; (3) each of the two or more computers exchanging the abstractions; and (4) each of the two or more computers merging the abstractions to create a complete abstraction representing all of the data in the cluster; (E) performing a second map function of the map-reduce function, wherein the second map function comprises: (1) conducting a search of the complete abstraction to determine a redistribution of the data across the two or more computers; and (2) conducting a data exchange wherein each of the two or more computers obtains data based on the redistribution and complete abstraction; and (F) performing a reduce function of the map-reduce function comprising each of the two or more computers performing, in parallel, the reduce function on the data obtained based on the redistribution to produce a result.