IP Library › Patent Application 14997383
Patent Application
App. No. 14/997,383

Systems and Methods for Quantile Estimation in a Distributed Data System

Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US None
App. No.
14/997,383
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.

Claims (9)

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.