Patent Publication Number: US-2016246852-A1

Title: Systems and Methods for Quantile Estimation in a Distributed Data System

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
     This application is a continuation of U.S. application Ser. No. 13/482,095 filed May 29, 2012, which is incorporated by reference in its entirety. 
    
    
     FIELD 
     The technology described in this patent document relates generally to computer-implemented systems and methods for estimating quantiles for data stored in a distributed system. 
     BACKGROUND 
     Quantiles are commonly used for various applications involving frequency data. Finding quantiles of a variate in small data sets is a relatively simple matter. As the number of observed values in the data set increases, however, the quantile problem becomes more difficult. Further complicating the problem is that large data sets are often stored in distributed systems in which different components (e.g., nodes) of the system have access to different portions of the data. 
     SUMMARY 
     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 minimum data value and a maximum data value for the variate are identified from the set of data. A plurality of data bins for the variate is defined, 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. A total number of data values in the set of data that fall within each of the plurality of data bins is determined. 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. One of the plurality of data bins is identified that includes the specified quantile based on the lower and upper quantile bounds. The specified quantile is estimated based on the identified one of the plurality of data bins. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is a block diagram of an example system for estimating quantiles for data stored in a distributed system. 
         FIG. 2  is a block diagram of another example system  200  for estimating quantiles for data stored in a distributed system  200  in which data is stored in a plurality of separate files at different nodes  204 ,  206  in the distributed system. 
         FIG. 3  is a block diagram of another example system  300  for estimating quantiles for data stored in a distributed system  300 . 
         FIGS. 4-8E  depict examples of how quantiles may be estimated using the systems and methods described herein. 
         FIG. 9  depicts an example of a distributed system that may be used for estimating quantiles. 
     
    
    
     DETAILED DESCRIPTION 
       FIG. 1  is a block diagram of an example system  100  for estimating quantiles for data stored in a distributed system. The system  100  includes a quantile estimation engine  102  that executes in a distributed system in which data is stored in a plurality of separate files at different nodes  104 ,  106  in the distributed system. As used herein, a distributed system consists of a plurality of separate computers and/or databases that are connected together through a network, and a node in the distributed system may include any one of the computers or databases in the distributed system. Typically, the nodes of a distributed system are connected using middleware such that the entire distributed system appears to a user as a single, integrated computing system. In the example illustrated in  FIG. 1 , the data of interest is stored in files at two separate nodes  104 ,  106  of the distributed system. The quantile estimation engine  102  may, for example, be a software application that is executed by a processor located either at nodes  104  or  106  or at a separate node in the distributed system. It should be understood that although two nodes are shown in the examples illustrated in  FIGS. 1-3 , a distributed system may include data stored in files located in more than two nodes. 
     In operation, the quantile estimation engine  102  receives an instruction  108  that identifies a quantile to be estimated for a variate in a set of data stored in a plurality of files at separate nodes  104 ,  106  in the distributed system. The quantile estimation instruction  108  may, for example, be received from user input or from another software module in the system. 
     Upon receiving the quantile estimation instruction  108 , the system  100  executes the processes depicted at  110 - 116  in  FIG. 1  in order to generate the quantile estimate  118  for the set of data. It should be understood that the steps of the method depicted in  FIG. 1  may be performed entirely by the quantile estimation engine  102  or, alternatively, the quantile estimation engine  102  may cause one or more steps or portions of one or more steps to be performed by other nodes  104 ,  106  of the distributed system. 
     At  110 , the system  100  performs a single pass through the set of data to determine the minimum and maximum values for the variate. At  111 , the quantile estimation engine  102  defines a plurality of data bins for the variate. The data bins for a variate collectively range from the minimum data value to the maximum data value for the variate in the set of data, with each data bin being associated with a different range of data values in the set of data. 
     At  112 , the system  100  performs another pass through the set of data to determine a count of the total number of data values for the variate that fall within each of the plurality of data bins. From the bin counts, the quantile estimation engine  102  determines, at  113 , the upper and lower bounds on the percentages for each of the plurality of data bins. At  114 , the quantile estimation engine  102  determines if one of the plurality of data bins has converged on the quantile specified in the quantile estimation instruction  108 . For example, the quantile estimation engine  102  may be configured to estimate the quantile  118  to a predetermined level of precision. The level of precision may, for example, be based on the absolute error bound for quantiles in the bin. For instance, if the specified quantile is between the upper and lower quantile bounds for a bin and the absolute error (e.g., calculated as half the distance between the upper and lower bounds) is within the predetermined precision level, then the quantile estimation engine  102  may estimate the quantile  118  from the data values within the bin. For example, the quantile estimate  118  may be selected from a data value at the midpoint of the bin or as a weighted average of the data values in the bin. 
     If one of the plurality of data bins has not converged on the specified quantile, then, at  115 , the quantile estimation engine  102  isolates one of the plurality of bins that includes the specified quantile. The method then returns to  111 , where the quantile estimation engine  102  defines a new set of data bins that collectively range from the lower to upper quantile bounds of the isolated bin. The method then repeats steps  112  and  113  to make another pass through the data set with the redefined data bins. This process is repeated until a data bin converges on the specified quantile (possibly within a predetermined precision level), at which point the quantile estimate  118  is provided and the quantile estimation method ends at  116 . 
       FIG. 2  is a block diagram of another example system  200  for estimating quantiles for data stored in a distributed system  200  in which data is stored in a plurality of separate files at different nodes  204 ,  206  in the distributed system. In this example, instructions  208  received by the quantile estimation engine  202  may specify a single quantile for estimation or may specify multiple quantiles (e.g., a vector of quantiles) for estimation. As explained below, if multiple quantiles for a set of data are specified for estimation, then the quantile estimation engine  202  may simultaneously determine quantile estimates for each of the multiple quantiles. In addition, the quantile estimate engine  202  may be configured to simultaneously estimate quantiles for multiple variates and data sets. The quantile estimation instructions  208  may therefore identify multiple variates and multiple data sets for quantile estimation. 
     Upon receiving the quantile estimation instruction(s)  208 , the system  200  executes the processes depicted at  210 - 218  in  FIG. 2  in order to generate the quantile estimate(s)  220 . In this example  200 , a dotted line  222  is included to illustrate processes that may be performed by the quantile estimation engine  202  and processes that may be performed at the distributed nodes  204 ,  206 . Specifically, in the illustrated example, the processes depicted to the left of the dotted line  222  are performed by the distributed nodes  204 ,  206  and the processes depicted to the right of the dotted line  222  are performed by the quantile estimation engine  202 . 
     At steps  210  and  211 , the system  200  performs a single pass through the set(s) of data to determine the minimum and maximum values for each variate. At  210 , each node  204 ,  206  that holds portions of the data for the identified variate(s) determines the maximum and minimum values of the variate(s) for its data and sends this information back to the quantile estimation engine  202 . At  211 , the quantile estimation engine  202  combines the data counts and minimum and maximum values from the distributed nodes  204 ,  206  to determine the counts, minimum and maximum values for the entire set(s) of data. 
     At  212 , the quantile estimation engine  202  defines a plurality of data bins for each variate. The data bins for a variate collectively range from the minimum data value to the maximum data value for the set of data, with each data bin being associated with a different range of data values in the set of data. If the quantile estimation instructions  208  identify multiple variates and/or data sets, then a different plurality of data bins are defined for each variate and data set. In addition, if multiple quantiles are included in the quantile estimation instructions, then a different plurality of data bins may be defined for each quantile. 
     At steps  213  and  214 , the system  200  performs another pass through the set(s) of data to determine the number of data values that fall within each of the plurality of data bins for each variate. At  213 , each node  204 ,  206  performs frequency counts of the variate for its data and projects the frequency counts into each bin. If the quantile estimation instructions  208  identify multiple variates and/or data sets, then the nodes  204 ,  206  may perform frequency counts and obtain maximum and minimum values for each variate and/or data set during the same data pass. The nodes  204 ,  206  send the bin counts and minimum and maximum values to the quantile estimation engine  202  which, at  214 , combines the bin counts from each of the nodes  204 ,  206  to determine the total bin counts for each variate. In addition, in this example, each node  204 ,  206  also identifies, at step  213 , the minimum and maximum data values within each of the plurality of data bins for each variate and returns these minimum/maximum values to the quantile estimation engine  202 , which combines the minima and maxima from each node  204 ,  206  at step  214 . In this way, the combined minimum and maximum values for each bin may be used by the quantile estimation engine  202  to help identify the location of the desired quantile and potentially speed up the convergence process. 
     At  215 , the quantile estimation engine  202  determines the upper and lower bounds on the percentages for each of the plurality of data bins based on the bin counts. The quantile estimation engine  202  may then determine, at  216 , if one of the plurality of data bins has converged, to a predetermined precision level, on the quantile(s) specified in the quantile estimation instruction  208 . As illustrated, the precision level necessary for convergence may, for example, be included in the quantile estimation instruction  208 . If one of the plurality of data bins has not converged on the specified quantile(s), then, at  217 , the quantile estimation engine  202  isolates one of the plurality of bins that includes the specified quantile(s), and returns to step  212  to define a new set of data bins that include the data values from the isolated bin. This process is repeated until a data bin converges on the specified quantile(s), at which point a quantile estimate  220  is determined from the data values in the bin, and the method ends at  218 . 
       FIG. 3  is a block diagram of another example system  300  for estimating quantiles for data stored in a distributed system  300 . In this example, the instructions  302  received by the quantile estimation engine  304  may also include one or more constraints to limit the data values included in the quantile estimation. For instance, the constraint(s) may limit the quantile estimation to one or more subcategories of data for the identified variate(s). As an example, the constraint(s) could limit the quantile estimation to data values for a variate from a certain geographic region, during a certain time period, or based on some other criteria. In addition, the example illustrated in  FIG. 3  may establish non-uniform data bins, for instance to help speed up the convergence process. 
     In operation, the system  300  depicted in  FIG. 3  executes the processes depicted at steps  310 - 319  upon receiving the quantile estimation instruction(s)  302 . Again in this example  300 , a dotted line  332  is included to illustrate processes that may be performed by the quantile estimation engine  304  (depicted to the right of the dotted line) and processes that may be performed at the distributed nodes  306 ,  308  (depicted to the left of the dotted line). 
     At steps  310  and  311 , the system  300  performs a single pass through the set(s) of data to determine the minimum and maximum values for each variate, subject to any constraints identified in the quantile estimation instructions  302 . Specifically, at  310 , each node  306 ,  308  that holds portions of the data for the identified variate(s) determines the maximum and minimum values of the variate(s) for its data, subject to any constraints, and sends this information back to the quantile estimation engine  304 . For example, if the quantile estimation instruction  302  includes a constraint that identifies a particular geographic region, then each node  306 ,  308  determines the minimum and maximum values of the variate(s) within its data that are associated with the identified geographic region. At  311 , the quantile estimation engine  304  combines the data counts from the distributed nodes  306 ,  308  to determine the minimum and maximum values for the entire set(s) of data. 
     At  312 , the quantile estimation engine  304  defines a grid size and distribution for a plurality of data bins for each variate. A grid for a set of data bins, as used herein, is the set of points that define the bounds of the data bins. That is, a set of data bins for a variate collectively include the data values between a minimum value and a maximum value. The set of points between the minimum and maximum values that define the bounds of each bin are referred to as the grid, where the grid size refers to the number of points in the grid and the grid distribution refers to where each of the set of grid points are located. (See, e.g., the examples described below with reference to  FIGS. 4-8E ). A grid for a set of data bins may be uniform or non-uniform. A non-uniform grid may, for example, be defined based on some known or calculated information regarding the likely position of the desired quantile within the data. For example, a non-uniform grid may be based on information obtained from a previous data pass (e.g., while isolating a data bin at  319 .) In another example, a non-uniform data grid may be established by applying a known quantile algorithm, such as conformal mapping, and using the resultant data to include likely quantile values in the same bin. In another example, a non-uniform grid distribution may be used to isolate one or more outlier data values. In the example illustrated in  FIG. 3 , one or more of these processes to define a non-uniform grid may be performed at process step  313 . Once the grid is defined, the data values are distributed into the plurality of bins at  314 . 
     At steps  315  and  316 , the system  300  performs another pass through the set(s) of data to determine the number of data values that fall within each of the plurality of data bins for each variate, along with the minimum and maximum data values within each bin. At  315 , each node  306 ,  308  performs frequency counts of the variate and projects the frequency counts into each bin. Each node  306 ,  308  also determines the minimum and maximum data values in each of the plurality of bins for each variate. The nodes  306 ,  308  then send the bin counts and the minimum and maximum values to the quantile estimation engine  304 , which combines them at  316  to determine total bin counts and minimum/maximum values for each variate 
     At  317 , the quantile estimation engine  304  determines the upper and lower bounds on the percentages for each of the plurality of data bins based on the bin counts. The quantile estimation engine  304  may then determine, at  318 , if one of the plurality of data bins has converged (e.g., to a predetermined precision level) on the specified quantile(s). If one of the plurality of data bins has not converged on the specified quantile(s), then, at  319 , the quantile estimation engine  304  isolates one of the plurality of bins that includes the specified quantile(s), and returns to step  312  to define a new data grid that includes the data values from the isolated bin. This process is repeated until a data bin converges on the specified quantile(s), at which point a quantile estimate  330  is determined from the data values in the bin, and the method ends at  320 . 
       FIGS. 4-6C  depict a first example of how a quantile may be estimated using the systems and methods described herein.  FIG. 4  illustrates example data values for a variate that are split between two nodes (server  1  and server  2 )  402 ,  404  in a distributed system. In this example, each data value represents an observed value for the same variate (the observations have been arranged in multiple columns for readability.) In total, the example includes 100 observed data values, with 50 observations stored at each of the two nodes  402 ,  404 . The goal of the illustrated example is to estimate the 75% quantile for the example set of data shown in  FIG. 4 . The exact answer to this query is 83.1. 
       FIG. 5A  illustrates an example of data that may be obtained from a first pass through the data shown in  FIG. 4 . As illustrated, the first node (server  1 ) determines that its stored data for the variate includes a count of 50 data values with a minimum data value of 1.1 and a maximum data value of 98.4. The second node (server  2 ) in the illustrated example determines that its stored data for the variate includes a count of 50 data values with a minimum data value of 7.2 and a maximum data value of 97.8. As shown, combined results may be determined (e.g., by a centralized node) from the data from the first and second nodes. In the illustrated example, the combined results include a total of 100 data values with a minimum value of 1.1 and a maximum value of 98.4. 
       FIG. 5B  illustrates an example of how data bins may be defined based on the minimum and maximum data values and how bin counts may be determined from a second pass through the data shown in  FIG. 4 . In this example, the data bins are defined with a grid size of 3 and with a uniform distribution. Equally spacing 3 points (rounded to 2 decimal places) between the minimum (1.1) and the maximum (98.4) data values, results in grid points of 25.45, 49.76 and 74.07. This results in four data bins, as illustrated in column  502  in  FIG. 5B . In a second pass through the data, the distributed nodes (server  1  and server  2 ) perform a count of the number of data values and the minimum and maximum values in each bin and return the results to the centralized node (e.g., the quantile estimation engine), as illustrated in columns  504  and  506 . The centralized node then combines the results, as illustrated in column  508 , and determines the quantile bounds for each bin, as shown in column  510 . For instance, in the illustrated example, the upper quantile bound for Bin  1  represents the 25% quantile [Bin  1  Count (25)/Total Count (100)], the upper quantile for Bin  2  represents the 48% quantile [Sum of Bin  1  and  2  Counts (25+23)/Total Count (100)], and so on. From this information, the centralized node can determine that the desired 75% quantile must be included within Bin  4 , which has a lower quantile bound representing the 69% quantile and an upper bound representing the 100% quantile. If the data range within Bin  4  meets the desired level of precision, then a quantile estimate may be determine from the information shown in  FIG. 5B . For example, the value at the mid-point of Bin  4  (74.07≦x≦98.4) may be selected, resulting in an estimated 75% quantile of 86.24. However, if greater precision is desired, then Bin  4  may be further refined into a new set of data bins, as illustrated in  FIG. 5C . 
     In  FIG. 5C , the data from the isolated bin (Bin  4 ) is separated into four new uniform bins (Bins  4 . 1 - 4 . 4 ), as shown in col.  512 . In a third pass, the distributed nodes (server  1  and server  2 ) perform a count of the data values in each of the redefined bins and return the results to the centralized node, as illustrated in columns  514  and  516 . The counts are then combined, as shown in column  518 , and the quantile bounds for each bin are calculated, as shown in column  520 . The centralized node may now isolate the desired 75% quantile to Bin  4 . 2 , which has a lower bound of 80.14 and an upper bound of 86.22. The actual quantile may reside anywhere within Bin  4 . 2 . The midpoint of the bin, 83.18, may be selected as the estimated 75% quantile, or further iterations could be performed to refine the estimate. In this example, each added iteration would reduce the error by a factor of at least ¼. 
       FIG. 6A-6C  illustrate another example using the data from  FIG. 4 , but with a non-uniform grid. Again, the goal of the example is to estimate the 75% quantile for the data in  FIG. 4 .  FIG. 6A  illustrates the minimum and maximum data values obtained from a first pass through the data, which is the same as in the uniform grid example shown in  FIG. 5A . A non-uniform grid is then established, which for this example includes grid points at 62.5%, 75% and 87.5% of the distance from the lower bin value to the upper bin value. These grid points may, for example, have been selected to cluster the bins around where the desired 75% quantile should be located if the distribution was uniform. The resulting non-uniform bins (Bin 1 -Bin 4 ) are illustrated in column  602  of  FIG. 6B . 
     In a second pass through the data, the distributed nodes (server  1  and server  2 ) perform a count of the number of data values and minimum and maximum values in each bin and return the results to the centralized node, as illustrated in columns  604  and  606 . The centralized node then combines the results, as illustrated in column  608 , and determines the quantile bounds for each bin, as shown in column  610 .  FIG. 6B  also tracks the minimum and maximum values within each bin, which may, for example, be used in the creation of a non-uniform grid to narrow the span of bins generated in further iterations. 
     From this information, the centralized node can determine that the desired 75% quantile must be included within Bin  3 , which has a lower quantile bound of 74.07% and an upper bound of 85.5. If the data range within Bin  3  meets the desired level of precision, then a quantile estimate may be determine from the information shown in  FIG. 6B . For example, the value at the mid-point of Bin  3  (74.07≦x≦86.22) may be selected, resulting in an estimated 75% quantile of 80.15. However, if greater precision is desired, then Bin  3  may be further refined into a new set of data bins, as illustrated in  FIG. 6C . 
     In  FIG. 6C , the data from the isolated bin (Bin  3 ) is separated into four uniform bins (Bins  3 . 1 - 3 . 4 ), as shown in col.  612 . In other examples, however, information regarding the likely position of the quantile within the isolated bin could be used to separate the isolated bin into another non-uniform set of data bins. In a third pass, the distributed nodes (server  1  and server  2 ) perform a count of the data values in each of the redefined bins and return the results to the centralized node, as illustrated in columns  614  and  616 . The counts are then combined, as shown in column  618 , and the quantile bounds for each bin are calculated, as shown in column  620 . In the illustrated example, the process has converged on the exact 75% quantile of 83.1, located in Bin  3 . 3 . 
       FIGS. 7-8E  depict another example in which the data of interest is non-numerical. In this example, the data of interest is the text of the U.S. Bill of Rights, which is stored at two separate nodes (server  1  and server  2 ) in a distributed system, as illustrated in  FIG. 7 . Specifically, the text from Amendments I-V is stored in a file located at a first node (server  1 )  702  and the text from Amendments VI-X is stored in a file located at a second node (server  2 )  704 . This example finds the 23% quantile of the words in the Bill of Rights. That is, the example determines the word that appears in the Bill of Rights that follows alphabetically 23% of all words appearing in the Bill of Rights. 
     It should be understood that there is a technicality involved with character data that isn&#39;t involved with numerical data. Depending on the number of datum, there may not be a datum for which 23% of the total data are less. Consider, for instance, the following example: 
       Data={1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, Desired quantile=23%. 
     In this data set, 20% of the data is less than or equal to 2, 30% of the data is less than or equal to 3. In practice, some systems report the 23% quantile to be 2, some report 3, some report the average 2.5, others report an interpolated value 2.3, and still others report some other interpolated number between 2 and 3. 
     Interpolation of character data typically does not give meaningful results. Instead, one or the two words adjacent to the desired percentile are reported. The character equivalent to the numerical example set forth above is: 
       Data={a, b, c, d, e, f, g, h, i, j}, Desired quantile=23%. 
     The answer to this example could be either ‘b’ or ‘c’. 
     To create the data bin boundaries for character data, a scheme may be used to interpolate character data. The bin boundaries will not be meaningful words under the interpolation scheme. However, the maximum and minimum words (alphabetically) may be stored for each bin. 
       FIG. 8A  illustrates the minimum and maximum words obtained from a first pass through the data. As shown, the first node (server  1 ) determines that its stored data includes a count of 266 words with a minimum word (alphabetically) of “a” and a maximum word of “witness.” The second node (server  2 ) in the illustrated example determines that its stored data includes a count of 196 words with a minimum word of “a” and a maximum word of “witnesses.” As illustrated, the combined results may then be determined (e.g., by a centralized node), resulting in a combined total of 462 words with a minimum of “a” and a maximum of “witnesses.” With a total of 462 words in the stored data, the example is looking for word number 462*0.23=106.26, to locate the 23% quantile. The example will therefore report words  106  and  107 . 
     In one example, to create the bin points for the character data each word may be mapped to an integer. This may be accomplished, for example, by locating the longest word in the data (in this case “establishment” with 13 letters) and consider each word as a number, in base 26, created by left-justifying the word with a=0, b=1, c=2, . . . , z=25. This reduces the bin creating process to the same problem as the numerical examples. 
     To reduce the number of comparisons, a minimum number of alphabetic digits may be determined in order to arrive at a desired number of distinct bins. For instance, to provide  3  bin boundaries between ‘a’ and ‘witnesses’, bins are only necessary between ‘a’=0 and ‘w’=22. The 25% bin boundary would therefore be (22−0)*0.25=5.5 (between ‘f’ and ‘g’, which we can round to ‘g’); the 50% bin boundary would be (22−0)*0.5=11 (‘l’), and the 75% bin boundary would be (22−0)*0.75=16.5 (between ‘q’ and ‘r’, which rounds to ‘r’). These resulting bins are illustrated in  FIG. 8B , at column  810 . 
     In a second pass through the data, the distributed nodes (server  1  and server  2 ) perform a count of the number of data values in each bin along with the minimum and maximum data values, as shown in columns  812  and  814  of  FIG. 8B . The centralized node then combines the results, as illustrated in column  816 , and determines the cumulative sum for each bin, as shown in column  818 . In the illustrated example, the cumulative sum of the first bin is  143 , therefore the desired quantile is located in Bin  1  between the words ‘a’ and ‘freedom.’ Bin  1  may then be divided into a new set of data bins to further isolate the desired quantile, as illustrated in  FIG. 8C . 
     In  FIG. 8C , the data from the isolated bin (Bin  1 ) is separated into four new bins (Bins  1 . 1 - 1 . 4 ), as shown at column  820 . In a third data pass, the distributed nodes (server  1  and server  2 ) determine a data count and minimum/maximum data values in each of the redefined bins, and return the results to the centralized node, as illustrated in columns  822  and  824 . The counts are then combined, as shown in column  826 , and the cumulative sum for each bin is determined, as shown in column  828 . In this example, the cumulative sum of the first two bins is  110 , therefore the desired quantile is located in Bin  1 . 2  between the words ‘bail’ and cruel.’ To further isolate the quantile, Bin  1 . 2  may be separated into four more bins, as shown in  FIG. 8D . 
     In  FIG. 8D , the data from the isolated bin (Bin  1 . 2 ) is separated into four new bins (Bins  1 . 2 . 1 - 1 . 2 . 4 ), as shown at column  830 . In a fourth data pass, the distributed nodes (server  1  and server  2 ) determine a data count and minimum/maximum data values in each of the redefined bins, and return the results to the centralized node, as illustrated in columns  832  and  834 . The counts are then combined, as shown in column  836 , and the cumulative sum for each bin is determined, as shown in column  838 . From this information, it can be seen that the quantile is located in Bin  1 . 2 . 4  between the words ‘committed’ and criminal.’ To further isolate the quantile, Bin  1 . 2 . 4  may be separated into four more bins, as shown in  FIG. 8E . 
     In  FIG. 8E , the data from the isolated bin (Bin  1 . 2 . 4 ) is separated into four new bins (Bins  1 . 2 . 4 . 1 - 1 . 2 . 4 . 4 ), as shown at column  840 . In a fifth data pass, the distributed nodes (server  1  and server  2 ) determine a data count and minimum/maximum data values in each of the redefined bins, and return the results to the centralized node, as illustrated in columns  842  and  844 . The counts are then combined, as shown in column  846 , and the cumulative sum for each bin is determined, as shown in column  848 . In the illustrated example, the process has converged on the desired 23% quantile (i.e., the 106 th  or 107 th  word alphabetically) in Bin  1 . 2 . 4 . 4 , which is the word ‘crime’. 
       FIG. 9  depicts an example of a distributed system  900  that may be used for estimating quantiles. The distributed system  900  includes a plurality of nodes  902  that are connected together though one or more networks  904  and which may be accessed over the network(s)  904  by one or more computers or network terminals  906 . Each node  902  may include one or more servers  908  executing data storage and retrieval software on a processing system  910 . Each node  902  may also include one or more data stores  912  and/or computer readable medium  914 . One of the nodes  902  may, for example, be a centralized node that executes a quantile estimation engine, as described herein. In addition, the nodes  902  of the distributed system  900  may be connected using middleware (not shown) such that the entire distributed system  900  appears to a user as a single, integrated computing system. 
     This written description uses examples to disclose the invention, including the best mode, and also to enable a person skilled in the art to make and use the invention. The patentable scope of the invention may include other examples. Additionally, the methods and systems described herein may be implemented on many different types of processing devices by program code comprising program instructions that are executable by the device processing subsystem. The software program instructions may include source code, object code, machine code, or any other stored data that is operable to cause a processing system to perform the methods and operations described herein. Other implementations may also be used, however, such as firmware or even appropriately designed hardware configured to carry out the methods and systems described herein. 
     The systems&#39; and methods&#39; data (e.g., associations, mappings, data input, data output, intermediate data results, final data results, etc.) may be stored and implemented in one or more different types of computer-implemented data stores, such as different types of storage devices and programming constructs (e.g., RAM, ROM, Flash memory, flat files, databases, programming data structures, programming variables, IF-THEN (or similar type) statement constructs, etc.). It is noted that data structures describe formats for use in organizing and storing data in databases, programs, memory, or other computer-readable media for use by a computer program. 
     The computer components, software modules, functions, data stores and data structures described herein may be connected directly or indirectly to each other in order to allow the flow of data needed for their operations. It is also noted that a module or processor includes but is not limited to a unit of code that performs a software operation, and can be implemented for example as a subroutine unit of code, or as a software function unit of code, or as an object (as in an object-oriented paradigm), or as an applet, or in a computer script language, or as another type of computer code. The software components and/or functionality may be located on a single computer or distributed across multiple computers depending upon the situation at hand. 
     It should be understood that as used in the description herein and throughout the claims that follow, the meaning of “a,” “an,” and “the” includes plural reference unless the context clearly dictates otherwise. Also, as used in the description herein and throughout the claims that follow, the meaning of “in” includes “in” and “on” unless the context clearly dictates otherwise. Finally, as used in the description herein and throughout the claims that follow, the meanings of “and” and “or” include both the conjunctive and disjunctive and may be used interchangeably unless the context expressly dictates otherwise; the phrase “exclusive or” may be used to indicate situation where only the disjunctive meaning may apply.