Method and system for detecting change in data streams

Abstract

A system for detecting change in a data stream comprising a distribution maintenance engine, a difference determining means and an alert generation engine is disclosed. The system detects change in the alert stream by the distribution maintenance engine maintaining a short term distribution that models the data stream and maintaining a long term distribution that models the data stream. The difference determining means determines the difference between the short term distribution and the long term distribution. The alert generation engine applies a statistical measure to the difference and generates an alert if the measure of the difference exceeds a threshold.

1 . A method of detecting changes in the properties of a data stream, comprising: 
 maintaining a short term distribution that models the data stream;    maintaining a long term distribution that models the data stream;    determining a difference between the short term distribution and the long term distribution; and    applying a statistical measure to the difference and generating an alert if the measure of the difference exceeds a threshold.    
   
   
       2 . A method according to  claim 1 , wherein the short term distribution is a model of probability distributions that describe the data stream.  
   
   
       3 . A method according to  claim 1 , wherein the long term distribution is a model of probability distributions that describe the data stream.  
   
   
       4 . A method according to  claim 1 , wherein the short term distribution is a recursively estimated weighted distribution of all the data received thus far.  
   
   
       5 . A method according to  claim 1 , wherein the long term distribution is a recursively estimated weighted distribution of all of the data received thus far.  
   
   
       6 . A method according to  claim 1 , wherein the short term distribution weights recent information more heavily than the long term distribution.  
   
   
       7 . A method according to  claim 1 , wherein the short term distribution is updated when input data is received.  
   
   
       8 . A method according to  claim 1 , wherein the long term distribution is updated when the input data is received.  
   
   
       9 . A method according to  claim 1 , wherein when an alert is generated the short term distribution is returned to a state just before it was updated to include an input that caused the alert.  
   
   
       10 . A method according to  claim 1 , wherein an alert is generated if the long term distribution is returned to a state just before it was updated to include an input that caused the alert.  
   
   
       11 . A method according to  claim 1 , wherein an alert is generated if the difference exceeds an adaptive alert threshold.  
   
   
       12 . A method according to  claim 11 , wherein the adaptive alert threshold is a function of the short term and long term distributions and previous values of the alert threshold.  
   
   
       13 . A method according to  claim 11 , wherein the adaptive alert threshold is formed from a predictability measure and a variability measure.  
   
   
       14 . A method according to  claim 13 , wherein the predictability measure is a moving average of the difference between the short term distribution and the long term distribution.  
   
   
       15 . A method according to  claim 13 , wherein the variability measure is a moving average of the absolute difference between the short term distribution and the long term distribution and the predictability measure.  
   
   
       16 . A method according to  claim 13 , wherein the predictability and variability measures are not updated when the measured difference between the short term distribution and the long term distribution exceeds a function of the variability measure.  
   
   
       17 . A method according to  claim 11 , wherein the generated alert includes information in the data stream and/or a function of information in the data stream.  
   
   
       18 . A method according to  claim 17 , wherein the generated alert includes a propensity measure as an indication of the severity of change.  
   
   
       19 . A method according to  claim 18 , wherein the propensity measure is calculated by dividing, the difference between the measure of difference between the short term distribution and the long term distribution and the alert threshold, by the variability measure.  
   
   
       20 . A method according to  claim 1 , further comprising maintaining an estimate of the amounts by which the sensitivity to the alert threshold would be needed to have been adjusted in order to not have generated an alert that turned out not to be caused by an event of interest since the last time it was instructed to adapt.  
   
   
       21 . A method according to  claim 20 , wherein the sensitivity adjustment estimate is increased by an additive constant each time an alert is generated and decays exponentially with each input received.  
   
   
       22 . A method according to  claim 1 , wherein a lead period may be provided during which alerts cannot be generated and the short term distribution and the long term distribution are adapted to all inputs within that period.  
   
   
       23 . A method according to  claim 1 , wherein alerts may be suppressed from being generated by inputs that are above a configurable lower percentile or below a configurable upper percentile.  
   
   
       24 . A method according to  claim 23 , wherein the lower percentile and upper percentile are both estimated from the long term probability distribution.  
   
   
       25 . A method according to  claim 1 , wherein the short term and long term distributions model discrete values.  
   
   
       26 . A method according to  claim 1 , wherein the short term and long term distributions model continuous values.  
   
   
       27 . A system for detecting changes in the properties of a data stream, comprising: 
 a distribution maintenance engine configured to maintain a short term distribution that models data stream and a long term distribution that models the data stream;    a determining section configured to determine a difference between the short term distribution and the long term distribution; and    an alert generation engine configured to apply a statistical measure to the difference and to generate an alert if the measure of the difference exceeds a threshold.    
   
   
       28 . A system according to  claim 27 , further comprising a threshold adaptation engine configured to adaptively determine the threshold.  
   
   
       29 . A system according to  claim 27 , wherein the distribution maintenance engine is configured to return the short term distribution to a state just before it was updated, when an alert is generated.  
   
   
       30 . A system according to  claim 27 , wherein the distribution maintenance engine is configured to return the long term distribution to a state just before it was updated, when an alert is generated.  
   
   
       31 . A system for detecting changes in the properties of a data stream, the system comprising: 
 means for maintaining a short term distribution that models the data stream;    means for maintaining a long term distribution that models the data stream;    means for determining a difference between the short term distribution and the long term distribution; and    means for applying a statistical measure to the difference and generating an alert if the measure of the difference exceeds a threshold.