US 2016/0188705 A1Published application

System and method for precise quantile determination

AssigneeSoftware AG

InventorsDaniel Schreck, Sebastian Millies

Life of this patent

Estimating the term…

Loading patent…

Abstract

Precise quantile determination in a distributed environment is provided where data is distributed among worker nodes, one of which functions as a coordinator node. Each worker node has local data for precise quantile determination. The coordinator node derives a maximum relative error value ε which guarantees an exact result for every quantile can be determined in two passes with optimal memory consumption on this node. The worker nodes perform a distributed computation of quantile summaries of datapoints, that specify lower and upper bounds of quantile ranks for selected datapoints. The coordinator node merges the quantile summaries and determines, for each quantile rank, lower and upper bounds for values between which the quantile must occur. The worker nodes filter out, in a second pass, those datapoints that are not within the bounds and stream the qualifying data to the coordinator node. The coordinator node computes precise quantiles from the qualifying data.

Claims15

Dependent claims

A method for precise quantile determination in a system in which data is distributed among nodes in the system, one of a plurality of worker nodes functions as a coordinator node, each of the worker nodes having local data for the precise quantile determination, the method comprising:

by each processor in parallel at each of the worker nodes, determining a number N of datapoints to be computed from the local data of the worker node;
by one of the processors at one of the nodes, selecting as the coordinator node one of the nodes with a largest number of datapoints;
by a processor at the coordinator node, determining from the number N of datapoints and one or more quantiles to be computed, a maximum relative error value ε that guarantees that an exact result for every quantile is determined in two passes;
by each processor in parallel at each of the worker nodes, computing, in a first pass of the datapoints of the local data of each of the worker nodes, using an approximation algorithm and ε, a quantile summary of the datapoints of the local data that specifies lower and upper bounds of the quantile ranks for selected datapoints of the local data of each of the worker nodes;
by the processor at the coordinator node:
merging the quantile summaries for the datapoints of the local data of each of the worker nodes, into a constructed summary;
determining, based on the constructed summary, for each quantile rank, the lower and upper bounds for values between which the quantile must occur;
by each processor in parallel at each of the worker nodes, filtering out, in a second pass over the datapoints of the local data at each of the worker nodes, the datapoints that are not between the lower and upper bounds, to provide subsets of datapoints of the local data within the lower and upper bounds;
by the processor at the coordinator node:
collecting, from the worker nodes, as collected qualifying data, all of the subsets of datapoints of the local data within the lower and upper bounds;
and
computing, based on the quantile ranks and the collected qualifying data which were collected from the worker nodes, the precise quantiles.

9 more elements

A system for precise quantile determination in which data is distributed among nodes in the system, one of a plurality of worker nodes functions as a coordinator node, each of the worker nodes having local data for the precise quantile determination comprising:

a coordinator node having a memory;
and
a processor cooperatively operable with the memory;
and
a plurality of worker nodes, each worker node having a memory;
and
a processor cooperatively operable with the memory,
the processor of the coordinator node is configured to, based on instructions stored in the memory of the coordinator node, determine from the number N of datapoints reported from the worker nodes and one or more quantiles to be computed, a maximum relative error value ε that guarantees that an exact result for every quantile is determined in two passes;
each processor of each of the worker nodes is configured to operate in parallel with the other worker nodes, and, based on instructions stored in the memory of the worker node, compute, in a first pass of the datapoints of the local data of each of the worker nodes, using an approximation algorithm and ε, a quantile summary of the datapoints of the local data that specifies lower and upper bounds of the quantile ranks for selected datapoints of the local data of each of the worker nodes,
the processor at the coordinator node is further configured to
merge the quantile summaries for the datapoints of the local data of each of the worker nodes, into a constructed summary;
determine, based on the constructed summary, for each quantile rank, the lower and upper bounds for values between which the quantile must occur;
each processor of each of the worker nodes is further configured to filter out, in a second pass over the datapoints of the local data at each of the worker nodes, the datapoints that are not between the lower and upper bounds, to provide subsets of datapoints of the local data within the lower and upper bounds;
the processor at the coordinator node is further configured to
collect, from the worker nodes, as collected qualifying data, all of the subsets of datapoints of the local data within the lower and upper bounds;
and
compute, based on the quantile ranks and the collected qualifying data which were collected from the worker nodes, the precise quantiles.

14 more elements

A non-transitory computer readable medium comprising executable instructions for a method for precise quantile determination in a system in which data is distributed among nodes in the system, one of a plurality of worker nodes functions as a coordinator node, each of the worker nodes having local data for the precise quantile determination, the instructions being executed on a processor to:

determine, by each processor in parallel at each of the worker nodes, a number N of datapoints to be computed from local data of each worker node;
select, by one of the processors at one of the nodes, as the coordinator node, one of the nodes with a largest number of datapoints;
determine, by a processor at the coordinator node, from the number N of datapoints and one or more quantiles to be computed, a maximum relative error value ε that guarantees that an exact result for every quantile is determined in two passes;
compute, by each processor in parallel at each of the worker nodes, in a first pass of the datapoints of the local data of each the worker nodes, using an approximation algorithm and ε, a quantile summary of the datapoints that specifies lower and upper bounds of the quantile ranks for selected datapoints of the local data of each of the worker nodes;
merge, by the processor at the coordinator node, the quantile summaries for the datapoints of the local data of each of the worker nodes, into a constructed summary;
determine, by the processor at the coordinator node, based on the constructed summary, for each quantile rank, the lower and upper bounds for values between which the quantile must occur;
filter out, by each processor in parallel at the worker nodes, in a second pass over the datapoints of the local data at each of the worker nodes, the datapoints that are not between the lower and upper bounds to provide subsets of datapoints of the local data within the lower and upper bounds;
and
collect, by the processor at the coordinator node, from the worker nodes, as collected qualifying data, all of the subsets of datapoints of the local data within the lower and upper bounds;
and
compute, by the processor at the coordinator node, based on the quantile ranks and the collected qualifying data which were collected from the worker nodes, the precise quantiles.

8 more elements

Dependencies are inferred from the claim text.