-can be modelled using normal distribution. After trimming the outliers,
-the median and deviations from median are used for detecting performance
-change anomalies following the three-sigma rule of thumb (a.k.a.
-68-95-99.7 rule).
-
-Metrics
-````````````````
-
-Following statistical metrics are used as performance trend indicators
-over the rolling window of last <N> sets of historical measurement data:
-
-- Q1, Q2, Q3 : Quartiles, three points dividing a ranked data set
- of <N> values into four equal parts, Q2 is the median of the data.
-- IQR = Q3 - Q1 : Inter Quartile Range, measure of variability, used
- here to calculate and eliminate outliers.
-- Outliers : extreme values that are at least (1.5 * IQR) below Q1.
-
- - Note: extreme values that are at least (1.5 * IQR) above Q3 are not
- considered outliers, and are likely to be classified as
- progressions.
-
-- TMA : Trimmed Moving Average, average across the data set of <N>
- values without the outliers. Used here to calculate TMSD.
-- TMSD : Trimmed Moving Standard Deviation, standard deviation over the
- data set of <N> values without the outliers,
- requires calculating TMA. Used for anomaly detection.
-- TMM : Trimmed Moving Median, median across the data set of <N> values
- excluding the outliers. Used as a trending value and as a reference
- for anomaly detection.
-
-Outlier Detection
-`````````````````
-
-Outlier evaluation of test result of value <X> follows the definition
-from previous section:
-
- ::
-
- Outlier Evaluation Formula Evaluation Result
- ====================================================
- X < (Q1 - 1.5 * IQR) Outlier
- X >= (Q1 - 1.5 * IQR) Valid (For Trending)
+can be modelled as concatenation of groups, each group modelled
+using normal distribution. While sometimes the samples within a group
+are far from being distributed normally, currently we do not have a
+better tractable model.
+
+The group boundaries are selected based on `Minimum Description Length`_.
+
+Minimum Description Length
+--------------------------
+
+`Minimum Description Length`_ (MDL) is a particular formalization
+of `Occam's razor`_ principle.
+
+The general formulation mandates to evaluate a large set of models,
+but for anomaly detection purposes, it is useful to consider
+a smaller set of models, so that scoring and comparing them is easier.
+
+For each candidate model, the data should be compressed losslessly,
+which includes model definitions, encoded model parameters,
+and the raw data encoded based on probabilities computed by the model.
+The model resulting in shortest compressed message is the "the" correct model.
+
+For our model set (groups of normally distributed samples),
+we need to encode group length (which penalizes too many groups),
+group average (more on that later), group stdev and then all the samples.
+
+Luckily, the "all the samples" part turns out to be quite easy to compute.
+If sample values are considered as coordinates in (multi-dimensional)
+Euclidean space, fixing stdev means the point with allowed coordinates
+lays on a sphere. Fixing average intersects the sphere with a (hyper)-plane,
+and Gaussian probability density on the resulting sphere is constant.
+So the only contribution is the "area" of the sphere, which only depends
+on the number of samples and stdev.
+
+A somehow ambiguous part is in choosing which encoding
+is used for group size, average and stdev.
+Diferent encodings cause different biases to large or small values.
+In our implementation we have chosen probability density
+corresponding to uniform distribution (from zero to maximal sample value)
+for stdev and average of the first group,
+but for averages of subsequent groups we have chosen a distribution
+which disourages deliminating groups with averages close together.
+
+// Below paragraph needs to be updated.
+One part of our implementation which is not precise enough
+is handling of measurement precision.
+The minimal difference in MRR values is currently 0.1 pps
+(the difference of one packet over 10 second trial),
+but the code assumes the precision is 1.0.
+Also, all the calculations assume 1.0 is totally negligible,
+compared to stdev value.
+
+The group selection algorithm currently has no parameters,
+all the aforementioned encodings and handling of precision is hardcoded.
+In principle, every group selection is examined, and the one encodable
+with least amount of bits is selected.
+As the bit amount for a selection is just sum of bits for every group,
+finding the best selection takes number of comparisons
+quadratically increasing with the size of data,
+the overall time complexity being probably cubic.
+
+The resulting group distribution looks good
+if samples are distributed normally enough within a group.
+But for obviously different distributions (for example `bimodal distribution`_)
+the groups tend to focus on less relevant factors (such as "outlier" density).