Systems and Methods for Quantile Estimation in a Distributed Data System

Abstract

In accordance with the teachings described herein, systems and methods are provided for estimating quantiles for data stored in a distributed system. In one embodiment, an instruction is received to estimate a specified quantile for a variate in a set of data stored at a plurality of nodes in the distributed system. A plurality of data bins for the variate are defined that are each associated with a different range of data values in the set of data. Lower and upper quantile bounds for each of the plurality of data bins are determined based on the total number of data values that fall within each of the plurality of data bins. The specified quantile is estimated based on an identified one of the plurality of data bins that includes the specified quantile based on the lower and upper quantile bounds.

It is claimed: 
     
         1 . A computer-implemented method for estimating quantiles for data stored in a distributed system, comprising:
 receiving an instruction to estimate a specified quantile for a variate in a set of data stored at a plurality of nodes in the distributed system;   identifying a minimum data value and a maximum data value for the variate from the set of data;   defining a plurality of data bins for the variate, wherein the plurality of data bins collectively range from the minimum data value to the maximum data value and each of the plurality of data bins is associated with a different range of data values in the set of data;   determining a total number of data values in the set of data that fall within each of the plurality of data bins;   determining lower and upper quantile bounds for each of the plurality of data bins based at least in part on the total number of data values that fall within each of the plurality of data bins;   identifying one of the plurality of data bins that includes the specified quantile based on the lower and upper quantile bounds;   estimating the specified quantile based on the identified one of the plurality of data bins; and   storing data including the estimated specified quantile and the upper and lower quantile bounds.