Estimating most frequent values for a data set
AssigneeInternational Business Machines Corporation
InventorsJames L. Finnerty, Venkatesh S. Gopal, Venkannababu Tammisetti, Paul-John A. To
Life of this patent
Estimating the term…
Abstract
Provided are techniques for estimating most frequent values. A sample of values made up of rows is received from each of multiple nodes. The sample of values from each of the multiple nodes are aggregated to generate a sample table storing the rows. A descending list of most frequent values and associated frequencies is obtained using the sample table. Most frequent values are pruned from the descending list whose associated frequencies are below a minimum absolute frequency. The remaining most frequent values are extrapolated to reflect a data set.
Claims15
A method, comprising:
- receiving, using a processor of a computer, from each of multiple nodes, a sample of values made up of rows;
- aggregating the sample of values from each of the multiple nodes to generate a sample table storing the rows;
- using the sample table to obtain a descending list of most frequent values and associated frequencies;
- pruning most frequent values from the descending list whose associated frequencies are below a minimum absolute frequency, wherein the minimum absolute frequency is determined by:
- computing two series, (x, f(x)) and (x, g(x)), where xi is an absolute frequency of element i in the sample table, f(xi) is a relative frequency in the sample table, and g(xi) is an absolute frequency in the sample table;
- graphing f(x)-g(x) against x on top of f(x)/x to plot two curves;
- and
- identifying a point at which the two curves intersect as the minimum absolute frequency;
- and
- extrapolating remaining most frequent values to reflect a data set.
A computer program product, the computer program product comprising a computer readable storage medium having program code embodied therewith, the program code executable by at least one processor to perform:
- receiving from each of multiple nodes, a sample of values made up of rows;
- aggregating the sample of values from each of the multiple nodes to generate a sample table storing the rows;
- using the sample table to obtain a descending list of most frequent values and associated frequencies;
- pruning most frequent values from the descending list whose associated frequencies are below a minimum absolute frequency, wherein the minimum absolute frequency is determined by:
- computing two series, (x, f(x)) and (x, g(x)), where xi is an absolute frequency of element i in the sample table, f(xi) is a relative frequency in the sample table, and g(xi) is an absolute frequency in the sample table;
- graphing f(x)-g(x) against x on top of f(x)/x to plot two curves;
- and
- identifying a point at which the two curves intersect as the minimum absolute frequency;
- and
- extrapolating remaining most frequent values to reflect a data set.
A computer system, comprising:
- one or more processors, one or more computer-readable memories and one or more computer-readable, tangible storage devices;
- and
- program instructions, stored on at least one of the one or more computer-readable, tangible storage devices for execution by at least one of the one or more processors via at least one of the one or more memories, to perform:
- receiving from each of multiple nodes, a sample of values made up of rows;
- aggregating the sample of values from each of the multiple nodes to generate a sample table storing the rows;
- using the sample table to obtain a descending list of most frequent values and associated frequencies;
- pruning most frequent values from the descending list whose associated frequencies are below a minimum absolute frequency, wherein the minimum absolute frequency is determined by:
- computing two series, (x, f(x)) and (x, g(x)), where xi is an absolute frequency of element i in the sample table, f(xi) is a relative frequency in the sample table, and g(xi) is an absolute frequency in the sample table;
- graphing f(x)-g(x) against x on top of f(x)/x to plot two curves;
- and
- identifying a point at which the two curves intersect as the minimum absolute frequency;
- and
- extrapolating remaining most frequent values to reflect a data set.
Dependencies are inferred from the claim text.