Click or drag to resize

Shifted Wavelet Tree

The Shifted Wavelet Tree is the efficient method for calculation some function on the different point intervals. The algorithms is described in paper [Yunyue Zhu and Dennis Shasha Efficient Elastic Burst Detection in Data Streams / In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, – ACM New York, NY, USA ©2003, – pp. 336-345].

The structure of the ordinary wavelet tree and shifted wavelet tree presented on the next figure.

BDShifted Wavelet

As you can see, in case of ordinary wavelet tree, the decimated values were not computed at all, whereas in shifted wavelet tree the intermediate values computed, but not used in next level values evaluation. These intermediate values can be used for more precise event detection.

As proved in the paper mentioned above, the algorithm can guarantee no false negatives in elastic burst detection from a time series of nonnegative numbers. Note the library contains only online algorithm implementation, as more useful and less memory consumption.

As you can see, any reasonable functional can be calculated with next restrictions:

  • The aggregate functional F is monotonically increasing or decreasing with respect to the window, i.e., if window [a1..b1] is contained in window [a2..b2], then F(x[a1..b1]) ≤F(x[a2..b2]) (or F(x[a1..b1]) ≥ F(x[a2..b2])) always holds.

  • The alarm domain is one sided, that is, [threshold, ∞) for monotonic increasing aggregates and (−∞, threshold] for monotonic decreasing aggregates.

At now, the library includes next functional: mean value (in ShiftedWaveletTreeMean class), minimum value (in ShiftedWaveletTreeMin class), maximum value (in ShiftedWaveletTreeMax class), spread value (maximum – minimum) (in ShiftedWaveletTreeSpread class).

The threshold level monitoring is not the case of this algorithm and classes. For this purpose you should use another appropriate algorithm and class (like Thresholder, for example).

Implementation

Use method Add to update the indicator value. Use property Value to get the current value.

Code Sample

C#
Copy
  1using System;
  2using System.Collections.Generic;
  3using System.Linq;
  4using System.Text;
  5using FinAnalysis.BurstDetection;
  6using FinAnalysis.Base;
  7using FinAnalysis.TA;
  8
  9namespace ShiftedWaveletTreeSample
 10{
 11    class ShiftedWaveletTreeSample
 12    {
 13        static public void PointWindowMean(Int32 count, Int32 levelLo, Int32 levelHi)
 14        {
 15            // Generate random data.
 16            Random random = new Random();
 17
 18            ShiftedWaveletTreeMean swt = new ShiftedWaveletTreeMean(levelLo, levelHi, 0.5);
 19            for (Int32 i = 0; i < count; ++i)
 20                if (swt.Add(random.NextDouble() * 1000000 + 1))
 21                {
 22                    Double[] result = swt.Values;
 23
 24                    // Check for incorrect values.
 25                    for (Int32 j = 0; j < result.Length; ++j)
 26                    {
 27                        if (Double.IsNaN(result[j]))
 28                            Console.WriteLine("Fail result[" + i + "][" + j + "] = NaN");
 29                        else if (Double.IsInfinity(result[j]))
 30                            Console.WriteLine("Fail result[" + i + "][" + j + "] = Infinity");
 31                    }
 32                }
 33        }
 34
 35        static public void PointWindowSpread(Int32 count, Int32 levelLo, Int32 levelHi)
 36        {
 37            // Generate random data.
 38            Random random = new Random();
 39
 40            ShiftedWaveletTreeSpread swt = new ShiftedWaveletTreeSpread(levelLo, levelHi, 0.5);
 41            for (Int32 i = 0; i < count; ++i)
 42                if (swt.Add(random.NextDouble() * 1000000 + 1))
 43                {
 44                    Double[] result = swt.Values;
 45
 46                    // Check for incorrect values.
 47                    for (Int32 j = 0; j < result.Length; ++j)
 48                    {
 49                        if (Double.IsNaN(result[j]))
 50                            Console.WriteLine("Fail result[" + i + "][" + j + "] = NaN");
 51                        else if (Double.IsInfinity(result[j]))
 52                            Console.WriteLine("Fail result[" + i + "][" + j + "] = Infinity");
 53                    }
 54                }
 55        }
 56
 57        static public void PointWindowMin(Int32 count, Int32 levelLo, Int32 levelHi)
 58        {
 59            // Generate random data.
 60            Random random = new Random();
 61
 62            ShiftedWaveletTreeMin swt = new ShiftedWaveletTreeMin(levelLo, levelHi, 0.5);
 63            for (Int32 i = 0; i < count; ++i)
 64                if (swt.Add(random.NextDouble() * 1000000 + 1))
 65                {
 66                    Double[] result = swt.Values;
 67
 68                    // Check for incorrect values.
 69                    for (Int32 j = 0; j < result.Length; ++j)
 70                    {
 71                        if (Double.IsNaN(result[j]))
 72                            Console.WriteLine("Fail result[" + i + "][" + j + "] = NaN");
 73                        else if (Double.IsInfinity(result[j]))
 74                            Console.WriteLine("Fail result[" + i + "][" + j + "] = Infinity");
 75                    }
 76                }
 77        }
 78
 79        static public void PointWindowMax(Int32 count, Int32 levelLo, Int32 levelHi)
 80        {
 81            // Generate random data.
 82            Random random = new Random();
 83
 84            ShiftedWaveletTreeMax swt = new ShiftedWaveletTreeMax(levelLo, levelHi, 0.5);
 85            for (Int32 i = 0; i < count; ++i)
 86                if (swt.Add(random.NextDouble() * 1000000 + 1))
 87                {
 88                    Double[] result = swt.Values;
 89
 90                    // Check for incorrect values.
 91                    for (Int32 j = 0; j < result.Length; ++j)
 92                    {
 93                        if (Double.IsNaN(result[j]))
 94                            Console.WriteLine("Fail result[" + i + "][" + j + "] = NaN");
 95                        else if (Double.IsInfinity(result[j]))
 96                            Console.WriteLine("Fail result[" + i + "][" + j + "] = Infinity");
 97                    }
 98                }
 99        }
100
101        static public void Main(string[] args)
102        {
103            PointWindowMean(1000000, 3, 7);
104
105            PointWindowSpread(1000000, 2, 6);
106
107            PointWindowMin(1000000, 4, 9);
108
109            PointWindowMax(1000000, 5, 5);
110        }
111    }
112}

See Also