Decremental Z-score calculation for big data or streamed data using components

Abstract

The present invention extends to methods, systems, and computing system program products for decrementally calculating Z-score for Big Data or streamed data. Embodiments of the invention include decrementally calculating one or more components of a Z-score for a modified computation subset based on one or more components of a Z-score calculated for a pre-modified computation subset and then calculating a Z-score for a selected data element in the modified computation subset based on one or more of the decrementally calculated components. Decrementally calculating Z-score avoids visiting all data elements in the modified computation subset and performing redundant computations thereby increasing calculation efficiency, saving computing resources and reducing computing system's power consumption.

What is claimed: 
     
       1. A computing-system-implemented method for calculating a Z-score for a selected data element for a modified computation subset, the method comprising:
 initializing, by a computing-device-based computing system, a computation subset size counter, a sum or a mean or both, and at least one additional component of a Z-score different from a sum and a mean for a pre-modified computation subset of a data stream or a data set on one or more storage media, wherein the pre-modified computation subset contains a specified number, n (n≥6), of data elements from the data stream or the data set, and the at least one additional component of a Z-score is a quantity or expression appearing in a Z-score's definition equation or any transforms of the equation; 
 accessing or receiving, by the computing-device-based computing system, a data element to be removed from the pre-modified computation subset; 
 modifying, by the computing-device-based computing system, the pre-modified computation subset:
 removing the accessed or received data element from the pre-modified computation subset; and 
 modifying the computation subset size counter; 
 
 decrementally deriving, by the computing-device-based computing system, a sum or a mean or both for the modified computation subset; 
 directly decrementally deriving, by the computing-device-based computing system and based at least in part on the at least one additional component of the Z-score different from a sum and a mean initialized or derived for the pre-modified computation subset, at least one additional component of a Z-score different from a sum and a mean for the modified computation subset, wherein the decrementally deriving includes:
 accessing the at least one additional component of the Z-score different from a sum and a mean for the pre-modified computation subset without accessing all data elements in the modified computation subset thereby saving computing resources and reducing the computing-device-based computing system's power consumption; and 
 removing any contribution of the data element removed from the pre-modified computation subset from each of the accessed components mathematically wherein not all data elements in the modified computation subset are used in the computation to reduce number of operations performed by the computing-device-based computing system thereby increasing calculation efficiency; 
 
 accessing, by the computing-device-based computing system, a data element selected for a Z-score calculation; and 
 generating, by the computing-device-based computing system, a Z-score for the selected data element for the modified computation subset based on one or more of the decrementally derived components. 
 
     
     
       2. The computing-system-implemented method of  claim 1 , wherein the generating a Z-score further comprises indirectly decrementally deriving, by the computing-device-based computing system, one or more components of the Z-score for the modified computation subset, wherein the indirectly decrementally deriving the one or more components includes individually calculating each respective one of the one or more components based on one or more components other than the respective one component. 
     
     
       3. The computing-system-implemented method of  claim 1 , wherein the method further comprises accessing a data element selected for a Z-score calculation and determining, after initializing the at least one additional component of a Z-score, by the computing-device-based computing system and based on one or more of the initialized components, a Z-score for the selected data element for the pre-modified computation subset. 
     
     
       4. The computing-system-implemented method of  claim 1 , wherein the receiving a data element to be removed includes receiving a plurality of z (z>1) data elements to be removed from the pre-modified computation subset, and wherein the method further comprises performing, for each of the respective z data elements, the modifying the pre-modified computation subset, the decrementally deriving a sum or a mean or both, the directly decrementally deriving the at least one additional component of a Z-score different from a sum and a mean for the modified computation subset, the accessing a data element selected for a Z-score calculation, and the generating a Z-score for the selected data element for the modified computation sub set. 
     
     
       5. The computing-system-implemented method of  claim 4 , wherein the accessing a data element selected for a Z-score calculation and the generating a Z-score for the selected data element for the modified computation subset comprises accessing a data element selected for a Z-score calculation and generating a Z-score for the modified computation subset only when the Z-score is accessed. 
     
     
       6. The computing-system-implemented method of  claim 5 , wherein the generating a Z-score for the modified computation subset further comprises indirectly decrementally deriving, by the computing-device-based computing system, one or more components of the Z-score for the modified computation subset, wherein the indirectly decrementally deriving of the one or more components includes individually calculating each respective one of the one or more components based on one or more components other than the respective one component. 
     
     
       7. The computing-system-implemented method of  claim 1 , wherein the receiving a data element to be removed includes receiving a plurality of z data elements to be removed from the pre-modified computation subset, and wherein the method further comprises performing, for each of the respective z data elements, the modifying the pre-modified computation subset, the decrementally deriving a sum or a mean or both, and the directly decrementally deriving the at least one additional component of a Z-score different from a sum and a mean for the modified computation sub set. 
     
     
       8. The computing-system-implemented method of  claim 1 , wherein the accessing or receiving a data element to be removed from the pre-modified computation subset further comprises removing the accessed or received data element from a data buffer on at least one of the one or more storage media. 
     
     
       9. A computing system, the computing system comprising:
 one or more computing devices; 
 each computing device comprising one or more processors; 
 one or more storage media; and 
 one or more calculation modules that, when executed by at least one of the one or more computing devices, determine a Z-score for a selected data element for a modified computation subset, the one or more calculation modules configured to: 
 a. initialize a computation subset size counter, a sum or a mean or both, and at least one additional component of a Z-score different from a sum and a mean for a pre-modified computation subset of a data stream or a data set on at least one of the one or more storage media, wherein the pre-modified computation subset contains a specified number, n (n≥6), of data elements from the data stream or the data set, and the at least one additional component of a Z-score is a quantity or expression appearing in a Z-score's definition equation or any transforms of the equation; 
 b. access or receive a data element to be removed from the pre-modified computation subset; 
 c. modify the pre-modified computation subset by removing the accessed or received data element from the pre-modified computation subset and modifying the computation subset size counter; 
 d. decrementally calculate a sum or a mean or both for the modified computation sub set; 
 e. directly decrementally calculate at least one additional component of a Z-score different from a sum and a mean for the modified computation subset based at least in part on the at least one additional component of the Z-score different from a sum and a mean initialized or calculated for the pre-modified computation subset, wherein decremental calculation of the at least one additional component includes to remove any contribution of the removed data element from the at least one additional component of the Z-score different from a sum and a mean initialized or calculated for the pre-modified computation subset mathematically without accessing and using all data elements in the modified computation subset thereby reducing data access latency, reducing number of operations performed by the computing system, and reducing the computing system's power consumption; 
 f. access a data element selected for a Z-score calculation; and 
 g. generate a Z-score for the selected data element for the modified computation subset based on one or more of the decrementally calculated components. 
 
     
     
       10. The computing system of  claim 9 , wherein the generating a Z-score for the modified computation subset further comprises indirectly decrementally calculate one or more components of a Z-score for the modified computation subset, wherein indirectly decrementally calculating one or more components includes individually calculating each respective one of the one or more components based on one or more components other than the respective one component. 
     
     
       11. The computing system of  claim 9 , wherein the one or more calculation modules, when executed by at least one of the one or more computing devices, performing b, c, d, e, f, and g multiple times. 
     
     
       12. The computing system of  claim 11 , wherein the performing f and g comprises accessing a data element selected for a Z-score calculation and generating a Z-score for the modified computation subset only when the Z-score is accessed. 
     
     
       13. The computing system of  claim 12 , wherein the generating a Z-score for the modified computation subset further comprises indirectly decrementally calculate one or more components of the Z-score for the modified computation subset, wherein indirectly decrementally calculating one or more components includes individually calculating each respective one of the one or more components based on one or more components other than the respective one component. 
     
     
       14. The computing system of  claim 9 , wherein the one or more calculation modules, when executed by at least one of the one or more computing devices, performing b, c, d, and e multiple times. 
     
     
       15. A computing system program product for use at a configured computing system which comprises one or more computing devices and one or more storage media, each computing device comprising one or more processors, the computing system program product comprising one or more non-transitory computing-device-readable storage media having stored thereon computing-device-executable instructions that, when executed by at least one of the one or more computing devices in the configured computing system, cause the configured computing system to perform a method for generating a Z-score for a selected data element for a modified computation subset, the method including steps to:
 initialize, by the configured computing system, a computation subset size counter, a sum or a mean or both, and at least one additional component of a Z-score different from a sum and a mean for a pre-modified computation subset of a data stream or a data set on at least one of the one or more storage media, wherein the pre-modified computation subset contains a specified number, n (n≥6), of data elements from the data stream or the data set, and the at least one additional component of a Z-score is a quantity or expression appearing in a Z-score's definition equation or any transforms of the equation; 
 access or receive, by the configured computing system, a data element to be removed from the pre-modified computation subset; 
 modify, by the configured computing system, the pre-modified computation subset via removing the accessed or received data element from the pre-modified computation subset and modifying the computation subset size counter by decreasing its value by 1; 
 decrementally calculate, by the configured computing system, a sum or a mean or both for the modified computation subset; 
 directly decrementally calculate, by the configured computing system, at least one additional component of a Z-score different from a sum and a mean for the modified computation subset based at least in part on the at least one additional component of the Z-score different from a sum and a mean initialized or calculated for the pre-modified computation subset, including to:
 access the at least one additional component of the Z-score different from a sum and a mean for the pre-modified computation subset without accessing all data elements in the modified computation subset thereby saving computing resources and reducing the computing-device-based computing system's power consumption; and 
 remove any contribution of the data element removed from the pre-modified computation subset from each of the accessed components mathematically wherein not all data elements in the modified computation subset are used in the computation to reduce number of operations performed by the computing-device-based computing system thereby increasing calculation efficiency; 
 
 access, by the configured computing system, a data element selected for a Z-score calculation; and 
 generate, by the configured computing system, a Z-score for the selected data element for the modified computation subset based on one or more of the decrementally calculated components. 
 
     
     
       16. The computing system program product of  claim 15 , wherein the generating a Z-score further comprises indirectly decrementally calculating, by the configured computing system, one or more components of the Z-score for the modified computation subset, wherein indirectly decrementally calculating the one or more components includes individually calculating each respective one of the one or more components based on one or more components other than the respective one component. 
     
     
       17. The computing system program product of  claim 15 , wherein the computing-device-executable instructions that, when executed, further cause the configured computing system to access or receive a data element to be removed from the pre-modified computation subset, to modify the pre-modified computation subset and the computation subset size counter, to decrementally calculate a sum or a mean or both, to directly decrementally calculate the at least one additional component different from a sum and a mean, to access a data element selected for a Z-score calculation, and to generate a Z-score for the selected data element for the modified computation subset for each of multiple data elements to be removed from the pre-modified computation subset. 
     
     
       18. The computing system program product of  claim 17 , wherein the computing-device-executable instructions that, when executed, cause the configured computing system to access a data element selected for a Z-score calculation and generate a Z-score comprise computing-device-executable instructions that, when executed, cause the configured computing system to access a data element selected for a Z-score calculation and generate a Z-score for the modified computation subset only when the Z-score is accessed. 
     
     
       19. The computing system program product of  claim 18 , wherein the generating a Z-score for the modified computation subset further comprises indirectly decrementally calculate one or more components of the Z-score for the modified computation subset, wherein indirectly decrementally calculating one or more components includes individually calculating each respective one of the one or more components based on one or more components other than the respective one component. 
     
     
       20. The computing system program product of  claim 15 , wherein the computing-device-executable instructions that, when executed, further cause the configured computing system to access or receive a data element to be removed from the pre-modified computation subset, to modify the pre-modified computation subset and the computation subset size counter, to decrementally calculate a sum or a mean or both, and to directly decrementally calculate the at least one additional component different from a sum and a mean for each of multiple data elements to be removed from the pre-modified computation subset.