MADRID: A Hyper-Anytime Algorithm to Find Time Series Anomalies of all Lengths

Student: Yue Lu

Committee Chair: Eamonn Keogh

Committee Members: Tao Jiang� Tamar Shinar� Evangelos Papalexakis

I am a fifth-year Ph.D. student in the Department of Computer Science and Engineering at University of California, Riverside. My advisor is Dr. Eamonn Keogh. 

Prior to beginning my doctoral studies at UC Riverside, I received my B.S. in Software Technology and Applications with First Class Honors from the Macau University of Science and Technology.

Publications

• Yue Lu, Thirumalai Vinjamoor Akhil Srinivas, Takaaki Nakamura, Makoto Imamura, and Eamonn Keogh. Matrix Profile XXX: MADRID: A Hyper-Anytime and Parameter-Free Algorithm to Find Time Series Anomalies of all Lengths. In Proceedings of IEEE International Conference on Data Mining (ICDM ‘23) 2023.
• Sadaf Tafazoli, Yue Lu, Renjie Wu, Thirumalai Srinivas, Hannah Dela Cruz, Ryan Mercer, and Eamonn Keogh. Matrix Profile XXIX: C22MP: Fusing catch22 and the Matrix Profile to Produce an Efficient and Interpretable Anomaly Detector. In Proceedings of IEEE International Conference on Data Mining (ICDM ‘23) 2023.
• Yue Lu, Renjie Wu, Mueen Abdullan, Maria A. Zuluaga, Eamonn Keogh. DAMP: accurate time series anomaly detection on trillions of datapoints and ultra-fast arriving data streams. Data Mining and Knowledge Discovery, pp.1-43 2023.
• Yue Lu, Renjie Wu, Mueen Abdullan, Maria A. Zuluaga, Eamonn Keogh. Matrix Profile XXIV: Scaling Time Series Anomaly Detection to Trillions of Datapoints and Ultra-fast Arriving Data Streams. In Proceedings of ACM Conference on Knowledge Discovery and Data Mining (KDD ‘22) 2022.

About me

Outline

• Motivation
• The proposed method: MADRID
• Empirical Evaluation
• Conclusion

Outline

• Motivation
• The proposed method: MADRID
• Empirical Evaluation
• Conclusion

Why is it worth further improving time series discords?

• Even though numerous time series anomaly detection (TSAD) methods are proposed every year, time series discords remain competitive among the state-of-the-art methods. (as we, and other groups have shown)
• It is simple and requires only one parameter.
• It seems to be the only TSAD technique to produce “superhuman” results.
• It has been widely used by more than one hundred independent teams to solve different real-world problems.
• However, time series discords have noted one weakness, the anomalies discovered depend on the algorithm’s only input parameter, the subsequence length.

Limitations of single-length TSAD algorithms I

• For single-length TSAD algorithms, setting the correct window size is very important. Numerous researchers have pointed this out, for example [1] notes: “failure to provide an optimal window size may incur monetary damage.”
• However, creating a heuristic to find the “optimal” window size (even assuming that such a task is well-defined) is a very hard task.
• The window size setting may depend on domain-specific information. Again from [1], “Finding the optimal window size has remained to be one of the most challenging tasks in TSDM domains, where no domain-agnostic method is known for learning the window size”.

[1] A. Ermshaus, P. Schäfer, and U. Leser, “Window Size Selection in Unsupervised Time Series Analytics: A Review and Benchmark,” in AALTD, 2023, pp. 83–101.

Limitations of single-length TSAD algorithms II

8

24

0

4000

0

Battery change

4000

0

70

hours

May 18^th 2016

Jan 25^th 2017

Bourke Street Mall (North) Pedestrian Traffic

# of Pedestrians

Subsequence Length (hours)

• Some datasets in the real world may have structures and anomalies on multiple scales. Consider this Melbourne pedestrian traffic data.
• Had we chosen ten hours, we would have discovered the sensor battery change on June 12th.

​

Limitations of single-length TSAD algorithms II

8

24

0

4000

0

70

hours

Xmas Day

May 18^th 2016

Jan 25^th 2017

Bourke Street Mall (North) Pedestrian Traffic

Subsequence Length (hours)

• Some datasets in the real world may have structures and anomalies on multiple scales. Consider this Melbourne pedestrian traffic data.
• Had we chosen twelve hours (or longer), we would have only discovered Xmas day.

Limitations of single-length TSAD algorithms II

8

24

0

4000

0

70

hours

Car Attack

May 18^th 2016

Jan 25^th 2017

Bourke Street Mall (North) Pedestrian Traffic

Subsequence Length (hours)

• Some datasets in the real world may have structures and anomalies on multiple scales. Consider this Melbourne pedestrian traffic data.
• Had we chosen only eight hours, we would have only discovered the tragic car attack on January 20th.

​

Limitations of single-length TSAD algorithms II

• Some datasets in the real world may have structures and anomalies on multiple scales.
• An algorithm that relies on a single subsequence length would miss anomalies at other lengths.

Limitations of single-length TSAD algorithms III

• Even for datasets that only have anomalies of the same length, finding the optimal window size is very hard.
• Anomaly detection can be hypersensitive to the sliding window size m. In the worst case, a subtle change in m dramatically affects the discord score.
• In both examples, m must be set exactly to 49, no more, no less.

Limitations of single-length TSAD algorithms III

• Even for datasets that only have anomalies of the same length, finding the optimal window size is very hard.
• Anomaly detection can be hypersensitive to the sliding window size m. In the worst case, a subtle change in m dramatically affects the discord score and can cause a single-length TSAD algorithm to fail.
• For any algorithm considering a window size of m < 54, this trivially simple problem is unsolvable.

Limitations of single-length TSAD algorithms III

8

24

0

4000

0

This small blip is only anomalous when seen in the context of the normal data that surrounds it

4000

0

70

hours

May 18^th 2016

Jan 25^th 2017

Bourke Street Mall (North) Pedestrian Traffic

# of Pedestrians

Subsequence Length (hours)

• Even if we know the exact duration of the anomaly, it would still be challenging to predict the appropriate window size to detect it.
• For example, the battery change anomaly is two hours long, yet it reveals itself best at a scale of ten hours.

Battery change (2 hours)

10 hours

Can we bypass the difficulties by testing all values?

• All the previously described limitations have a straightforward solution: simply find anomalies for every possible subsequence length!
• However, the computational speed of the “test-all-lengths” method seems to be too slow to be practical.

Outline

• Motivation
• The proposed method: MADRID
• Empirical Evaluation
• Conclusion

MERLIN And DAMP Refined Iteratively on Demand

• In this work, we propose a novel TSAD method, called MADRID, which solves all the problems in the previous slides.
• Specifically, MADRID has the following two key properties:
• MADRID is absolutely fast to compute all-discords.

​

MERLIN And DAMP Refined Iteratively on Demand

• In this work, we propose a novel TSAD method, called MADRID, which solves all the problems in the previous slides.
• Specifically, MADRID has the following two key properties:
• MADRID is absolutely fast to compute all-discords.
• MADRID is able to produce very efficient anytime convergence, a property we have named a Hyper-Anytime Algorithm.
• The term “Hyper-Anytime Algorithm” means an algorithm that can converge to within 10% of the optimal answer, after using less than 10% of the time needed for full convergence.

​

MERLIN And DAMP Refined Iteratively on Demand

• In this work, we propose a novel TSAD method, called MADRID, which solves all the problems in the previous slides.
• Specifically, MADRID has the following two key properties:
• MADRID is absolutely fast to compute all-discords.
• MADRID is able to produce very efficient anytime convergence, a property we have named a Hyper-Anytime Algorithm.
• The term “Hyper-Anytime Algorithm” means an algorithm that can converge to within 10% of the optimal answer, after using less than 10% of the time needed for full convergence.
• MADRID exploits some ideas from the recently introduced DAMP algorithm^[2], which we'll review in the next four slides.

​

[2] Y. Lu, et al, “DAMP: accurate time series anomaly detection on trillions of datapoints and ultra-fast arriving data streams,” Data Mining and Knowledge Discovery, pp. 1–43, 2023. 

• DAMP is an ultra-fast time-series anomaly detection algorithm that operates on a fixed sliding window size. 
• On a never-ending sliding window, DAMP takes in the current subsequence, and looks backwards for its nearest neighbor in its entire history (training data). This makes discords particularly robust to concept drift, as newly ingested data instantly becomes part of the training data.

​

Brief Review of DAMP I

0

500

1000

1500

2000

2500

Left-aMP

(Partly computed)

Now

Training Data

Current Subsequence

Time Series

Brief Review of DAMP II

• We chose DAMP as the core subroutine of MADRID, because
• DAMP inherits all the advantages of time series discords - it is simple, requires a single parameter and performs at superhuman levels.
• DAMP is not confused by repeated anomalies (twin-freaks) and can handle concept drift in time series.
• DAMP achieves state-of-the-art performance on several benchmark datasets including the Hexagon ML/UCR Anomaly Detection datasets.
• MADRID also inherits all the benefits of DAMP listed above.
• DAMP employs two key strategies to speed up the process of anomaly detection, which are also adopted by MADRID: 
• Iterative doubling: DAMP only looks back as far as it needs to (early abandoning).
• Forward pruning: DAMP can “peek” ahead to prune the future subsequences that are unlikely to be a discord.

​

DAMP only looks back as far as it needs to

0

500

1000

1500

2000

2500

Left-aMP

(Partly computed)

Time Series

Current Subsequence

Now

Best-So-Far = 2.1

Double the length. Now look back this far.

If DAMP finds a subsequence whose distance from the current subsequence is less than Best-So-Far, stop.

DAMP find a nearest neighbor!

1. Stop searching.
2. Update the Left-aMP score.

This process is “iterative doubling”.

DAMP can “peek” ahead to prune unqualified future subsequences

Look ahead a bit.

If there are future subsequences whose distance from the current subsequence is less than Best-So-Far, they will be pruned and not processed in the future.

0

500

1000

1500

2000

2500

3000

3500

4500

5000

Distance Profile

Best-So-Far = 2.1

Current Subsequence

Time Series

✄

✄

4000

The distance between these two subsequences and the current subsequence is less than 2.1.

• Future subsequences similar to the current subsequence are unlikely to be a discord.

This process is “forward pruning”.

MADRID is absolutely fast to compute all-discords

• The efficiency of DAMP greatly depends upon the Best-So-Far (BSF) discord score. The larger it is, the more effective the pruning is.
• If we set the initial BSF to a value just slightly below the final BSF before starting DAMP, this can reduce the absolute time to compute discords.
• How can we determine this initial BSF?

​

​

​

MADRID is absolutely fast to compute all-discords

• This is what the MADRID’s data structure, the multi-length discord table M, initially looks like.

multi-length discord table M

MADRID is absolutely fast to compute all-discords

• Each row of the multi-length discord table M is a Left-aMP.

Left-aMP for m=8

MADRID is absolutely fast to compute all-discords

• Each row of the multi-length discord table M is a Left-aMP.
• MADRID incrementally increases the size of m, repeatedly invoking DAMP to compute the Left-aMP row by row.

​

Left-aMP for m=8

MADRID is absolutely fast to compute all-discords

• Each row of the multi-length discord table M is a Left-aMP.
• MADRID incrementally increases the size of m, repeatedly invoking DAMP to compute the Left-aMP row by row.

Left-aMP for m=9

MADRID is absolutely fast to compute all-discords

• Each row of the multi-length discord table M is a Left-aMP.
• MADRID incrementally increases the size of m, repeatedly invoking DAMP to compute the Left-aMP row by row.

Left-aMP for m=10

MADRID is absolutely fast to compute all-discords

• The left side is the table’s meta-data.

meta-data

MADRID is absolutely fast to compute all-discords

• Meta-data stores the information of the top discord for each row.
• For example, the red cell represents the top discord at m=8.
• Discord: the highest discord score.
• Loc: anomaly location.
• m: anomaly length.

MADRID is absolutely fast to compute all-discords

• Recall that to improve the absolute speed for computing discords, we need a large initial BSF.
• To do so, when MADRID completes the calculation for row m and is about to compute m+1…

MADRID is absolutely fast to compute all-discords

• MADIRD goes to the anomaly location Loc, increases the size of m by one and compute the discord score.
• In general, the discord score of cell M_[Loc,m] will be highly correlated with cell M_[Loc,m+1].

MADRID is absolutely fast to compute all-discords

• This gives MADRID a large initial BSF discord score before computing the next row.
• We call this optimization warm-start.

This value may be increased in the subsequent calculation.

MADRID is absolutely fast to compute all-discords

• The task involves computing the multi-length discord table M for a slightly noisy sine wave of length 8,192, with minL = 128, maxL = 768, and step size S = 1. This means that there are a total of 5,251,072 cells in the table that need to be processed.
• We start with the pure brute force algorithm and incrementally add our 3 optimizations and observe the execution time of these algorithms.

Wall clock time (seconds)

MADRID is absolutely fast to compute all-discords

• Each optimization contributes to speed up, reducing what would have taken 15.5 hours for 5 million data points to just 16 minutes.
• Compared with pure DAMP, MADRID with warm-start optimization (red curve) is 1.5 times faster.

MADRID is a Hyper-Anytime Algorithm

• We theoretically defined a hierarchy to reference the performance of anytime algorithms.
• Based on the convergence performance of anytime algorithms, we defined five different hierarchical categories.
• For instance, Ultra-Anytime refers to a 70%-efficient algorithm, meaning it converges to within 30% of the final solution using only 30% of the time required by the batch algorithm. The definitions for other levels follow a similar logic.

MADRID is a Hyper-Anytime Algorithm

• Despite the warm-start optimization, MADRID is essentially a batch-only algorithm as it sequentially processes the cells in the table M row by row.
• The red curve shows it converges to the final solution slightly better than linearly.
• Can MADRID algorithm be adapted to a Hyper-Anytime Algorithm that converges to within 10% of the final solution using only 10% of the time required by the batch algorithm?

Wall clock time (seconds)

MADRID is a Hyper-Anytime Algorithm

• MADRID employs an additional initialization strategy to quickly estimate the scores and locations of all-discords early in its execution.
• We start with an empty multi-length discord table M.

MADRID is a Hyper-Anytime Algorithm

• Since DAMP is fast for a single length, we can take this advantage to quickly compute three representative discords.
• The most representative discords we choose here are at the maximum length (24), the minimum length minL (8), and the mid-length (16).

* Cells in gray represent those visited by DAMP, those in red highlight the top discords.

​

MADRID is a Hyper-Anytime Algorithm

• Discord scores/locations are also updated in the meta-data.
• With information about the three representative discords, we can make quick and reasonable inferences about the remaining discords.

meta-data

MADRID is a Hyper-Anytime Algorithm

• We compute the scores for all cells in the same columns as the three representative discords.
• The discord scores of these yellow cells should be very close to the highest discord score, as the discord score of cell M_[Loc,m] will be highly correlated with cell M_[Loc,m+1].

MADRID is a Hyper-Anytime Algorithm

• Evaluate the three cells in each row, select the one with the highest value as the approximate solution for that row, and update the metadata.
• After this initialization process, MADRID initiates warm-start DAMP to calculate the exact scores and positions of top discords row by row.

* The red fonts in meta-data represent exact values that match the final results and will not be modified in subsequent computations, while the black fonts are approximations, which may be corrected in subsequent calculations.

max{cell1, cell2, cell3}

MADRID is a Hyper-Anytime Algorithm

• Consider two synthetic datasets with lengths of 100,000 and 1,000,000, both being slightly noisy sine waves.
• We intentionally introduced concept drift in both datasets, their periodicity increases over time.
• In both cases, we used the first 50,000 datapoints for training and embedded three visually obvious anomalies of different lengths between 50,000 and 60,000.

The three embedded anomalies

Quality of solution

0

4000

0%

100%

Wall clock time (seconds)

Warm-start DAMP

Pure DAMP

MASS Brute Force

Pure brute force (NN)

(Zoom-in)

MADRID is a Hyper-Anytime Algorithm

• Recall that in terms of absolute speed, warm-start DAMP is already much faster than the application of pure DAMP.

MADRID is a Hyper-Anytime Algorithm

• However, the convergence of warm-start DAMP is not optimal, since it accesses the table M row by row in sequence. Within our established hierarchy of anytime algorithms, we expect the convergence of our algorithms to improve to the Hyper-Anytime level.
• Let‘s see how well MADRID converges after applying the additional initialization step.

​

100%

0%

Hyper-Anytime

Percentage of Computational Resource

Percentage of Computational Resource

0

100%

Warm-start DAMP

Quality of solution

0%

100%

MADRID is a Hyper-Anytime Algorithm

• In both cases, after MADRID completed only ~1.55% of the total computation, it successfully converged to within 10% of the final solution, confirming its robust anytime performance.
• Overlaying MADRID's convergence plot onto the nomenclature template demonstrates that MADRID is a Hyper-Anytime Algorithm.
• MADRID also exhibits excellent scalability, with better convergence as the dataset size increases.

Percentage of Computational Resource

0

100%

Warm-start DAMP

MADRID

MADRID

Percentage of Computational Resource

0

100%

Warm-start DAMP

100%

0%

Hyper-Anytime

Percentage of Computational Resource

100,000

Datapoints

1,000,000

Datapoints

Quality of solution

0%

100%

Outline

• Motivation
• The proposed method: MADRID
• Empirical Evaluation
• Conclusion

Comparison of MADRID with state-of-the-art TSAD methods

• We compared MADRID with two most cited deep learning methods and two Matrix Profile-based methods on the 100K synthetic dataset.