Patent Publication Number: US-10311128-B2

Title: Analytic system for fast quantile computation with improved memory consumption strategy

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
     The present application claims the benefit of 35 U.S.C. § 111(e) to U.S. Provisional Patent Application No. 62/563,142 filed on Sep. 26, 2017, the entire contents of which are hereby incorporated by reference. The present application is also a continuation-in-part of U.S. patent application Ser. No. 15/961,373 that was filed Apr. 24, 2018, the entire contents of which are hereby incorporated by reference. 
    
    
     BACKGROUND 
     Quantiles (or percentiles) are essential statistical descriptions for data. They provide a numerical and an accurate view of data and the shape of a data distribution. However, computing exact quantiles for distributed data systems and/or big data environments remains challenging because data stored in different computing nodes and the amount of data prevents sorting, which is commonly used to compute the quantiles. 
     SUMMARY 
     In an example embodiment, a non-transitory computer-readable medium is provided having stored thereon computer-readable instructions that, when executed by a computing device, cause the computing device to compute a quantile value. A maximum value and a minimum value are computed for a plurality of unsorted variable values of a variable read from a dataset. An upper bin value and a lower bin value are computed for each bin of a plurality of bins using the computed maximum value and the computed minimum value. A frequency counter is computed 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. 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. A bin number and a cumulative rank value are computed for a quantile using the frequency counter for each bin of the plurality of bins. The bin number identifies a specific bin of the plurality of bins within which a quantile value associated with the quantile is located. The cumulative rank value identifies a cumulative rank for the quantile value associated with the quantile. A memory usage value is estimated for storing frequency data based on the computed frequency counter for the computed bin number for the quantile. When the estimated memory usage value exceeds a predefined memory size constraint value, a subset of the plurality of bins are split into a predefined bin split numerical value number of bins, the frequency counter is recomputed 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 the bin number and the cumulative rank value are recomputed 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. The frequency data is computed 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. The frequency data includes the variable value and a number of occurrences of the variable value for each unique value. The quantile value associated with the quantile is computed using the computed frequency data and the recomputed cumulative rank value for the quantile. The computed quantile value is output. 
     In another example embodiment, a computing device is provided. The computing device includes, but is not limited to, a processor and a non-transitory computer-readable medium operably coupled to the processor. The computer-readable medium has instructions stored thereon that, when executed by the computing device, cause the computing device to compute a quantile value. 
     In yet another example embodiment, a method of computing a quantile value is provided. 
     Other principal features of the disclosed subject matter will become apparent to those skilled in the art upon review of the following drawings, the detailed description, and the appended claims. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       Illustrative embodiments of the disclosed subject matter will hereafter be described referring to the accompanying drawings, wherein like numerals denote like elements. 
         FIG. 1  depicts a block diagram of a quantile computation device in accordance with an illustrative embodiment. 
         FIGS. 2A, 2B, 3 to 12, and 13A to 13C  depict flow diagrams illustrating examples of operations performed by the quantile computation device of  FIG. 1  in accordance with an illustrative embodiment. 
     
    
    
     DETAILED DESCRIPTION 
     Referring to  FIG. 1 , a block diagram of a quantile computation device  100  is shown in accordance with an illustrative embodiment. Quantile computation device  100  may compute a quantile value for each quantile of one or more quantile values. Quantile computation device  100  may include an input interface  102 , an output interface  104 , a communication interface  106 , a non-transitory computer-readable medium  108 , a processor  110 , a quantile computation application  122 , an input dataset  124 , quantile values  126 , and frequency data. Fewer, different, and/or additional components may be incorporated into quantile computation device  100 . 
     Quantile computation application  122  provides an efficient and exact method to locate quantiles in input dataset  124  that may be distributed or classified as “big data” due to the large number of values of the variable. Quantile computation application  122  avoids non-convergence situations that may occur using the iterative algorithm (the percentile action) and does not need expensive sorting that may occur using the sorting-based algorithm (the aggregate action). Quantile computation application  122  further evaluates whether memory is an issue. When memory is not an issue, quantile computation application  122  provides an efficient and exact method to locate quantiles in input dataset  124  with at most three passes through input dataset  124 . When memory is an issue, quantile computation application  122  applies additional steps that result in use of much less memory when the data in input dataset  124  is highly-skewed or highly-concentrated resulting in much better performance. Therefore, quantile computation application  122  is an improvement to existing processes performed by computing devices in solving the technical problem of computing quantiles from a dataset. Quantile computation application  122  does not require a stopping criterion such as a number of iterations or a convergence tolerance for which values may be difficult to define. Quantile computation application  122  also computes an exact quantile for any distributed or big data with comparable or significantly less computational cost and memory cost compared with existing methods. 
     Input interface  102  provides an interface for receiving information from the user or another device for entry into quantile computation device  100  as understood by those skilled in the art. Input interface  102  may interface with various input technologies including, but not limited to, a keyboard  112 , a microphone  113 , a mouse  114 , a display  116 , a track ball, a keypad, one or more buttons, etc. to allow the user to enter information into quantile computation device  100  or to make selections presented in a user interface displayed on display  116 . 
     The same interface may support both input interface  102  and output interface  104 . For example, display  116  comprising a touch screen provides a mechanism for user input and for presentation of output to the user. Quantile computation device  100  may have one or more input interfaces that use the same or a different input interface technology. The input interface technology further may be accessible by quantile computation device  100  through communication interface  106 . 
     Output interface  104  provides an interface for outputting information for review by a user of quantile computation device  100  and/or for use by another application or device. For example, output interface  104  may interface with various output technologies including, but not limited to, display  116 , a speaker  118 , a printer  120 , etc. Quantile computation device  100  may have one or more output interfaces that use the same or a different output interface technology. The output interface technology further may be accessible by quantile computation device  100  through communication interface  106 . 
     Communication interface  106  provides an interface for receiving and transmitting data between devices using various protocols, transmission technologies, and media as understood by those skilled in the art. Communication interface  106  may support communication using various transmission media that may be wired and/or wireless. Quantile computation device  100  may have one or more communication interfaces that use the same or a different communication interface technology. For example, quantile computation device  100  may support communication using an Ethernet port, a Bluetooth antenna, a telephone jack, a USB port, etc. Data and messages may be transferred between quantile computation device  100  and another computing device of distributed computing system  128  using communication interface  106 . 
     Computer-readable medium  108  is an electronic holding place or storage for information so the information can be accessed by processor  110  as understood by those skilled in the art. Computer-readable medium  108  can include, but is not limited to, any type of random access memory (RAM), any type of read only memory (ROM), any type of flash memory, etc. such as magnetic storage devices (e.g., hard disk, floppy disk, magnetic strips, . . . ), optical disks (e.g., compact disc (CD), digital versatile disc (DVD), . . . ), smart cards, flash memory devices, etc. Quantile computation device  100  may have one or more computer-readable media that use the same or a different memory media technology. For example, computer-readable medium  108  may include different types of computer-readable media that may be organized hierarchically to provide efficient access to the data stored therein as understood by a person of skill in the art. As an example, a cache may be implemented in a smaller, faster memory that stores copies of data from the most frequently/recently accessed main memory locations to reduce an access latency. Quantile computation device  100  also may have one or more drives that support the loading of a memory media such as a CD, DVD, an external hard drive, etc. One or more external hard drives further may be connected to quantile computation device  100  using communication interface  106 . 
     Processor  110  executes instructions as understood by those skilled in the art. The instructions may be carried out by a special purpose computer, logic circuits, or hardware circuits. Processor  110  may be implemented in hardware and/or firmware. Processor  110  executes an instruction, meaning it performs/controls the operations called for by that instruction. The term “execution” is the process of running an application or the carrying out of the operation called for by an instruction. The instructions may be written using one or more programming language, scripting language, assembly language, etc. Processor  110  operably couples with input interface  102 , with output interface  104 , with communication interface  106 , and with computer-readable medium  108  to receive, to send, and to process information. Processor  110  may retrieve a set of instructions from a permanent memory device and copy the instructions in an executable form to a temporary memory device that is generally some form of RAM. Quantile computation device  100  may include a plurality of processors that use the same or a different processing technology. 
     Some processors may be central processing units (CPUs). Some processes may be more efficiently and speedily executed and processed with machine-learning specific processors (e.g., not a generic CPU). Such processors may also provide additional energy savings when compared to generic CPUs. For example, some of these processors can include a graphical processing unit, an application-specific integrated circuit, a field-programmable gate array, an artificial intelligence accelerator, a purpose-built chip architecture for machine learning, and/or some other machine-learning specific processor that implements a machine learning approach using semiconductor (e.g., silicon, gallium arsenide) devices. These processors may also be employed in heterogeneous computing architectures with a number of and a variety of different types of cores, engines, nodes, and/or layers to achieve additional various energy efficiencies, processing speed improvements, data communication speed improvements, and/or data efficiency response variables and improvements throughout various parts of the system. 
     Quantile computation application  122  performs operations associated with defining frequency data and quantile values  126  from data stored in input dataset  124 . Quantile values  126  define a variable value of input dataset  124  that is associated with each quantile of one or more quantiles computed by ranking the variable values of input dataset  124 . Some or all of the operations described herein may be embodied in quantile computation application  122 . The operations may be implemented using hardware, firmware, software, or any combination of these methods. 
     Referring to the example embodiment of  FIG. 1 , quantile computation application  122  is implemented in software (comprised of computer-readable and/or computer-executable instructions) stored in computer-readable medium  108  and accessible by processor  110  for execution of the instructions that embody the operations of quantile computation application  122 . Quantile computation application  122  may be written using one or more programming languages, assembly languages, scripting languages, etc. Quantile computation application  122  may be integrated with other analytic tools. As an example, quantile computation application  122  may be part of an integrated data analytics software application and/or software architecture such as that offered by SAS Institute Inc. of Cary, N.C., USA. Merely for illustration, quantile computation application  122  may be implemented using or integrated with one or more SAS software tools such as JMP®, Base SAS, SAS® Enterprise Miner™, SAS/STAT®, SAS® High Performance Analytics Server, SAS® Visual Data Mining and Machine Learning, SAS® LASR™, SAS® In-Database Products, SAS® Scalable Performance Data Engine, SAS® Cloud Analytic Services, SAS/OR®, SAS/ETS®, SAS® Inventory Optimization, SAS® Inventory Optimization Workbench, SAS® Visual Analytics, SAS® Viya™, SAS In-Memory Statistics for Hadoop®, SAS® Forecast Server, and SAS/IML® all of which are developed and provided by SAS Institute Inc. of Cary, N.C., USA. Data mining, statistical analytics, and response prediction are applicable in a wide variety of industries to solve technical problems. 
     Quantile computation application  122  may be implemented as a Web application. For example, quantile computation application  122  may be configured to receive hypertext transport protocol (HTTP) responses and to send HTTP requests. The HTTP responses may include web pages such as hypertext markup language documents and linked objects generated in response to the HTTP requests. Each web page may be identified by a uniform resource locator that includes the location or address of the computing device that contains the resource to be accessed in addition to the location of the resource on that computing device. The type of file or resource depends on the Internet application protocol such as the file transfer protocol, HTTP, H.323, etc. The file accessed may be a simple text file, an image file, an audio file, a video file, an executable, a common gateway interface application, a Java applet, an extensible markup language file, or any other type of file supported by HTTP. 
     Input dataset  124  may include, for example, a plurality of rows and a plurality of columns. The plurality of rows may be referred to as observation vectors or records (observations), and the columns may be referred to as variables. In an alternative embodiment, input dataset  124  may be transposed. An observation vector is defined as x j  that may include a value for each of the plurality of variables associated with the observation j. Each variable of the plurality of variables may describe a characteristic of a physical object. For example, if input dataset  124  includes data related to operation of a vehicle, the variables may include an oil pressure, a speed, a gear indicator, a gas tank level, a tire pressure for each tire, an engine temperature, a radiator level, etc. Input dataset  124  may include data captured as a function of time for one or more physical objects. 
     The data stored in input dataset  124  may be generated by and/or captured from a variety of sources including one or more sensors of the same or different type, one or more computing devices, etc. The data stored in input dataset  124  may be received directly or indirectly from the source and may or may not be pre-processed in some manner. For example, the data may be pre-processed using an event stream processor such as the SAS® Event Stream Processing Engine (ESPE), developed and provided by SAS Institute Inc. of Cary, N.C., USA. As used herein, the data may include any type of content represented in any computer-readable format such as binary, alphanumeric, numeric, string, markup language, etc. The data may be organized using delimited fields, such as comma or space separated fields, fixed width fields, using a SAS® dataset, etc. The SAS dataset may be a SAS® file stored in a SAS® library that a SAS® software tool creates and processes. The SAS dataset contains data values that are organized as a table of observation vectors (rows) and variables (columns) that can be processed by one or more SAS software tools. 
     In data science, engineering, and statistical applications, data often consists of multiple measurements (across sensors, characteristics, responses, etc.) collected across multiple time instances (patients, test subjects, etc.). These measurements may be collected in input dataset  124  for analysis and processing. 
     Input dataset  124  may be stored on computer-readable medium  108  and/or on one or more computer-readable media of distributed computing system  128  and accessed by quantile computation device  100  using communication interface  106 , input interface  102 , and/or output interface  104 . Data stored in input dataset  124  may be sensor measurements or signal values captured by a sensor, may be generated or captured in response to occurrence of an event or a transaction, generated by a device such as in response to an interaction by a user with the device, etc. The data stored in input dataset  124  may include any type of content represented in any computer-readable format such as binary, alphanumeric, numeric, string, markup language, etc. The content may include textual information, graphical information, image information, audio information, numeric information, etc. that further may be encoded using various encoding techniques as understood by a person of skill in the art. The data stored in input dataset  124  may be captured at different time points periodically, intermittently, when an event occurs, etc. One or more columns of input dataset  124  may include a time and/or date value. 
     Input dataset  124  may include data captured under normal operating conditions of the physical object. Input dataset  124  may include data captured at a high data rate such as 200 or more observation vectors per second for one or more physical objects. For example, data stored in input dataset  124  may be generated as part of the Internet of Things (IoT), where things (e.g., machines, devices, phones, sensors) can be connected to networks and the data from these things collected and processed within the things and/or external to the things before being stored in input dataset  124 . For example, the IoT can include sensors in many different devices and types of devices, and high value analytics can be applied to identify hidden relationships and drive increased efficiencies. This can apply to both big data analytics and real-time analytics. Some of these devices may be referred to as edge devices, and may involve edge computing circuitry. These devices may provide a variety of stored or generated data, such as network data or data specific to the network devices themselves. Again, some data may be processed with an ESPE, which may reside in the cloud or in an edge device before being stored in input dataset  124 . 
     Input dataset  124  may be stored using various data structures as known to those skilled in the art including one or more files of a file system, a relational database, one or more tables of a system of tables, a structured query language database, etc. on quantile computation device  100  and/or on distributed computing system  128 . Quantile computation device  100  may coordinate access to input dataset  124  that is distributed across distributed computing system  128  that may include one or more computing devices. For example, input dataset  124  may be stored in a cube distributed across a grid of computers as understood by a person of skill in the art. As another example, input dataset  124  may be stored in a multi-node Hadoop® cluster. For instance, Apache™ Hadoop® is an open-source software framework for distributed computing supported by the Apache Software Foundation. As another example, input dataset  124  may be stored in a cloud of computers and accessed using cloud computing technologies, as understood by a person of skill in the art. The SAS® LASR™ Analytic Server may be used as an analytic platform to enable multiple users to concurrently access data stored in input dataset  124 . The SAS® Viya™ open, cloud-ready, in-memory architecture also may be used as an analytic platform to enable multiple users to concurrently access data stored in input dataset  124 . SAS® Cloud Analytic Services (CAS) may be used as an analytic server with associated cloud services in SAS® Viya™. Some systems may use SAS In-Memory Statistics for Hadoop® to read big data once and analyze it several times by persisting it in-memory for the entire session. Some systems may be of other types and configurations. 
     Referring to  FIGS. 2A, 2B, 3 to 12, and 13A to 13C , example operations associated with quantile computation application  122  are described. Quantile computation application  122  may be used to create quantile values  126  from input dataset  124 . Quantile computation application  122  may be executed directly by the user or may be called by another application with a request to compute one or more quantile values. Additional, fewer, or different operations may be performed depending on the embodiment of quantile computation application  122 . The order of presentation of the operations of  FIGS. 2A, 2B, 3 to 12, and 13A to 13C  is not intended to be limiting. Some of the operations may not be performed in some embodiments. Although some of the operational flows are presented in sequence, the various operations may be performed in various repetitions, concurrently (in parallel, for example, using threads and/or distributed computing system  128 ), and/or in other orders than those that are illustrated. For example, a user may execute quantile computation application  122 , which causes presentation of a first user interface window, which may include a plurality of menus and selectors such as drop-down menus, buttons, text boxes, hyperlinks, etc. associated with quantile computation application  122  as understood by a person of skill in the art. The plurality of menus and selectors may be accessed in various orders. An indicator may indicate one or more user selections from a user interface, one or more data entries into a data field of the user interface, one or more data items read from computer-readable medium  108  or otherwise defined with one or more default values, etc. that are received as an input by quantile computation application  122 . 
     Referring to  FIG. 2A , in an operation  200 , a first indicator may be received that indicates input dataset  124 . For example, the first indicator indicates a location and a name of input dataset  124 . As an example, the first indicator may be received by quantile computation application  122  after selection from a user interface window, after entry by a user into a user interface window, by extracting the information from a request, by reading an input file, etc. In an alternative embodiment, input dataset  124  may not be selectable. For example, a most recently created dataset may be used automatically. 
     In an operation  202 , a second indicator may be received that indicates variable x and a frequency value for variable x in input dataset  124 . For example, the second indicator may indicate a column number or a column name for each of variable x and the frequency value. As another option, a first pair or a last pair of columns of input dataset  124  may be assumed to be variable x and the frequency value. As an example, the second indicator may be received by quantile computation application  122  after selection from a user interface window, after entry by a user into a user interface window, by extracting the information from a request, by reading an input file, etc. 
     In an operation  204 , a third indicator may be received that indicates a quantile for which to compute a value of the variable x associated with the quantile. The quantile is a value between zero and one exclusive. Alternatively, the quantile may be a percentile that is converted to a decimal value after receipt. A plurality of quantiles may be received. N Q  is a number of the quantiles that may be one. Q references a set of the one or more quantiles indicated by the third indicator. For example, the plurality of quantiles may be a list of percentiles to compute provided by the user such as 0.15, 0.3, 0.35, 0.45, 0.5, 0.55, 0.75, where N Q =7, and Q={0.15, 0.3, 0.35, 0.45, 0.5, 0.55, 0.75}. In an alternative embodiment, the third indicator may not be received. For example, a default value(s) may be stored, for example, in computer-readable medium  108  and used automatically. In another alternative embodiment, the quantile(s) may not be selectable. Instead, a fixed, predefined value may be used. For illustration, a default value for the set of quantiles Q={0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9}, where N Q =9. One or more quantiles may be indicated using a variety of different methods. As an example, the third indicator may be received by quantile computation application  122  after selection from a user interface window, after entry by a user into a user interface window, by extracting the information from a request, by reading an input file, etc. If the one or more quantiles are not indicated in numerical order, the set of quantiles Q may be defined in numerical order based on the indicated numerical vales of the one or more quantiles. Q may be an array storing N Q  values though different types of data structures may be used in alternative embodiments. 
     In an operation  206 , a fourth indicator of a number of computing nodes N N  of distributed computing system  128  may be received. In an alternative embodiment, the fourth indicator may not be received. For example, a default value may be stored, for example, in computer-readable medium  108  and used automatically. In another alternative embodiment, the number of computing nodes may not be selectable. Instead, a fixed, predefined value may be used. For illustration, a default value of the number of computing nodes may be one to indicate that quantile computation device  100  performs the operations of  FIGS. 2A, 2B, 3 to 12, and 13A to 13C  without any other computing devices. As an example, the fourth indicator may be received by quantile computation application  122  after selection from a user interface window, after entry by a user into a user interface window, by extracting the information from a request, by reading an input file, etc. 
     In an operation  208 , a fifth indicator of a number of threads N T  may be received. In an alternative embodiment, the fifth indicator may not be received. For example, a default value may be stored, for example, in computer-readable medium  108  and used automatically. In another alternative embodiment, the number of threads may not be selectable. Instead, a fixed, predefined value may be used or may be determined based on a number of processors of quantile computation device  100 . For illustration, a default value of the number of threads may be four. The number of threads may be available at each computing device of the number of computing nodes N N . For example, using Hadoop, input dataset  124  may be split across a plurality of computing devices and further split across a plurality of threads at each computing device. As an example, the fifth indicator may be received by quantile computation application  122  after selection from a user interface window, after entry by a user into a user interface window, by extracting the information from a request, by reading an input file, etc. 
     In an operation  210 , a sixth indicator of a maximum number of data structure nodes N X  may be received. In an alternative embodiment, the sixth indicator may not be received. For example, a default value may be stored, for example, in computer-readable medium  108  and used automatically. In another alternative embodiment, the maximum number of data structure nodes may not be selectable. Instead, a fixed, predefined value may be used or may be determined based on an available memory of quantile computation device  100 . For illustration, a default value for the maximum number of data structure nodes may be any value less than the amount of useable memory. As an example, the sixth indicator may be received by quantile computation application  122  after selection from a user interface window, after entry by a user into a user interface window, by extracting the information from a request, by reading an input file, etc. 
     In an operation  212 , a seventh indicator of a number of bins N B  may be received. In an alternative embodiment, the seventh indicator may not be received. For example, a default value may be stored, for example, in computer-readable medium  108  and used automatically. In another alternative embodiment, the number of bins may not be selectable. Instead, a fixed, predefined value may be used or may be determined based on an available memory of quantile computation device  100 . For illustration, a default value for the number of bins may be 10,000. As an example, the seventh indicator may be received by quantile computation application  122  after selection from a user interface window, after entry by a user into a user interface window, by extracting the information from a request, by reading an input file, etc. In an alternative embodiment, the same value may be used for both N X  and N B  so that only one value is indicated. 
     In an operation  213 , an eighth indicator of a memory size constraint value may be received. In an alternative embodiment, the eighth indicator may not be received. For example, a default value may be stored, for example, in computer-readable medium  108  and used automatically. In another alternative embodiment, the memory size constraint value may not be selectable. Instead, a fixed, predefined value may be used or may be determined based on an available memory of quantile computation device  100 . For illustration, a default value for the memory size constraint value may be determined based on an available memory. For example, if the data type is double, the memory size constraint value may be selected as the available memory in bytes divided by eight. The eighth indicator may be received by quantile computation application  122  after selection from a user interface window, after entry by a user into a user interface window, by extracting the information from a request, by reading an input file, etc. 
     In an operation  214 , a ninth indicator of a bin split ratio value R B  may be received that indicates a bin size of a bin that may be split into a plurality of bins when needed as described further below. In an alternative embodiment, the ninth indicator may not be received. For example, a default value may be stored, for example, in computer-readable medium  108  and used automatically. In another alternative embodiment, the bin split ratio value may not be selectable. Instead, a fixed, predefined value may be used. For illustration, a default value for the bin split ratio value may be 5% though other values may be used possibly based on memory constraints. As an example, the ninth indicator may be received by quantile computation application  122  after selection from a user interface window, after entry by a user into a user interface window, by extracting the information from a request, by reading an input file, etc. 
     In an operation  215 , a tenth indicator of a bin split numerical value N BS  may be received. In an alternative embodiment, the tenth indicator may not be received. For example, a default value may be stored, for example, in computer-readable medium  108  and used automatically. In another alternative embodiment, the bin split numerical value N BS  may not be selectable. Instead, a fixed, predefined value may be used. For illustration, a default value for the bin split numerical value N BS  may be 10,000 for input dataset  124  that includes from five to ten million observations. As an example, the tenth indicator may be received by quantile computation application  122  after selection from a user interface window, after entry by a user into a user interface window, by extracting the information from a request, by reading an input file, etc. 
     In an operation  216 , frequency data T xkn  for unique values of the variable X may be computed by each thread k of the number of threads N T  of each computing device n of the number of computing nodes N N  of distributed computing system  128 . Frequency data T xkn  may be computed in a variety of manners. Frequency data T xkn  may be stored as an array, a linked list, an AVL tree, a red-black tree, etc. In an illustrative embodiment, frequency data is stored using an ascending AVL tree. An AVL tree is a self-balancing binary search tree where a height of two child sub-trees of any node of the AVL tree differs by at most one. If at any time they differ by more than one, rebalancing is done to restore this property. Frequency data T xkn  stores each unique value of the variable x and a frequency value that indicates a number of occurrences of the associated unique value in ascending order relative to the unique value. For illustration, example operations for computing frequency data T xkn  are shown referring to  FIG. 3 . 
     In an operation  300 , a data structure T xkn  for frequency data, a unique value counter N U , and a counter flag are initialized. For example, for an array type data structure for frequency data, memory is allocated for the array and array values are initialized to zero; for an AVL tree type data structure for frequency data, an empty tree is initialized; etc. The unique value counter may be initialized to zero, and the counter flag may be initialized to zero or FALSE. 
     In an operation  302 , a variable value v for variable x and a frequency value for the variable value are read from input dataset  124 . 
     In an operation  304 , a determination is made concerning whether the unique value counter is less than the maximum number of data structure nodes N X . When the unique value counter is less than the maximum number of data structure nodes N X , processing continues in an operation  308 . When the unique value counter is not less than the maximum number of data structure nodes N X , processing continues in an operation  306 . 
     In operation  306 , the counter flag is set to one or TRUE, and processing continues in an operation  320  to indicate that the number of unique values of the variable x exceeds the maximum number of data structure nodes N X . 
     In operation  308 , a determination is made concerning whether the variable value exists in data structure T xkn . When the variable value exists in data structure T xkn , processing continues in an operation  310 . When the variable value does not exist in data structure T xkn , processing continues in an operation  312 . For example, the read variable value is compared to existing keys of data structure T xkn  that is an AVL tree to identify a matching key if it exists. 
     In operation  310 , a frequency value associated with the existing variable value is updated in data structure T xkn  by adding the read frequency value to the frequency value associated with the existing variable value, and processing continues in an operation  318 . 
     In operation  312 , the unique value counter is incremented by one to indicate that the read variable value is a new variable value. 
     In an operation  314 , a new entry is created and added to data structure T xkn . For example, a new AVL tree node is added in ascending order to data structure T xkn  using the read variable value as a key so that the variable values are maintained in sorted order in data structure T xkn . 
     In an operation  316 , a frequency value associated with the variable value key in data structure T xkn  is initialized with the read frequency value. 
     In operation  318 , a determination is made concerning whether the read variable value is a last variable value of input dataset  124 . When the read variable value is a last variable value, processing continues in operation  320 . When the read variable value is not a last variable value, processing continues in operation  302  to read and process the next variable value. 
     In operation  320 , processing to compute frequency data T xkn  for unique values of the variable x by the thread k and the computing node n is complete or is stopped, and control returns to the calling operation. When the number of threads N T  or the number of computing nodes N N  is greater than one, the computed frequency data T xkn  is returned to a controlling process and/or a controlling computing device. For example, quantile computation device  100  may be executing the controlling process and act as the controlling computing device. 
     Referring again to  FIG. 2A , in an operation  217 , a determination is made concerning whether the counter flag indicates true such that the number of unique values of the variable x exceeds the maximum number of data structure nodes N X . When the counter flag indicates true, processing continues in an operation  218 . When the counter flag indicates false, processing continues in an operation  234 . 
     Referring to  FIG. 2B , in operation  218 , a maximum value M xkn , a minimum value M nkn , and a total number of observations N okn  of the variable x may be computed by each thread k of the number of threads N T  of each computing device n of the number of computing nodes N N  of distributed computing system  128 . For illustration, example operations for the maximum value M xkn , the minimum value M nkn , and the total number of observations N okn  of the variable x are shown referring to  FIG. 4 . 
     In an operation  400 , a maximum value M xkn , a minimum value M ikn , and a total number of observations N okn  of the variable x are initialized. For example, the maximum value M xkn  is initialized to a maximum value included in frequency data T xkn , the minimum value M ikn  is initialized to a minimum value included in frequency data T xkn , and the total number of observations N okn  is initialized based on the frequency values stored in frequency data T xkn . Frequency data T xkn  can then be discarded because it is incomplete. 
     In an operation  402 , a variable value v for variable x and a frequency value for the variable value are read from input dataset  124 . On a first iteration of operation  402 , the line read in operation  302  that resulted in setting the counter flag to true in operation  306  may be processed instead of reading a next line from input dataset  124 . 
     In an operation  404 , the maximum value M xkn  may be updated with the read variable value if the read variable value is greater than the maximum value M xkn . 
     In an operation  406 , the minimum value M ikn  may be updated with the read variable value if the read variable value is less than the minimum value M ikn . 
     In an operation  408 , the total number of observations N okn  is updated by adding the read frequency value to the total number of observations N okn . 
     In an operation  410 , a determination is made concerning whether the read variable value is a last variable value of input dataset  124 . When the read variable value is a last variable value, processing continues in an operation  412 . When the read variable value is not a last variable value, processing continues in operation  402  to read and process the next variable value. 
     In operation  412 , processing to compute the maximum value M xkn , the minimum value M ikn , and the total number of observations N okn  of the variable x is complete, and control returns to the calling operation. 
     Referring again to  FIG. 2B , in an operation  220 , the maximum value M xkn , the minimum value M ikn , and the total number of observations N okn  of the variable x computed by each thread k of the number of threads N T  of each computing device n of the number of computing nodes N N  of distributed computing system  128  is merged to define a global maximum value M xg , a global minimum value M ig , and a global total number of observations N og  of the variable x for input dataset  124 . 
     In an operation  222 , upper and lower bounds are computed for each bin of the N B  bins indicated in operation  212 . For illustration, example operations for computing the upper and lower bounds are shown referring to  FIG. 5 . 
     In an operation  500 , a current bin number i and a bin size are initialized. For example, the current bin number is initialized to i=1, and the bin size is initialized to S=(M xg −M ig )/N B . 
     In an operation  502 , a lower bound LB for the current bin number i is computed as LB i =M ig +(i−1)*S, where LB may be an array storing N B  values. 
     In an operation  504 , an upper bound UB for the current bin number i is computed as UB i =LB i +S, where UB may be an array storing N B  values. 
     In an operation  506 , the current bin number i is incremented by one. 
     In an operation  508 , a determination is made concerning whether the current bin number i is greater than N B  such that all of the N B  bins have been processed. When i≤N B , processing continues in operation  502  to compute the bounds for the next bin. When i&gt;N B , processing continues in an operation  510 . 
     In operation  510 , processing to compute the upper and lower bounds for each bin of the N B  bins is complete, and control returns to the calling operation. 
     Referring again to  FIG. 2B , in operation  224 , a bin frequency counter F bkn  for each bin b of the N B  bins may be computed by each thread k of the number of threads N T  of each computing device n of the number of computing nodes N N  of distributed computing system  128 . For illustration, example operations for computing frequency counter F bkn  are shown referring to  FIG. 6 . 
     In an operation  600 , a current bin number i and each bin frequency counter F bkn  of the N B  bins are initialized. For example, the current bin number is initialized to i=1, and each bin frequency counter F bkn  of the N B  bins is initialized to zero, where F bkn  may be an array storing N B  values. 
     In an operation  602 , a variable value v for variable x and a frequency value for the variable value are read from input dataset  124 . 
     In an operation  604 , a determination is made concerning whether the read variable value is between the upper and the lower bound of the current bin based on LB i ≤v&lt;UB i . When the read variable value is between the upper and the lower bound, processing continues in an operation  608 . When the read variable value is not between the upper and the lower bound, processing continues in an operation  606 . 
     In operation  606 , the current bin number i is incremented by one, and processing continues in operation  604  to determine if the read variable value is within the next bin. 
     In operation  608 , the bin frequency counter F ikn  associated with the current bin number i is updated by adding the read frequency value to the bin frequency counter F ikn . 
     In an operation  610 , the current bin number is reinitialized to i=1. 
     In an operation  612 , a determination is made concerning whether the read variable value is a last variable value of input dataset  124 . When the read variable value is a last variable value, processing continues in an operation  614 . When the read variable value is not a last variable value, processing continues in operation  602  to read and process the next variable value. 
     In operation  614 , processing to compute the bin frequency counter F bkn  for each bin b of the N B  bins is complete, and control returns to the calling operation. 
     Referring again to  FIG. 2B , in an operation  226 , the bin frequency counter F bkn  for each bin b of the N B  bins computed by each thread k of the number of threads N T  of each computing device n of the number of computing nodes N N  of distributed computing system  128  is merged to define a global frequency counter F bg  for each bin b of the N B  bins for input dataset  124 . For example, the values computed by each thread k and each computing device n are added together for each bin b of the N B  bins to compute global frequency counter F bg  for each bin b of the N B  bins. F bg  may be an array storing N B  values. 
     In an operation  228 , a bin number W j  and a cumulative rank value R j  can be computed for each quantile, where j is a quantile index into the quantile set Q indicated in operation  204 . As a result, W j  and R j  store N Q  values. W j  and R j  may each be an array storing N Q  values though different types of data structures may be used. For illustration, example operations for computing bin number W j  and cumulative rank value R j  are shown referring to  FIG. 7 . 
     In an operation  700 , a current bin number i and a cumulative frequency counter CF b  of the N B  bins are initialized. For example, the current bin number is initialized to i=1, and each cumulative frequency counter CF b  of the N B  bins is initialized to zero, where CF b  may be an array storing N B  values. CF 0  may be initialized to zero. A zero th  entry of global frequency counter F bg  may be set to zero as F 0g =0. 
     In an operation  702 , a frequency value F ig  is selected from the computed global frequency counter F bg  as the value associated with the current bin number i. 
     In an operation  704 , a cumulative frequency counter CF i  for the current bin number i is computed as CF i =DF i-1 +F ig . 
     In an operation  706 , the current bin number i is incremented by one. 
     In an operation  708 , a determination is made concerning whether the current bin number i is greater than N B  such that all of the N B  bins have been processed. When i≤N B , processing continues in operation  702  to compute the cumulative frequency counter for the next bin. When i&gt;N B , processing continues in an operation  710 . 
     In operation  710 , the current bin number i, a current quantile counter j, a current quantile q, and a current quantile frequency QF are initialized. For example, the current bin number is reinitialized to i=1, the current quantile counter is initialized to j=1, the current quantile q is selected as a first entry from the quantile set Q as q=Q 1 , and the current quantile frequency is initialized to QF=q*N og . N og  is a total frequency count. For illustration, if q=10% and N og =100, QF=10 so that the tenth rank is the current quantile frequency QF. 
     In an operation  712 , a determination is made concerning whether the current quantile frequency QF is between the cumulative frequency counters bounding the current bin based on CF i-1 ≤QF&lt;CF i . When the current quantile frequency QF is between the cumulative frequency counter of the current bin, processing continues in an operation  716 . When the current quantile frequency QF is not between the cumulative frequency counter of the current bin, processing continues in an operation  714 . 
     In operation  714 , the current bin number i is incremented by one, and processing continues in operation  712  to determine if the current quantile frequency QF is within the cumulative frequency counters bounding the next bin. 
     In operation  716 , the current bin number i is stored in bin number array W j =i in association with the current quantile counter j. For example, j is used as an index into W j  stored as an array. 
     In an operation  718 , a cumulative rank value r for the current quantile counter j is computed using r=(QF−CF i-1 )+F (i-1)g , and stored in cumulative rank value array R j =r in association with the current quantile counter j. For example, j is used as an index into R j  stored as an array. 
     In an operation  720 , the current quantile counter j is incremented by one. 
     In an operation  722 , a determination is made concerning whether the current quantile counter j is greater than N Q  such that all of the N Q  quantiles of the quantile set Q have been processed. When j≤N Q , processing continues in an operation  724 . When j&gt;N Q , processing continues in an operation  728 . 
     In operation  724 , the current bin number is reinitialized to i=1. 
     In an operation  726 , the current quantile q is selected as a j th  entry from the quantile set Q as q=Q j , the current quantile frequency is updated to QF=q*N og , and processing continues in operation  712  to identify the bin within which the current quantile frequency is located. 
     In operation  728 , processing to compute the bin number array W j  and the cumulative rank value array R j  for each quantile j of the N Q  quantiles of the quantile set Q is complete, and control returns to the calling operation. 
     Referring again to  FIG. 2B , in an operation  230 , a memory size is estimated for frequency data T bkn  to be created in an operation  234  using the frequency value included in the bin frequency counter F bkn  for each bin number b included in bin number array W j  that lists all of the bin numbers that include requested quantiles. The memory size is estimated by adding up the bin frequency counter F bkn  value for each bin number b included in bin number array W j  and optionally multiplying the added value by a memory used to store information for each entry in frequency data T bkn . Whether the added value is multiplied by a memory used to store information for each entry in frequency data T bkn  may be based on how the memory size constraint value indicated in operation  213  is defined as in whether it is based on the total count or a total memory usage considering a size of the data stored. 
     In an operation  232 , a determination is made concerning whether the estimated memory size is greater than the memory size constraint value indicated in operation  213 . When the estimated memory size is greater than the memory size constraint value, processing continues in an operation  238 . When the estimated memory size is not greater than the memory size constraint value, processing continues in operation  234 . When the estimated memory size is greater than the memory size constraint value, operations  238  to  248  increase the number of bins by splitting one or more of the bins into additional bins. Once the processing is complete, the total bin frequency counter F bkn  value updated in operation  244  for each bin number b included in the bin number array W j  updated in operation  246  is much smaller. As a result, frequency data T bkn  to be created in operation  234  uses less memory. 
     In operation  234 , frequency data T bkn  for each number of x values in the bin defined for each quantile q may be computed by each thread k of the number of threads N T  of each computing device n of the number of computing nodes N N  of distributed computing system  128 . Frequency data T bkn  may be computed in a variety of manners. For illustration, example operations for computing frequency data T bkn  are shown referring to  FIG. 8 . 
     In an operation  800 , a data structure T bkn  for the frequency data, a current bin index j, and a current bin number i are initialized. For example, a current bin index is initialized to j=1 and is used to index into the bin number W j . For example, for an array type data structure for frequency data, memory is allocated for the array and array values are initialized to zero; for an AVL tree type data structure for frequency data, an empty tree is initialized; etc. The current bin number i is selected as a first entry from bin number W j  as i=W 1 . 
     In an operation  802 , a variable value v for variable x and a frequency value for the variable value are read from input dataset  124 . 
     In an operation  804 , a determination is made concerning whether the read variable value is between the upper bound and the lower bound of the current bin number selected from bin number W j  based on LB i ≤v&lt;UB i . When the read variable value is between the upper and the lower bounds, processing continues in an operation  808 . When the read variable value is not between the upper and the lower bounds, processing continues in an operation  806 . 
     In operation  806 , the current bin index j is incremented by one, and processing continues in an operation  820 . 
     In operation  808 , a determination is made concerning whether the variable value exists in data structure T bkn . When the variable value exists in data structure T bkn , processing continues in an operation  810 . When the variable value does not exist in data structure T xkn , processing continues in an operation  812 . For example, the read variable value is compared to existing keys of data structure T bkn  to identify a matching key if it exists. 
     In operation  810 , a frequency value associated with the existing variable value is updated in data structure T bkn  by adding the read frequency value to the frequency value associated with the existing variable value, and processing continues in an operation  816 . 
     In operation  812 , a new entry is created and added to data structure T bkn . For example, a new AVL tree node is added in ascending order to data structure T bkn  using the read variable value as a key so that the variable values are maintained in sorted order in data structure T bkn . 
     In an operation  814 , a frequency associated with the variable value key in data structure T bkn  is initialized with the read frequency value. 
     In operation  816 , a determination is made concerning whether the read variable value is a last variable value of input dataset  124 . When the read variable value is a last variable value, processing continues in an operation  818 . When the read variable value is not a last variable value, processing continues in operation  802  to read and process the next variable value. 
     In operation  818 , processing to compute the frequency data T bkn  for each bin k of the bin number array W k , is complete, and control returns to the calling operation. 
     In operation  820 , a determination is made concerning whether the current bin index j is greater than N Q  such that each bin j of the bin number array W j  has been processed. When j≤N Q , processing continues in an operation  822 . When j&gt;N Q , processing continues in an operation  824 . 
     In an operation  822 , the current bin number i is selected as the j th  entry from the bin number as i=W j , and processing continues in operation  804  to determine if the read variable value is within the next bin of bin number W j . 
     In operation  824 , the current bin index is reinitialized to j=1, and the current bin number i is selected as a first entry from bin number W j  as i=W 1 , and processing continues in operation  816  to process the next variable value, if any. 
     Referring again to  FIG. 2B , in operation  236 , frequency data T bkn  computed by each thread of the number of threads N T  of each computing device of the number of computing nodes N N  of distributed computing system  128  is merged to define frequency data T bg  on quantile computation device  100  that stores global frequency data for input dataset  124 . Processing continues in an operation  254 . 
     In operation  238 , a subset of the N B  bins to split into the bin split numerical value of bins is selected. For illustration, example operations for selecting the subset of the N B  bins are shown referring to  FIG. 10 . 
     Referring to  FIG. 10 , in an operation  1000 , a current bin number i is initialized. For example, the current bin number is initialized to i=1. 
     In an operation  1002 , a bin size ratio for the current bin number i is computed as R i =F ig /N og , where F ig  is the global frequency counter value from F bg  for the current bin number i, and N og  is the total frequency count. 
     In an operation  1004 , a determination is made concerning whether the computed bin size ratio R i  is greater than the bin split ratio value R B  indicated in operation  214 . When R i &gt;R B , processing continues in an operation  1006 . When R i ≤R B , processing continues in an operation  1008 . 
     In operation  1006 , the current bin number i is added to the bins to be split BS. For example, the current bin number i may be added to BS that is a list, an array, etc. and includes a number of bins to split N ToSplit . 
     In operation  1008 , the current bin number i is incremented by one. 
     In an operation  1010 , a determination is made concerning whether the current bin number i is greater than N B  such that all of the N B  bins have been processed. When i≤N B , processing continues in operation  1002  to compute the bin size ratio and determine whether the next bin is to be split into the bin split numerical value N BS  of new bins. When i&gt;N B , processing continues in an operation  1012 . 
     In operation  1012 , processing to determine the bins to be split BS is complete, and control returns to the calling operation. The bins to be split BS includes the number of bins to split N ToSplit  each of which will be split into the bin split numerical value N BS  of new bins. 
     Referring again to  FIG. 2B , in operation  240 , upper and lower bounds for each of the new bins to be created are computed. The number of new bins N NewB  to create is N NewB =N ToSplit *N BS . For illustration, example operations for computing the upper and lower bounds are shown referring to  FIG. 11 . 
     Referring to  FIG. 11 , in an operation  1100 , a next bin number j is selected from the bins to be split BS. For example, on a first iteration of operation  1100 , a first bin number entry in the bins to be split BS is selected; on a second iteration of operation  1100 , a second bin number entry in the bins to be split BS is selected; . . . ; and on an N ToSplit  iteration of operation  1100 , a last bin number entry in the bins to be split BS is selected. 
     In an operation  1102 , a current sub-bin number i and a bin size for the current bin number j are initialized. For example, the current sub-bin number is initialized to i=1, and the bin size is initialized to S=(UB j −LB j )/N BS . 
     In an operation  1104 , a lower bound LB for the current sub-bin number i of the next bin number j is computed as LB ji =LB j +(i−1)*S, where LB ji  may be a two-dimensional array storing N BS  by N ToSplit  values where an iteration number of operation  1100  may be used as an index that may also be mapped to the associated next bin number j. 
     In an operation  1106 , an upper bound UB for the current sub-bin number i of the next bin number j is computed as UB ji =LB ji +S, where UB ji  may be a two-dimensional array storing N BS  by N ToSplit  values where an iteration number of operation  1100  may be used as an index that may also be mapped to the associated next bin number j. 
     In an operation  1108 , the current sub-bin number i is incremented by one. 
     In an operation  1110 , a determination is made concerning whether the current sub-bin number i is greater than N BS  such that all of the N BS  bins have been processed. When i≤N BS , processing continues in operation  1104  to compute the bounds for the next sub-bin. When i&gt;N BS , processing continues in an operation  1112 . 
     In operation  1112 , a determination is made concerning whether the bins to be split BS includes another bin to split. For example, after N ToSplit  iterations of operation  1100 , all of the bins included in the bins to be split BS have been processed. When the bins to be split BS includes another bin to split, processing continues in operation  1100  to select the next bin to be split. When bins to be split BS does not include another bin to split, processing continues in an operation  1114 . 
     In operation  1114 , processing to compute the upper and lower bounds for each of the N NewB  new bins to be created is complete, and control returns to the calling operation. 
     Referring again to  FIG. 2B , in operation  242 , a bin frequency counter F bskn  for each sub-bin s of the bin split numerical value N BS  of each of the bins b to be split of the number of bins to be split N ToSplit  may be computed by each thread k of the number of threads N T  of each computing device n of the number of computing nodes N N  of distributed computing system  128 . For illustration, example operations for computing frequency counter F bskn  are shown referring to  FIG. 12 . 
     Similar to operation  1100  and referring to  FIG. 12 , in an operation  1200 , a first bin number is selected from the bins to be split BS as the next bin number j. 
     In an operation  1202 , a current sub-bin number i and each sub-bin frequency counter F bskn  of each sub-bin s of the bin split numerical value N BS  of new bins for next bin number j are initialized. For example, the current sub-bin number is initialized to i=1, and each bin frequency counter F bskn  of the bin split numerical value N BS  of new bins for next bin number j is initialized to zero, where F jskn  may be an array storing N NewB  values. 
     In an operation  1204 , a variable value v for variable x and a frequency value for the variable value are read from input dataset  124 . 
     In an operation  1206 , a determination is made concerning whether the read variable value is between the upper and the lower bound of the sub-bin number i and the next bin number j based on LB ji ≤v≤UB ji . When the read variable value is between the upper and the lower bound, processing continues in an operation  1208 . When the read variable value is not between the upper and the lower bound, processing continues in an operation  1210 . 
     In operation  1208 , the sub-bin frequency counter F jikn  associated with the current sub-bin number i and the next bin number j is updated by adding the read frequency value to the sub-bin frequency counter F jikn , and processing continues in an operation  1220 . 
     In operation  1210 , the current sub-bin number i is incremented by one. 
     In an operation  1212 , a determination is made concerning whether the current sub-bin number i is greater than N BS  such that all of the N BS  bins have been processed. When i≤N BS , processing continues in operation  1206  to determine if the read value is within the next sub-bin. When i&gt;N BS , processing continues in an operation  1214 . 
     In operation  1214 , a determination is made concerning whether the current bin number j is greater than N B  such that all of the N B  bins have been processed. When j≤N B , processing continues in operation  1216  to select the next bin. When j&gt;N B , processing continues in operation  1220 . 
     In operation  1216 , a next bin number j is selected from the bins to be split BS. 
     In an operation  1218 , the current sub-bin number i is reinitialized. For example, the current sub-bin number is reinitialized to i=1, and processing continues in operation  1206  to determine if the read variable value is within the next sub-bin. 
     In operation  1220 , the current sub-bin number is reinitialized to i=1 and the first bin number is selected from the bins to be split BS as the next bin number j. 
     In an operation  1222 , a determination is made concerning whether the read variable value is a last variable value of input dataset  124 . When the read variable value is a last variable value, processing continues in an operation  1224 . When the read variable value is not a last variable value, processing continues in operation  1204  to read and process the next variable value. 
     In operation  1224 , processing to compute the bin frequency counter F bskn  for each sub-bin s of the bin split numerical value N BS  of new bins and each of the bins b to be split BS of the number of bins to be split N ToSplit  is complete, and control returns to the calling operation. 
     Referring again to  FIG. 2B , in operation  244 , the bin frequency counter F bskn  for each sub-bin s of the bin split numerical value N BS  of new bins and each of the bins b to be split BS of the number of bins to be split N ToSplit  computed by each thread k of the number of threads N T  of each computing device n of the number of computing nodes N N  of distributed computing system  128  is merged to define a global frequency counter F bsg  for each sub-bin s of each of the bins b to be split BS. For example, the values computed by each thread k and each computing device n are added together for each sub-bin s of each of the bins b to be split BS to compute global frequency counter F bsg ·F bsg  may be an array storing N NewB  values. 
     In an operation  246 , a bin number W j  and a cumulative rank value R j  can be computed for each quantile, where j is a quantile index into the quantile set Q indicated in operation  204 . As a result, W j  and R j  store N Q  values. W j  and R j  may each be an array storing N Q  values though different types of data structures may be used. For illustration, example operations for computing bin number W j  and cumulative rank value R j  are shown referring to  FIGS. 13A to 13C . 
     Referring to  FIG. 13A , in an operation  1300 , a current bin number j and a cumulative frequency counter CF b  of the N B  bins plus the N NewB  new bins are initialized. For example, the current bin number is initialized to j=1, and each cumulative frequency counter CF b  of the N B  bins plus the N NewB  new bins is initialized to zero, where CF b  may be an array storing N B +N NewB  values. CF 0  may be initialized to zero. A zero th  entry of global frequency counter F bg  may be set to zero as F 0g =0. Because each bin of the number of bins to be split N ToSplit  is replaced with the bin split numerical value N BS  of new bins, the number of bins is now N B =N B −N ToSplit +N NewB . 
     In an operation  1302 , a determination is made concerning whether the current bin number j is included in the bins to be split BS. When the current bin number j is included in the bins to be split BS, processing continues in an operation  1312 . When the current bin number j is not included in the bins to be split BS, processing continues in an operation  1304 . 
     In operation  1304 , a frequency value F jg  is selected from the computed global frequency counter F bg  as the value associated with the current bin number j. 
     In an operation  1306 , a cumulative frequency counter CF j  for the current bin number j is computed as CF j =CF j-1 +F jg . 
     In an operation  1308 , the current bin number j is incremented by one. 
     In an operation  1310 , a determination is made concerning whether the current bin number j is greater than N B  such that all of the N B  bins have been processed. When j≤N B , processing continues in operation  1302  to compute the cumulative frequency counter for the next bin. When j&gt;N B , processing continues in an operation  1322  shown referring to  FIG. 13B . 
     In operation  1312 , a current sub-bin number i is initialized. For example, the current sub-bin number is initialized to i=1. 
     In operation  1314 , a frequency value F jig  is selected from the computed global frequency counter F bsg  as the value associated with the current sub-bin number i of the current bin number j. 
     In an operation  1316 , a cumulative frequency counter CF ji  for the current sub-bin number i of the current bin number j is computed as CF ji =CF ji-1 +F jig . 
     In an operation  1318 , the current sub-bin number i is incremented by one. 
     In an operation  1320 , a determination is made concerning whether the current sub-bin number i is greater than N BS  such that all of the N BS  bins have been processed. When i≤N BS , processing continues in operation  1314  to compute the cumulative frequency counter CF ji  for the next sub-bin of the current bin number j. When i&gt;N BS , processing continues in operation  1308 . 
     Referring to  FIG. 13B , in operation  1322 , a current bin number m, a current quantile counter j, a current quantile q, a current quantile frequency QF, and a current frequency sum Y are initialized. For example, the current bin number is initialized to m=1, the current quantile counter is initialized to j=1, the current quantile q is selected as a first entry from the quantile set Q as q=Q 1 , the current quantile frequency is initialized to QF=q*N og , and the current frequency sum Y is initialized to Y=0. N og  is a total frequency count. For illustration, if q=10% and N og =100, QF=10 so that the tenth rank is the current quantile frequency QF. 
     In an operation  1324 , a determination is made concerning whether the current bin number m is included in the bins to be split BS. When the current bin number m is included in the bins to be split BS, processing continues in an operation  1346  shown referring to  FIG. 13C . When the current bin number m is not included in the bins to be split BS, processing continues in an operation  1326 . 
     In operation  1326 , a determination is made concerning whether the current quantile frequency QF is between the cumulative frequency counters bounding the current bin based on CF m-1 ≤QF&lt;CF m . When the current quantile frequency QF is between the cumulative frequency counter of the current bin, processing continues in an operation  1330 . When the current quantile frequency QF is not between the cumulative frequency counter of the current bin, processing continues in an operation  1328 . 
     In operation  1328 , the current bin number m is incremented by one, and processing continues in operation  1324  to determine if the current quantile frequency QF is within the cumulative frequency counters bounding the next bin. 
     In operation  1330 , the current bin number m is stored in bin number array W j =m in association with the current quantile counter j. For example, j is used as an index into W j  stored as an array. 
     In an operation  1332 , a cumulative rank value r for the current quantile counter j is computed using r=(QF−CF m-1 )+F (m-1)g , and stored in cumulative rank value array R j =r in association with the current quantile counter j. For example, j is used as an index into R j  stored as an array. 
     In an operation  1334 , the current quantile counter j is incremented by one. 
     In an operation  1336 , the current frequency sum Y is updated using Y=Y+F mg . 
     In an operation  1338 , a determination is made concerning whether the current quantile counter j is greater than N Q  such that all of the N Q  quantiles of the quantile set Q have been processed. When j≤N Q , processing continues in an operation  1342 . When j&gt;N Q , processing continues in an operation  1340 . 
     In operation  1340 , processing to compute the bin number W j  and the cumulative rank value R j  for each quantile j of the N Q  quantiles of the quantile set Q is complete, and control returns to the calling operation. 
     In operation  1342 , the current bin number is reinitialized to m=1. 
     In an operation  1344 , the current quantile q is selected as a j th  entry from the quantile set Q as q=Q j , the current quantile frequency is updated to QF=q*N og , and processing continues in operation  1324  to identify the bin within which the current quantile frequency is located. 
     Referring to  FIG. 13C , in operation  1346 , the current sub-bin number i is initialized to one. 
     In operation  1348 , a determination is made concerning whether the current quantile frequency QF is between the cumulative frequency counters bounding the current sub-bin number i of the current bin number m based on CF mi-1 ≤QF&lt;CF mi . When the current quantile frequency QF is between the cumulative frequency counter of the current sub-bin, processing continues in an operation  1356 . When the current quantile frequency QF is not between the cumulative frequency counter of the current sub-bin, processing continues in an operation  1350 . 
     In an operation  1350 , the current sub-bin number i is incremented by one. 
     In an operation  1352 , a determination is made concerning whether the current sub-bin number i is greater than N BS  such that all of the N BS  bins have been processed. When i≤N BS , processing continues in operation  1348  to evaluate the bounds of the next sub-bin of the current bin number m. When i&gt;N BS , processing continues in an operation  1354 . 
     In operation  1354 , the current bin number m is incremented by one, and processing continues in operation  1324  to determine if the current quantile frequency QF is within the cumulative frequency counters bounding the next bin. 
     In operation  1356 , the current bin number m and the current sub-bin number i are stored in bin number array W j =mi in association with the current quantile counter j. For example, j is used as an index into W j  stored as an array that indicates the two current indices m and i. 
     In an operation  1358 , a cumulative rank value r for the current quantile counter j is computed using r=(QF−CF mi-1 )+F (mi-1)g , and stored in cumulative rank value array R j =r in association with the current quantile counter j. For example, j is used as an index into R j  stored as an array. 
     In an operation  1360 , the current quantile counter j is incremented by one. 
     In an operation  1362 , the current frequency sum Y is updated using Y=Y+F mig , and processing continues in operation  1338 . 
     Referring again to  FIG. 2B , in an operation  248 , the estimated memory size is updated, and processing continues in operation  232 . The updated memory size is estimated for frequency data T bkn  to be created in an operation  234  using the frequency value included in the bin frequency counter F bkn  updated in operation  244  for each bin number b included in bin number W j  updated in operation  246  that includes all of the bin numbers that include requested quantiles. The estimated memory size is updated by adding up the updated bin frequency counter F bkn  for each bin number b included in updated bin number W j  and optionally multiplying the added value by a memory used to store information for each entry in frequency data T bkn . 
     Referring again to  FIG. 2A , in operation  250 , frequency data T xkn  computed by each thread of the number of threads N T  of each computing device of the number of computing nodes N N  of distributed computing system  128  is merged to define frequency data T xg  on quantile computation device  100  that stores global frequency data for input dataset  124 . The global total number of observations N og  of the variable x is also computed. 
     In an operation  252 , a cumulative rank value R j  for each quantile j of the N Q  quantiles of the quantile set Q indicated in operation  204  is computed. For illustration, the quantiles and the computed cumulative rank value may be stored as arrays with values accessed using the same index. A rank indicates a numerical order of a respective value of the variable x. The cumulative rank value R j  can be computed for each j th  quantile using R j =Q j /N og , where the j th  quantile Q j  is selected as a j th  entry from the quantile set Q. 
     In operation  254 , a quantile value is computed for each quantile of the N Q  quantiles of the quantile set Q indicated in operation  204  using the computed frequency data. The quantile value is the value of the variable x associated with the quantile. When performed after operation  252 , the frequency data is T xg  that includes values for each unique value of the variable x; whereas, when performed after operation  236 , the frequency data is T bg  that includes values for each number of x values in the bin defined for each quantile q. As a result, frequency data T bg  is much smaller in size than frequency data T xg  when N U ≥N X  and is much faster to process to compute the quantile value for each quantile. 
     For illustration, example operations for computing each quantile value from the frequency data T xg  or T bg  and from the cumulative rank value R j  for each quantile of the N Q  quantiles of the quantile set Q are shown referring to  FIG. 9 . 
     In an operation  900 , a current quantile counter j, and a cumulative frequency counter C are initialized. For example, the current quantile counter is initialized to j=1, and the cumulative frequency counter is initialized to C=0. 
     In an operation  902 , a first data structure node is selected from either the frequency data T xg  or T bg  as a current data structure node. For example, for an array type data structure for frequency data, a first node is an index equal to one; for an AVL tree type data structure for frequency data, a first node pointer is retrieved from the tree; etc. 
     In an operation  904 , a current rank value r is selected from the cumulative rank value R j  using the current quantile counter j as r=R j . 
     In an operation  906 , the cumulative frequency counter C is updated by adding the frequency value stored in association with the current data structure node to the current value of the cumulative frequency counter C+=FV, where FV is the frequency value stored in association with the current data structure node. 
     In an operation  908 , a determination is made concerning whether the cumulative frequency counter C is equal to the current rank value r based on C=r. When C=r, processing continues in an operation  912 . When C≠r, processing continues in an operation  910 . 
     In operation  910 , the current data structure node is updated to a next data structure node, and processing continues in operation  906 . For example, for an array type data structure for frequency data, a next node is determined by incrementing the index; for an AVL tree type data structure for frequency data, a next node pointer is retrieved from the tree; etc. 
     In operation  912 , a quantile value Z j  for the current quantile counter j is selected as the key value associated with the current data structure node. As a result, Z j  stores N Q  values. Z j  may be an array storing N Q  values though different types of data structures may be used. 
     In an operation  914 , a determination is made concerning whether the current quantile counter j is greater than N Q  such that all of the N Q  quantiles of the quantile set Q have been processed. When j≤N Q , processing continues in an operation  916 . When j&gt;N Q , processing continues in an operation  918 . 
     In operation  916 , the current quantile counter j is incremented by one, and processing continues in operation  904 . 
     In operation  918 , processing to compute each quantile value Z j  for each quantile of the N Q  quantiles of the quantile set Q is complete, and control returns to the calling operation. 
     Referring again to  FIG. 2A , in an operation  256 , the quantile value(s) Z j  computed for each quantile of the N Q  quantiles of the quantile set Q indicated in operation  204  may be output to quantile values  126  stored on computer-readable medium  108  or another computer-readable medium of distributed computing system  128 . The associated quantile of the N Q  quantiles of the quantile set Q may also be output. In addition, or in the alternative, quantile values  126  may be presented on display  116 , for example, graphically in a histogram or a table, printed on printer  120 , sent to another computing device using communication interface  106 , etc. In addition, or in the alternative, quantile values  126  may be returned to a calling function that requested computation of the one or more quantiles of the quantile set Q that may be executing on quantile computation device  100  or another computing device of distributed computing system  128 . Processing by quantile computation application  122  is either done or process control returns to the calling function. 
     For comparison, quantile computation application  122  was compared to two existing actions implemented in SAS Viya 3.2: 1) a “percentile” action that implements an iterative algorithm as described in United States Patent Publication Number 20130325825 assigned to the assignee of the present application, and 2) an “aggregate” action that implements a sorting-based algorithm. 
     To test the performance, input dataset  124  with 1 million, 10 million, and 20 million rows was generated and the three methods were executed using a symmetric multi-processing mode on quantile computation device  100  as a single computing device with N X =N B =10000 and N N =1. Quantile computation device  100  included eight core processors, a 2699 megahertz processor speed, and 252 gigabytes of RAM. Input dataset  124  included variable values computed using a uniform distribution with a minimum value of zero and a maximum value of 100. Table I shows run time comparisons between each of the three methods with different dataset sizes and number of threads. 
     
       
         
           
               
               
               
               
             
               
                   
                 TABLE I 
               
             
            
               
                   
                   
               
               
                   
                   
                   
                 Run Time (seconds) 
               
            
           
           
               
               
               
               
               
               
            
               
                   
                   
                   
                 Quantile 
                   
                   
               
               
                   
                   
                   
                 computation 
                 Percentile 
                 Aggregate 
               
               
                   
                 Input 
                   
                 application 
                 Action, SAS 
                 Action, SAS 
               
               
                   
                 dataset 124 
                 N T   
                 122 
                 Viya 3.2 
                 Viya 3.2 
               
               
                   
                   
               
            
           
           
               
               
               
               
               
               
            
               
                   
                 1 million 
                 1 
                 0.55 
                 0.79 
                 3.71 
               
               
                   
                 rows 
                 5 
                 0.22 
                 0.18 
                 2.51 
               
               
                   
                   
                 10 
                 0.13 
                 0.11 
                 1.98 
               
               
                   
                   
                 15 
                 0.13 
                 0.15 
                 2.06 
               
               
                   
                   
                 20 
                 0.10 
                 0.12 
                 2.22 
               
               
                   
                   
                 25 
                 0.09 
                 0.12 
                 2.39 
               
               
                   
                   
                 30 
                 0.08 
                 0.12 
                 2.43 
               
               
                   
                 10 million 
                 1 
                 5.45 
                 8.34 
                 55.98 
               
               
                   
                 rows 
                 5 
                 1.89 
                 1.71 
                 31.18 
               
               
                   
                   
                 10 
                 1.69 
                 0.98 
                 21.71 
               
               
                   
                   
                 15 
                 1.50 
                 0.66 
                 33.74 
               
               
                   
                   
                 20 
                 1.00 
                 0.61 
                 33.35 
               
               
                   
                   
                 25 
                 1.01 
                 0.66 
                 34.41 
               
               
                   
                   
                 30 
                 0.77 
                 0.77 
                 28.69 
               
               
                   
                 20 million 
                 1 
                 10.93 
                 15.42 
                 90.90 
               
               
                   
                 rows 
                 5 
                 4.47 
                 3.41 
                 71.10 
               
               
                   
                   
                 10 
                 3.12 
                 1.80 
                 52.14 
               
               
                   
                   
                 15 
                 1.42 
                 1.31 
                 55.69 
               
               
                   
                   
                 20 
                 2.40 
                 1.20 
                 56.61 
               
               
                   
                   
                 25 
                 1.23 
                 0.95 
                 71.60 
               
               
                   
                   
                 30 
                 1.47 
                 0.95 
                 73.30 
               
               
                   
                   
               
            
           
         
       
     
     Another input dataset  124  was also generated with variable values computed using a normal distribution with a mean value of zero and a standard deviation value of 100. Table II shows run time comparisons between each of the three methods with different dataset sizes and number of threads. 
     
       
         
           
               
               
               
             
               
                 TABLE II 
               
             
            
               
                   
               
               
                   
                   
                 Run Time (seconds) 
               
            
           
           
               
               
               
               
               
            
               
                   
                   
                 Quantile 
                   
                   
               
               
                   
                   
                 computation 
                 Percentile 
                 Aggregate 
               
               
                 Input dataset 
                   
                 application 
                 Action, SAS 
                 Action, SAS 
               
               
                 124 
                 N T   
                 122 
                 Viya 3.2 
                 Viya 3.2 
               
               
                   
               
            
           
           
               
               
               
               
               
            
               
                 1 million  
                 1 
                 0.56 
                 1.01 
                 3.46 
               
               
                 rows 
                 5 
                 0.20 
                 0.21 
                 3.30 
               
               
                   
                 10 
                 0.17 
                 0.11 
                 3.17 
               
               
                   
                 15 
                 0.12 
                 0.08 
                 3.20 
               
               
                   
                 20 
                 0.12 
                 0.07 
                 3.28 
               
               
                   
                 25 
                 0.10 
                 0.07 
                 3.43 
               
               
                   
                 30 
                 0.08 
                 0.09 
                 3.52 
               
               
                 10 million 
                 1 
                 5.64 
                 11.62 
                 40.08 
               
               
                 rows 
                 5 
                 2.01 
                 2.35 
                 33.09 
               
               
                   
                 10 
                 1.70 
                 1.23 
                 32.63 
               
               
                   
                 15 
                 1.46 
                 0.86 
                 35.67 
               
               
                   
                 20 
                 1.25 
                 0.69 
                 35.29 
               
               
                   
                 25 
                 0.93 
                 0.60 
                 34.98 
               
               
                   
                 30 
                 0.77 
                 0.67 
                 36.76 
               
               
                 20 million 
                 1 
                 11.27 
                 20.24 
                 89.29 
               
               
                 rows 
                 5 
                 4.14 
                 4.08 
                 67.90 
               
               
                   
                 10 
                 3.42 
                 2.05 
                 67.88 
               
               
                   
                 15 
                 3.02 
                 1.53 
                 68.97 
               
               
                   
                 20 
                 2.55 
                 1.18 
                 67.85 
               
               
                   
                 25 
                 1.99 
                 1.03 
                 70.74 
               
               
                   
                 30 
                 1.36 
                 1.00 
                 75.21 
               
               
                   
               
            
           
         
       
     
     Quantile computation application  122  achieves significantly faster computations times in comparison to the aggregate action provided by SAS Viya 3.2, which both provide an exact result without the need to specify stopping criteria such as the maximal number of iterations and convergence tolerance. 
     Though the percentile action provided by SAS Viya 3.2 sometimes provided faster results than quantile computation application  122 , the percentile action does not guarantee an exact solution and requires specification of stopping criteria such as a maximum number of iterations and a convergence tolerance. For example, Table III shows two examples of a convergence status generated using the percentile action with different settings for the maximum number of iterations (Maxiters) and the convergence tolerance (Tolerance) used to stop execution of the iterative algorithm. The first dataset “Arrest prediction” used a neural network prediction of arrest using a Chicago arrest dataset, and the second dataset “Age group prediction” used a logistics regression prediction of age group using a dataset named CAMPNRML. 
     
       
         
           
               
               
               
               
               
             
               
                 TABLE III 
               
               
                   
               
               
                   
                   
                   
                   
                 Converge 
               
               
                 Dataset 
                 Variable 
                 Maxiters 
                 Tolerance 
                 (Y/N) 
               
               
                   
               
             
            
               
                 Arrest 
                 P_arrest 
                 10 
                 1.00E−05 
                 N 
               
               
                 prediction 
                   
                 20 
                 1.00E−05 
                 N 
               
               
                   
                   
                 30 
                 1.00E−05 
                 N 
               
               
                   
                   
                 40 
                 1.00E−05 
                 N 
               
               
                   
                   
                 50 
                 1.00E−05 
                 Y 
               
               
                   
                   
                 10 
                 1.00E−06 
                 N 
               
               
                   
                   
                 20 
                 1.00E−06 
                 N 
               
               
                   
                   
                 30 
                 1.00E−06 
                 N 
               
               
                   
                   
                 40 
                 1.00E−06 
                 N 
               
               
                   
                   
                 50 
                 1.00E−06 
                 Y 
               
               
                 Age group 
                 P_va_d_Age_Group_21 
                 10 
                 1.00E-05 
                 N 
               
               
                 prediction 
                   
                 20 
                 1.00E−05 
                 N 
               
               
                   
                   
                 30 
                 1.00E−05 
                 N 
               
               
                   
                   
                 40 
                 1.00E−05 
                 N 
               
               
                   
                   
                 50 
                 1.00E−05 
                 N 
               
               
                   
                   
                 60 
                 1.00E−05 
                 N 
               
               
                   
                   
                 70 
                 1.00E−05 
                 Y 
               
               
                   
                   
                 10 
                 1.00E−06 
                 N 
               
               
                   
                   
                 20 
                 1.00E−06 
                 N 
               
               
                   
                   
                 30 
                 1.00E−06 
                 N 
               
               
                   
                   
                 40 
                 1.00E−06 
                 N 
               
               
                   
                   
                 50 
                 1.00E−06 
                 N 
               
               
                   
                   
                 60 
                 1.00E−06 
                 N 
               
               
                   
                   
                 70 
                 1.00E−06 
                 Y 
               
               
                   
               
            
           
         
       
     
     As shown in Table III, the percentile action cannot converge in many cases before hitting the stop criterion. For convergence, the user must specify appropriate values for the maximum number of iterations (Maxiters) and the convergence tolerance (Tolerance) using trial and error, which requires additional computing time and user analysis time that is not captured in Tables I and II. 
     Quantile computation application  122  provides an efficient and exact method to locate quantiles in at most three passes through input dataset  124  that may be distributed or classified as “big data” due to the large number of values of the variable. Quantile computation application  122  avoids non-convergence situations that may occur using the iterative algorithm (the percentile action) and does not need expensive sorting that may occur using the sorting-based algorithm (the aggregate action). 
     Quantile computation application  122  further evaluates whether memory is an issue. When memory is not an issue, quantile computation application  122  provides an efficient and exact method to locate quantiles in input dataset  124  with at most three passes through input dataset  124 . When memory is an issue, quantile computation application  122  applies additional steps that result in use of much less memory when the data in input dataset  124  is highly-skewed or highly-concentrated resulting in much better performance. Therefore, quantile computation application  122  is an improvement to existing processes performed by computing devices in solving the technical problem of computing quantiles from a dataset. Quantile computation application  122  does not require a stopping criterion such as a number of iterations or a convergence tolerance for which values may be difficult to define. Quantile computation application  122  also computes an exact quantile for any distributed or big data with comparable or significantly less computational cost compared with existing methods. 
     The word “illustrative” is used herein to mean serving as an example, instance, or illustration. Any aspect or design described herein as “illustrative” is not necessarily to be construed as preferred or advantageous over other aspects or designs. Further, for the purposes of this disclosure and unless otherwise specified, “a” or “an” means “one or more”. Still further, using “and” or “or” in the detailed description is intended to include “and/or” unless specifically indicated otherwise. 
     The foregoing description of illustrative embodiments of the disclosed subject matter has been presented for purposes of illustration and of description. It is not intended to be exhaustive or to limit the disclosed subject matter to the precise form disclosed, and modifications and variations are possible in light of the above teachings or may be acquired from practice of the disclosed subject matter. The embodiments were chosen and described in order to explain the principles of the disclosed subject matter and as practical applications of the disclosed subject matter to enable one skilled in the art to utilize the disclosed subject matter in various embodiments and with various modifications as suited to the particular use contemplated.