Analytic system for fast quantile computation with improved memory consumption strategy

A non-transitory computer-readable medium having stored thereon computer-readable instructions that when executed by a computing device cause the computing device to:

• (a) compute a maximum value and a minimum value for a plurality of unsorted variable values of a variable read from a dataset;
• (b) compute an upper bin value and a lower bin value for each bin of a plurality of bins using the computed maximum value and the computed minimum value;
• (c) compute a frequency counter for each bin of the plurality of bins by reading the plurality of unsorted variable values of the variable from the dataset a second time, wherein each frequency counter is a count of the variable values within a respective bin based on a variable value between the computed upper bin value and the computed lower bin value of the respective bin;
• (d) compute a bin number and a cumulative rank value for a quantile using the frequency counter for each bin of the plurality of bins, wherein the bin number identifies a specific bin of the plurality of bins within which a quantile value associated with the quantile is located, wherein the cumulative rank value identifies a cumulative rank for the quantile value associated with the quantile;
• (e) estimate a memory usage value for storing frequency data based on the computed frequency counter for the computed bin number for the quantile;
• (f) when the estimated memory usage value exceeds a predefined memory size constraint value, split a subset of the plurality of bins into a predefined bin split numerical value number of bins, recompute the frequency counter for each of the predefined bin split numerical value number of bins and for each bin of the subset of the plurality of bins, and recompute the bin number and the cumulative rank value for the quantile using an updated frequency counter for each of the predefined bin split numerical value number of bins for each bin of the subset of the plurality of bins and for each remaining bin of the plurality of bins not included in the subset of the plurality of bins;
• (g) compute the frequency data for each unique value of the variable values read from the dataset that is between the computed upper bin value and the computed lower bin value of the recomputed bin number by reading the plurality of unsorted variable values of the variable from the dataset a third time, wherein the frequency data includes the variable value and a number of occurrences of the variable value for each unique value;
• (h) compute the quantile value associated with the quantile using the computed frequency data and the recomputed cumulative rank value for the quantile;
• and
• (i) output the computed quantile value.

A method of computing a quantile value, the method comprising:

• (a) computing, by a computing device, a maximum value and a minimum value for a plurality of unsorted variable values of a variable read from a dataset;
• (b) computing, by the computing device, an upper bin value and a lower bin value for each bin of a plurality of bins using the computed maximum value and the computed minimum value;
• (c) computing, by the computing device, a frequency counter for each bin of the plurality of bins by reading the plurality of unsorted variable values of the variable from the dataset a second time, wherein each frequency counter is a count of the variable values within a respective bin based on a variable value between the computed upper bin value and the computed lower bin value of the respective bin;
• (d) computing, by the computing device, a bin number and a cumulative rank value for a quantile using the frequency counter for each bin of the plurality of bins, wherein the bin number identifies a specific bin of the plurality of bins within which a quantile value associated with the quantile is located, wherein the cumulative rank value identifies a cumulative rank for the quantile value associated with the quantile;
• (e) estimating, by the computing device, a memory usage value for storing frequency data based on the computed frequency counter for the computed bin number for the quantile;
• (f) when the estimated memory usage value exceeds a predefined memory size constraint value, splitting, by the computing device, a subset of the plurality of bins into a predefined bin split numerical value number of bins, recomputing the frequency counter for each of the predefined bin split numerical value number of bins and for each bin of the subset of the plurality of bins, and recomputing the bin number and the cumulative rank value for the quantile using an updated frequency counter for each of the predefined bin split numerical value number of bins for each bin of the subset of the plurality of bins and for each remaining bin of the plurality of bins not included in the subset of the plurality of bins;
• (g) computing, by the computing device, the frequency data for each unique value of the variable values read from the dataset that is between the computed upper bin value and the computed lower bin value of the recomputed bin number by reading the plurality of unsorted variable values of the variable from the dataset a third time, wherein the frequency data includes the variable value and a number of occurrences of the variable value for each unique value;
• (h) computing, by the computing device, the quantile value associated with the quantile using the computed frequency data and the recomputed cumulative rank value for the quantile;
• and
• outputting, by the computing device, the computed quantile value.