Real time detection of peaks of frequency of events

Question

In a web application, I get a trigger every time an event occurs. I want to detect 'violent' frequency peaks, which probably translate into abnormal behaviour.

I can think of two naive ways of achieving that:

• Fixed threshold - "If more than 500 events occur within a minute, sth's probably wrong". This method cannot handle smooth threshold breaches or steadily increasing traffic, unless the application can adjust the threshold periodically.

• Window-related heuristic - Divide the window into N equal (?) intervals. While N>0, calculate the frequency of events happened in [now-(N*interval_length), now]. Save it in a list. Decrease N by 1. Repeat. Detect list outliers. If there is an outlier larger than the mean frequency of [now-window_length, now], sth's probably wrong."

I'd like to know if there is instead a common/standard solution for this problem or if you can think of anything more efficient or elegant.

Thank you in advance.

EDIT -- Another suggestion

A friend of mine suggested aberrant behaviour detection with Holt-Winters forecasting. You can find more information about this methodology in the links below:

http://www.hpl.hp.com/news/events/csc/2005/jake_slides.pdf

http://www.usenix.org/events/lisa00/full_papers/brutlag/brutlag_html/

Answer 1

You can compute an exponentially weighted floating-mean estimator, and compare it with its previous value. An abrupt increase is probably what you are trying to detect, but combined with a certain minimum threshold (so e.g. 0 to 1 is not significant).

But say the current floating mean jumps up from 100 to 200, that probably is the kind of events you want to detect.

Answer 2

I am not expert. What I would do:

Let's say you keep only the last n results and x_n is the last sample (time difference from the previous event).

α_n x_n + α_{n-1}/2 x_{n-1} + ... + α_{1} 2^{-n} x_1 = T

If the difference T - T_{previous}, where T_{previous} is the previous value of T, surpass a limit, do something.

If your values of x_i are binary, you can nice tricks with shift and or operations, if speed is a matter.

Answer 3

just get a simple average over the values of the last X minutes (keep the values)

compare each new incoming value with the average:

• if difference is more than Y% then its an outlier, alert.
• If less, add this to the average and remove the first one, fifo style.

If you think it can be tricked with ' steadily increasing traffic', make X sufficiently large.