Hi all,

Casey and I had an interesting chat yesterday, during which we agreed that the 
example code for Outlier Analysis in 
https://github.com/apache/incubator-metron/blob/master/metron-analytics/metron-statistics/README.md
 and the revised example code in 
https://issues.apache.org/jira/browse/METRON-668 (as of 23 January) both do not 
correctly implement the desired Sliding Window model.  This email gives the 
argument for why, and proposes a couple ways to do it right.  Your input and 
preferences are requested.

 

First a couple statements about the STATS object that underlies most 
interesting Profile work:

·         The STATS object is a t-digest.  It summarizes a set of data points, 
such as those received during a sampling period, in a way that is nominally 
O(1) regardless of the input number of data points, and preserves the info 
about the “shape” of the statistical distribution of those points.  Not only 
info about averages and standard deviations, but also about medians and 
percentiles (which, btw, is a very different kind of information), is preserved 
and can be calculated correctly to within a given error epsilon.  Since it is a 
summary, however, time information is lost.

·         STATS objects, these digests of sampling periods, are MERGEABLE, 
meaning if you have a digest from time(1) to time(2), and another digest from 
time(2) to time (3), you can merge them and get a digest that is statistically 
equivalent to a digest from time(1) to time(3) continuously.

·         They are sort of idempotent, in that if you take two identical 
digests and merge them, you get almost the same object.  However, the result 
object will be scaled as summarizing twice the number of input data points.

·         Which is why it DOESN’T work to try to merge overlapping sampling 
periods.  To give a crude example, if you have a digest from time(1) to time(3) 
and another digest from time(2) to time(4), and merge them, the samples from 
time(2) to time(3) will be over-represented by a factor of 2x, which should be 
expected to skew the distribution (unless the distribution really is constant 
for all sub-windows – which would mean we don’t need Sliding Windows because 
nothing changes).

 

The Outlier Analysis profiles linked above try to implement a sliding window, 
in which each profile period summarizes the Median Absolute Deviation 
distribution of the last five profile periods only.  An “Outlier MAD Score” can 
then be determined by comparing the deviation of a new data point to the last 
MAD distribution recorded in the Profile.  This allows for changes over time in 
the statistical distribution of inputs, but does not make the measure unduly 
sensitive to just the last minute or two.  This is a typical use case for 
Sliding Windows.

 

Both example codes trip on how to do the sliding window in the context of a 
Profile.  At sampling period boundaries, both either compose the “result” 
digest or initialize the “next” digest by reading the previous 5 result 
digests.  That is wrong, because it ignores the fact that those digests aren’t 
just for their time periods.  They too were composed with THEIR preceding 5 
digests, each of which were composed with their preceding 5 digests, which in 
turn… etc.  The end result is sort of like the way Madieras or some brandies 
are aged via the Solera process with fractional blending.  You don’t get a true 
sliding window, which sharply drops the past, you get a continuous dilution of 
the past. In fact, it’s wrong to assume that the “tail” of the far past is more 
diluted than the near past! – It would be with some algorithms, but the alg 
used in these two examples causes the far past to become an exponentially MORE 
important fraction of the overall data than the near past – much worse than 
simply turning on digesting at time(0) and leaving it on, with no attempt at 
windowing.  (Simulate it in a spreadsheet and you’ll see.)

 

We need a Profiler structure that assists in creating Sliding Window profiles.  
The problem is that Profiles let you save only one thing (quantity or object) 
per sampling period, and that’s typically a different “thing” (object type or 
scale) than you want to use to compose the result for each windowed span.  One 
way to do it correctly would be with two Profiles, like this:

 

(SOLUTION A)

{

  "profiles": [

    {

      "profile": "sketchy_mad",

      "foreach": "'global'",

      "init" : {

        "s": "OUTLIER_MAD_INIT()"

        },

      "update": {

        "s": "OUTLIER_MAD_ADD(s, value)"

        },

      "result": "s"

    },

    {

      "profile": "windowed_mad",

      "foreach": "'global'",

      "init" : { },

      "update": { },

      "result": "OUTLIER_MAD_STATE_MERGE(PROFILE_GET('sketchy_mad',

'global', 5, 'MINUTES'))"

    }

  ]

}

 

This is typical.  You have a fine-grain sampling period that you want to 
“tumble”, and a broader window that you want to “slide” or “roll” along the 
underlying smaller sampling periods.

The above pair of profiles is clear enough, but not real efficient.  Also, you 
can’t guarantee they’ll stay exactly synchronized.  It would be better to 
combine them somehow.

 

In these examples, we only need to look back 5 sampling periods, so the 
following would work (NOTE: requires Casey’s PR#668 that preserves state 
between sampling periods): 

 

(SOLUTION B)

{

  "profiles": [

    {

      "profile": "windowed_mad",

      "foreach": "'global'",

      "init" : {

        "s4": "if exists(s3) then s3 else OUTLIER_MAD_INIT()",

        "s3": "if exists(s2) then s2 else OUTLIER_MAD_INIT()",

        "s2": "if exists(s1) then s1 else OUTLIER_MAD_INIT()",

       "s1": "if exists(s0) then s0 else OUTLIER_MAD_INIT()",

        "s0": "OUTLIER_MAD_INIT()"

        },

      "update": {

        "s0": "OUTLIER_MAD_ADD(s0, value)"

        },

      "result": "OUTLIER_MAD_STATE_MERGE(s0, s1, s2, s3, s4)”

    }

  ]

}

 

This works fine for a sliding window of size 5 sample periods.  But what if it 
was 15?  Or 60?

No doubt we could implement a ring buffer with a stellar list object, but it’s 
gonna get ugly(er) and slow.

 

A much more elegant solution would be to allow “result” to write two objects.  
The result could be viewed either as two Profiles, or as a Profile with 
multiple addressable columns of hbase output.  For instance:

(SOLUTION C)

{

  "profiles": [

    {

      "profile": "[ 'sketchy_mad', 'windowed_mad' ]",

      "foreach": "'global'",

      "init" : {

        "s": "OUTLIER_MAD_INIT()"

        },

      "update": {

        "s": "OUTLIER_MAD_ADD(s, value)"

        },

      "result": {

        "sketchy_mad": "s",

        "windowed_mad": "OUTLIER_MAD_STATE_MERGE(s, PROFILE_GET('sketchy_mad',

'global', 4, 'MINUTES'))"

        }

    }

  ]

}

 

This is clean and tight, and I think will be easily generalized to any Sliding 
Window scenario.

BTW, given that each write has to work it’s way through more processing before 
getting to HBase, it’s best to say that all writes happen AFTER all the 
“result” processing, which is why I showed the MERGE above retrieving only 4 
sampling periods prior to the current one, and then add the current one from 
local state.

 

What do you think?  Can anyone specify a better way to do Sliding Window 
profiles correctly with current functionality?

 

 

Casey noted that if this feature were available, he would like to consider 
separating the value distribution from the deviation distribution, in the 
OUTLIER_MAD state objects.  He also notes that the hypothetical 
OUTLIER_MAD_INIT() function needs to take a starting median, as argument.  So 
the final Sliding Window Profile for OUTLIER_MAD state tracking might look more 
like:

 

{

  "profiles": [

    {

      "profile": "[ 'sketchy_values', 'sketchy_mad', 'windowed_mad' ]",

      "foreach": "'global'",

      "init" : {

        "median": "STATS_PERCENTILE(STATS_MERGE(PROFILE_GET('sketchy_values', 
'global', 5, 'MINUTES')), 50)",

        "s": "OUTLIER_MAD_INIT(median)",

        "val_dist": "STATS_INIT()"

        },

      "update": {

        "val_dist": "STATS_ADD(val_dist, value)",

        "s": "OUTLIER_MAD_ADD(s, value)"

        },

      "result": {

        "sketchy_values": "val_dist",

        "sketchy_mad": "s",

        "windowed_mad": "OUTLIER_MAD_STATE_MERGE(s, PROFILE_GET('sketchy_mad',

'global', 4, 'MINUTES'))"

        }

    },

  ]

}

 

Thanks,

--Matt

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Reply via email to