# US 2019/0377774 A1 · Two-stage distributed estimation system

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

- Number: US 2019/0377774 A1
- Document ID: US20190377774A1
- Status: Published application
- Kind: A1
- Application number: 16/433,192
- Filed: 2019-06-06
- Published: 2019-12-12
- Earliest claimed: 2018-06-06
- Assignees: SAS Institute Inc.
- Applicants: SAS Institute Inc.
- Inventors: Mahesh V. Joshi
- Web page: https://patentgrep.com/patent/US20190377774A1

## CPC

- G06F 17/18: for evaluating statistical data {, e.g. average values, frequency distributions, probability functions, regression analysis (forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04)}
- G06F 9/542: {Event management; Broadcasting; Multicasting; Notifications}
- G06F 11/3452: {Performance evaluation by statistical analysis}
- G06N 7/01: Probabilistic graphical models, e.g. probabilistic networks
- G06F 11/3447: {Performance evaluation by modeling}
- G06F 16/2425: {Iterative querying; Query formulation based on the results of a preceding query}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS

## Abstract

A computing device provides distributed estimation of an empirical distribution function. A boundary cumulative distribution function (CDF) value is defined at a start of each region of a plurality of regions. An accuracy value is defined for each region. (a) First equal proportion bins are computed for a first sample of a first marginal variable using the defined boundary CDF value for each region. (b) Second equal proportion bins are computed for the first sample of the first marginal variable within each region based on the defined accuracy value for each region. (c) The computed second equal proportion bins are added as an empirical distribution function (EDF) for the first marginal variable. (d) (a) to (c) are repeated for each remaining sample of the first marginal variable. (e) (a) to (d) are repeated with each remaining marginal variable of a plurality of marginal variables as the first marginal variable.

## Claims

### Claim 1

A non-transitory computer-readable medium having stored thereon computer-readable instructions that when executed by a computing device cause the computing device to:
define a boundary cumulative distribution function (CDF) value at a start of each region of a plurality of regions;
define an accuracy value for each region of the plurality of regions;
(a) compute first equal proportion bins for a first sample of a first marginal variable using the defined boundary CDF value for each region;
(b) compute second equal proportion bins for the first sample of the first marginal variable within each region based on the defined accuracy value for each region;
(c) add the computed second equal proportion bins to an empirical distribution function (EDF) for the first marginal variable;
(d) repeat (a) to (c) for each remaining sample of the first marginal variable;
(e) repeat (a) to (d) with each remaining marginal variable of a plurality of marginal variables as the first marginal variable; and
(f) output the EDF computed for each marginal variable of the plurality of marginal variables.

### Claim 2 (depends on 1)

The non-transitory computer-readable medium of claim 1, wherein the defined accuracy value for each region and a width of each region define a number of bins within each region, wherein the defined accuracy value and the width are defined along a dimension of the EDF.

### Claim 3 (depends on 1)

The non-transitory computer-readable medium of claim 1, wherein the equal proportion bins are computed using a plurality of worker computing devices in parallel.

### Claim 4 (depends on 3)

The non-transitory computer-readable medium of claim 3, wherein the equal proportion bins are further computed using a plurality of threads of each worker computing device of the plurality of worker computing devices in parallel.

### Claim 5 (depends on 4)

The non-transitory computer-readable medium of claim 4, wherein the defined accuracy value for each region and a width of each region define a number of bins within each region, wherein the defined accuracy value and the width are defined along a dimension of the EDF.

### Claim 6 (depends on 5)

The non-transitory computer-readable medium of claim 5, wherein, when a number of worker computing devices is greater than or equal to a number of regions, the number of bins of each region are assigned for computation by a different worker computing device of the number of worker computing devices.

### Claim 7 (depends on 6)

The non-transitory computer-readable medium of claim 6, wherein, when a number of threads is greater than or equal to a number of regions, the number of bins of each region are assigned for computation by a different thread of the number of threads.

### Claim 8 (depends on 1)

The non-transitory computer-readable medium of claim 1, wherein, when a number of threads is greater than or equal to a number of regions, the number of bins of each region are assigned for computation by a different thread of the number of threads.

### Claim 9 (depends on 1)

The non-transitory computer-readable medium of claim 1, wherein (a) comprises:
estimating a number of bins;
computing a bin boundary for each of the estimated number of bins;
computing the bin counts for the estimated number of bins based on the computed bin boundary for each of the estimated number of bins;
when the computed bin counts are not approximately uniform, updating the bin boundaries and computing the bin counts until the computed bin counts are approximately uniform or until a predefined limit on boundary updates are reached;
when the computed bins are approximately uniform, computing a count in each region; and
computing an EDF value at an end of each region based on the computed count in each region.

### Claim 10 (depends on 1)

The non-transitory computer-readable medium of claim 1, wherein (b) comprises:
when a number of threads is greater than or equal to a number of regions,
assigning a number of threads to each region proportional to a width of a respective region;
defining subregions of the respective region; and
assigning a thread of the number of threads to each subregion;
when a number of threads is less than a number of regions, assigning regions to threads in a round robin manner;
computing a number of bins for each assigned region or each assigned subregion by a respective thread, where the number of bins is computed based on an EDF range and the defined accuracy value of the respective assigned region or the respective assigned subregion; and
compute the equal proportion bin boundary values for the computed number of bins for each assigned region or each assigned subregion by the respective thread.

### Claim 11 (depends on 1)

The non-transitory computer-readable medium of claim 1, wherein (a) comprises:
estimating a number of bins;
initializing a bin boundary for each of the estimated number of bins;
broadcasting the initialized bin boundary for each of the estimated number of bins to a plurality of worker computing devices;
receiving, from the plurality of worker computing devices, a bin count for each bin based on the initialized bin boundary for each of the estimated number of bins;
(g) updating each bin boundary;
(h) broadcasting the updated bin boundary for each of the estimated number of bins to the plurality of worker computing devices;
(i) receiving, from the plurality of worker computing devices, an updated bin count for each bin based on the update bin boundary for each of the estimated number of bins; and
repeating (g) to (i) until the bin boundary computation converges.

### Claim 12 (depends on 11)

The non-transitory computer-readable medium of claim 11, wherein (g) comprises:
splitting a kth bin into two bins when the bin count for the kth bin is greater than a predefined target count c, where c=a*M, where a is the defined accuracy value for a region of the plurality of regions that includes the kth bin, and M is a number of points in the first sample of the first marginal variable; and
expanding a width of the kth bin when the bin count for the kth bin is less than the predefined target count c.

### Claim 13 (depends on 12)

The non-transitory computer-readable medium of claim 12, wherein when the kth bin is split, an excess count is added to a next bin of the kth bin.

### Claim 14 (depends on 12)

The non-transitory computer-readable medium of claim 12, wherein when the kth bin is expanded, the kth bin is merged with a next bin of the kth bin such that the bin count for the kth bin is added to the next bin's count.

### Claim 15 (depends on 11)

The non-transitory computer-readable medium of claim 11, wherein the bin boundary computation convergence determination comprises:
computing a count of values in each bin;
when the computed count of values is less than a predefined minimum expected number of observations per bin, loading the entire sample in the device memory, sorting the sample, setting bin boundaries as sorted sample points, and determining that the bin boundary computation has converged;
when the computed count of values is greater than or equal to the predefined minimum expected number of observations per bin, computing a p-value, wherein the p-value is a probability that a value of a random variable that follows a chi-squared distribution with Bc−1 degrees of freedom is greater than a value computed using a predefined uniformity test statistic, wherein Bc is a number of bins that contain a nonzero computed count of values; and
when the computed p-value is greater than a predefined minimum p-value,
computing a first criterion based on a proportion of the computed count of values in each bin;
computing a convergence parameter for each region of the plurality of regions by multiplying a predefined acceptable tolerance value by the defined accuracy value for each region of the plurality of regions; and
when the computed first criterion is greater than the computed convergence parameter, determining that the bin boundary computation has converged.

### Claim 16 (depends on 11)

The non-transitory computer-readable medium of claim 11, wherein (a) further comprises:
computing a first amount of work to be done for each bin in each region;
computing a second amount of work to be assigned to each worker computing device of the plurality of worker computing devices;
when a number of workers is less than the number of regions, assigning subregions to workers in proportion to the computed second amount of work, wherein a distribution of a total amount of work assigned to each worker computing device is defined for each bin in each region;
when a number of workers is greater than or equal to the number of regions, assigning regions to workers in proportion to the computed second amount of work; and
computing an EDF value at an end of each region or subregion by the plurality of worker computing devices based on the assignment.

### Claim 17 (depends on 1)

The non-transitory computer-readable medium of claim 1, wherein (b) comprises:
defining a bin to worker mapping;
broadcasting the defined bin to worker mapping to each worker computing device of the plurality of worker computing devices;
requesting creation of sampled buffers to be moved based on the defined bin to worker mapping, wherein the created sample buffers are distributed across the plurality of worker computing devices based on the defined bin to worker mapping in response to the request; and
requesting computation of equal proportion bin boundary values for each assigned bin by a respective worker.

### Claim 18 (depends on 17)

The non-transitory computer-readable medium of claim 17, wherein defining the bin to worker mapping comprises:
when a number of the plurality of worker computing devices is less than a number of the plurality of regions, assigning one or more subregions defined for each region of the plurality of regions to one or more of the plurality of worker computing devices to balance a number of bins processed by each worker computing device of the plurality of worker computing devices; and
when a number of the plurality of worker computing devices is greater than or equal to a number of the plurality of regions, assigning each region of the plurality of regions to one or more of the plurality of worker computing devices to balance a number of bins processed by each worker computing device of the plurality of worker computing devices.

### Claim 19

A computing device comprising:
a processor; and
a non-transitory computer-readable medium operably coupled to the processor, the computer-readable medium having computer-readable instructions stored thereon that, when executed by the processor, cause the computing device to
define a boundary cumulative distribution function (CDF) value at a start of each region of a plurality of regions;
define an accuracy value for each region of the plurality of regions;
(a) compute first equal proportion bins for a first sample of a first marginal variable using the defined boundary CDF value for each region;
(b) compute second equal proportion bins for the first sample of the first marginal variable within each region based on the defined accuracy value for each region;
(c) add the computed second equal proportion bins to an empirical distribution function (EDF) for the first marginal variable;
(d) repeat (a) to (c) for each remaining sample of the first marginal variable;
(e) repeat (a) to (d) with each remaining marginal variable of a plurality of marginal variables as the first marginal variable; and
(f) output the EDF computed for each marginal variable of the plurality of marginal variables.

### Claim 20

A method of distributed estimation of an empirical distribution function, the method comprising:
defining, by a computing device, a boundary cumulative distribution function (CDF) value at a start of each region of a plurality of regions;
defining, by the computing device, an accuracy value for each region of the plurality of regions;
(a) computing, by the computing device, first equal proportion bins for a first sample of a first marginal variable using the defined boundary CDF value for each region;
(b) computing, by the computing device, second equal proportion bins for the first sample of the first marginal variable within each region based on the defined accuracy value for each region;
(c) adding, by the computing device, the computed second equal proportion bins to an empirical distribution function (EDF) for the first marginal variable;
(d) repeating, by the computing device, (a) to (c) for each remaining sample of the first marginal variable;
(e) repeating, by the computing device, (a) to (d) with each remaining marginal variable of a plurality of marginal variables as the first marginal variable; and
(f) outputting, by the computing device, the EDF computed for each marginal variable of the plurality of marginal variables.

### Claim 21 (depends on 20)

The method of claim 20, wherein the defined accuracy value for each region and a width of each region define a number of bins within each region, wherein the defined accuracy value and the width are defined along a dimension of the EDF.

### Claim 22 (depends on 20)

The method of claim 20, wherein the equal proportion bins are computed using a plurality of worker computing devices in parallel.

### Claim 23 (depends on 23)

The method of claim 23, wherein the equal proportion bins are further computed using a plurality of threads of each worker computing device of the plurality of worker computing devices in parallel.

### Claim 24 (depends on 20)

The method of claim 20, wherein (a) comprises:
estimating a number of bins;
computing a bin boundary for each of the estimated number of bins;
computing the bin counts for the estimated number of bins based on the computed bin boundary for each of the estimated number of bins;
when the computed bin counts are not approximately uniform, updating the bin boundaries and computing the bin counts until the computed bin counts are approximately uniform or until a predefined limit on boundary updates are reached;
when the computed bins are approximately uniform, computing a count in each region; and
computing an EDF value at an end of each region based on the computed count in each region.

### Claim 25 (depends on 20)

The method of claim 20, wherein (b) comprises:
when a number of threads is greater than or equal to a number of regions,
assigning a number of threads to each region proportional to a width of a respective region;
defining subregions of the respective region; and
assigning a thread of the number of threads to each subregion;
when a number of threads is less than a number of regions, assigning regions to threads in a round robin manner;
computing a number of bins for each assigned region or each assigned subregion by a respective thread, where the number of bins is computed based on an EDF range and the defined accuracy value of the respective assigned region or the respective assigned subregion; and
compute the equal proportion bin boundary values for the computed number of bins for each assigned region or each assigned subregion by the respective thread.

### Claim 26 (depends on 20)

The method of claim 20, wherein (a) comprises:
estimating a number of bins;
initializing a bin boundary for each of the estimated number of bins;
broadcasting the initialized bin boundary for each of the estimated number of bins to a plurality of worker computing devices;
receiving, from the plurality of worker computing devices, a bin count for each bin based on the initialized bin boundary for each of the estimated number of bins;
(g) updating each bin boundary;
(h) broadcasting the updated bin boundary for each of the estimated number of bins to the plurality of worker computing devices;
(i) receiving, from the plurality of worker computing devices, an updated bin count for each bin based on the update bin boundary for each of the estimated number of bins; and
repeating (g) to (i) until the bin boundary computation converges.

### Claim 27 (depends on 26)

The method of claim 26, wherein (g) comprises:
splitting a kth bin into two bins when the bin count for the kth bin is greater than a predefined target count c, where c=a*M, where a is the defined accuracy value for a region of the plurality of regions that includes the kth bin, and M is a number of points in the first sample of the first marginal variable; and
expanding a width of the kth bin when the bin count for the kth bin is less than the predefined target count c.

### Claim 28 (depends on 26)

The method of claim 26, wherein the bin boundary computation convergence determination comprises:
computing a count of values in each bin;
when the computed count of values is greater than or equal to the predefined minimum expected number of observations per bin, computing a p-value, wherein the p-value is a probability that a value of a random variable that follows a chi-squared distribution with Bc−1 degrees of freedom is greater than a value computed using a predefined uniformity test statistic, wherein Bc is a number of bins that contain a nonzero computed count of values; and
when the computed p-value is greater than a predefined minimum p-value or when the computed count of values is less than the predefined minimum expected number of observations per bin,
computing a first criterion;
computing a convergence parameter for each region of the plurality of regions by multiplying a predefined acceptable tolerance value by the defined accuracy value for each region of the plurality of regions; and
when the computed first criterion is greater than the computed convergence parameter, determining that the bin boundary computation has converged.

### Claim 29 (depends on 26)

The method of claim 26, wherein (a) further comprises:
computing a first amount of work to be done for each bin in each region;
computing a second amount of work to be assigned to each worker computing device of the plurality of worker computing devices;
when a number of workers is less than the number of regions, assigning subregions to workers in proportion to the computed second amount of work, wherein a distribution of a total amount of work assigned to each worker computing device is defined for each bin in each region;
when a number of workers is greater than or equal to the number of regions, assigning regions to workers in proportion to the computed second amount of work; and
computing an EDF value at an end of each region or subregion by the plurality of worker computing devices based on the assignment.

### Claim 30 (depends on 20)

The method of claim 20, wherein (b) comprises:
defining a bin to worker mapping;
broadcasting the defined bin to worker mapping to each worker computing device of the plurality of worker computing devices;
requesting creation of sampled buffers to be moved based on the defined bin to worker mapping, wherein the created sample buffers are distributed across the plurality of worker computing devices based on the defined bin to worker mapping in response to the request; and
requesting computation of equal proportion bin boundary values for each assigned bin by a respective worker.