Techniques to find percentiles in a distributed computing environment

An article of manufacture comprising a storage medium containing instructions that when executed enable a system to:

• determine a target rank position at a target percentile rank for a total data set;
• divide the total data set into one or more data subsets;
• allocate each of the one or more data subsets of the total data set to a particular one of one or more processors;
• sort each allocated data subset to form sorted data subsets;
• determine candidate rank positions for each of the sorted data subsets based on the target percentile rank and a data subset size representing a total number of data items within each of the sorted data subsets;
• retrieve a candidate data item from a candidate rank position for each sorted data subset;
• and
• determine a target data item at the target rank position for the total data set using candidate data items at candidate rank positions from each of the sorted data subsets of the total data set, and correlation values associated with each of the candidate data items, each correlation value for each of the candidate data items from each of the sorted data subsets representing an approximate rank position of the target data item based on a summation of a number of data items within each sorted data subset with a value lower than or equal to the candidate data item for the sorted data subset and iteratively used to isolate the target rank position for the target data item.

An apparatus, comprising:

• a processor;
• and
• a memory unit communicatively coupled to the processor, the memory unit to store a correlation module that when executed by the processor is operative to:
• determine a target rank position at a target percentile rank within a total data set,
• divide the total data set into one or more data subsets,
• allocate each of the one or more data subsets of the total data set to the processor,
• sort each allocated data subset to form sorted data subsets,
• determine candidate rank positions for each of the sorted data subsets based on the target percentile rank and a data subset size representing a total number of data items within each of the sorted data subsets,
• retrieving a candidate data item from a candidate rank position for each sorted data subset, and
• determine a target data item at the target rank position for the total data set using candidate data items at candidate rank positions from each of the sorted data subsets of the total data set, and correlation values associated with each of the candidate data items, each correlation value for each of the candidate data items from each of the sorted data subsets representing an approximate rank position of the target data item based on a summation of a number of data items within each sorted data subset with a value lower than or equal to the candidate data item for the sorted data subset and iteratively used to isolate the target rank position for the target data item.

A computer-implemented method, comprising:

• receiving a target percentile rank to identify a target rank position of a target data item;
• determining the target rank position at the target percentile rank within a total data set distributed between one or more processors;
• dividing the total data set into a plurality of data subsets;
• allocating a data subset of the total data set to each processor;
• sorting each allocated data subset to form sorted data subsets;
• determining candidate rank positions for each of the sorted data subsets based on the target percentile rank and a data subset size representing a total number of data items within each of the sorted data subsets;
• retrieving a candidate data item from a candidate rank position for each sorted data subset;
• determining the target data item at the target rank position for the total data set using candidate data items at candidate rank positions from each of the sorted data subsets of the total data set, and correlation values associated with each of the candidate data items, each correlation value for each of the candidate items from each of the sorted data subsets representing an approximate rank position of the target data item based on a summation of a number of data items within each sorted data subset with a value lower than or equal to the candidate data item for sorted data subset and iteratively used to isolate the target rank position for the target data item;
• comparing correlation values for each of the candidate data items to find a correlation value closest to the target rank position and not exceeding the target rank position;
• determining a closest correlation value does not match the target rank position;
• and
• performing a merge algorithm starting at a set of starting candidate rank positions until a candidate rank position for a candidate data item matches the target rank position.