Back to results
US 8,788,499 B2Granted
System and method for finding top N pairs in a map-reduce setup
AssigneeYahoo! Inc.
InventorShaji Illias Chennan Kunnummal
Life of this patent
Estimating the term…
Abstract
According to an example embodiment, a special purpose computing apparatus includes, but is not limited to, one or more processors programmed with instructions to, based at least in part, on one or more signals representative of a plurality of splits defined by a map process that implements a signature function, compute a density value for at least one of the plurality of splits, where the density value is representative of an expected contribution of the at least one split to a top N key/value pairs of a data set, the data set comprising the key/value pairs.
Claims16
A method comprising:
- executing instructions by a special purpose computing apparatus, based, at least in part, on one or more signals representative of a plurality of splits defined by a map process to:
- determine corresponding density values of individual ones of the plurality of splits, wherein a density value for a particular one of the plurality of splits is representative of an expected contribution of corresponding one of the plurality of splits to a top N key/value pairs of a data set, the data set comprising the key/value pairs;
- select a first one of the plurality of splits having a largest one of the corresponding density values and run a first reduce process on the first one of the plurality of splits to determine a first set of key/value pairs;
- determine whether the first set of key/value pairs comprises the top N key/value pairs for the data set and, in response to a determination that the first set of key/value pairs do not contain the top N key/value pairs for the data set, run a second reduce process on the at least a second one of the plurality of splits to determine at least a second set of key/value pairs;
- wherein the determination of whether the first set of key/value pairs does not contain the top N key/value pairs for the data set is based, at least in part, on a determination of whether the first set of key/value pairs contains fewer than N keys having corresponding values higher than at least a maximum value for the at least a second one of the individual ones of the plurality of splits;
- and
- generate one or more signals representing the top N key/value pairs of the data set from the first set of key/value pairs or the at least a second set of key/value pairs.
4 more elements
An article comprising:
- a non-transitory machine-readable medium comprising instructions stored thereon which, in response to being executed by a special purpose computing apparatus, direct the special purpose computing apparatus, based, at least in part, on one or more signals representative of a plurality of splits defined by a map process to:
- determine corresponding density values of individual ones of the plurality of splits, wherein a density value for a particular one of the plurality of splits is representative of an expected contribution of corresponding one of the plurality of splits to a top N key/value pairs of a data set, the data set comprising the key/value pairs;
- select a first one of the plurality of splits having a largest one of the corresponding density values and run a first reduce process on the first one of the plurality of splits to determine a first set of key/value pairs;
- determine whether the first set of key/value pairs comprises the top N key/value pairs for the data set and, in response to a determination that the first set of key/value pairs do not contain the top N key/value pairs for the data set, run a second reduce process on the at least a second one of the plurality of splits to determine at least a second set of key/value pairs;
- wherein in response to being executed by said special purpose computing apparatus, the instructions further direct the special purpose computing apparatus perform the determination of whether the first set of key/value pairs does not contain the top N key/value pairs for the data set based, at least in part, on a determination of whether the first set of key/value pairs contains fewer than N keys having corresponding values higher than at least a maximum value for the at least a second one of the individual ones of the plurality of splits;
- and
- generate one or more signals representing the top N key/value pairs of the data set from the first set of key/value pairs or the at least a second set of key/value pairs.
4 more elements
A special purpose computing apparatus comprising:
- one or more processors programmed with instructions, based, at least in part, on one or more signals representative of a plurality of splits defined by a map process that implements a signature function to:
- determine corresponding density values of individual ones of the plurality of splits, wherein a density value for a particular one of the plurality of splits is representative of an expected contribution of corresponding one of the plurality of splits to a top N key/value pairs of a data set, the data set comprising the key/value pairs;
- select a first one of the plurality of splits having a largest one of the corresponding density values and run a reduce process on the first one of the plurality of splits to determine a first set of key/value pairs;
- determine whether the first set of key/value pairs comprises the top N key/value pairs for the data set and, in response to a determination that the first set of key/value pairs do not contain the top N key/value pairs for the data set, run a second reduce process on the at least a second one of the plurality of splits to determine at least a second set of key/value pairs;
- wherein the one or more processors further programmed with instructions to perform the determination of whether the first set of key/value pairs does not contain the top N key/value pairs for the data set based, at least in part, on a determination of whether the first set of key/value pairs contains fewer than N keys having corresponding values higher than at least a maximum value for the at least a second one of the individual ones of the plurality of splits;
- and
- generate one or more signals representing the top N key/value pairs of the data set from the first set of key/value pairs or the at least a second set of key/value pairs.
4 more elements
Dependencies are inferred from the claim text.