Algorithms/methods for detecting regime changes in data rates

Question

I'm looking at multiple live data streams which I process on a daily basis and would like to monitor in real time.

The way I did it at first was to introduce a somewhat arbitrary upper bound for each of the streams..the monitoring would look at time elapsed between consecutive stream items and if it exceeds its threshold it would alert on possibly missing data on that stream. The problem with this approach is that the streams are very active at some points of the day and rather quiet at other points, so a hard coded limit ends up being unnecessarily high to avoid false alarms during the tranquil periods.

The second way I reworked it was to introduce bucketed data rate thresholds for each data stream. So, for example, something like: Stream A 4am threshold, Stream A 7am threshold, Stream A 5pm threshold...and the threshold used throughout the day is dependent on the time. This is more reasonable but the problem I have now is in coming up with appropiate times for each stream in a better way than arbitrarily choosing them for each data stream. For a given stream, I envision stepping through the data and generating "reasonable" buckets along with their threshold (for now I'm using twice the maximum time between items because their distribution is not approximately normal so I haven't looked at how to get a threshold time which would correspond to a certain low probability of occurrence) but I'm wondering where to start for this? And is this similar or identical to a well studied problem with solutions I might want to use?

Answer 1

Sounds like the streams you are interested in could be modelled as inhomogeneous Poisson processes. Not surprising that the time between items is not normal --- I'm guessing it is closer to exponential. You may be interested in this white paper, which discusses a simple stat for detecting a change in rate of this type of data. It might provide a data-based way to select the buckets for each stream. In any case, you might want to look into change-point detection in general (e.g., https://stats.stackexchange.com/questions/tagged/change-point)

I could envision monitoring each stream for a few days, using the stat in the above paper (or some other change point algorithm) to find where the rate changes occur. Then you can model each stream within that bucket as a Poisson process with the average rate seen over those few days. Since you'd have a model for the data in each bucket, you could then get a probability that a stream is unusually active or tranquil at any particular time.