TR2022-040

Algorithms for Fast Computation of Matrix Profiles of Time Series Under Unnormalized Euclidean Distances


    •  Zhang, J., Nikovski, D.N., "Algorithms for Fast Computation of Matrix Profiles of Time Series Under Unnormalized Euclidean Distances", International Conference on Applied Statistics and Data Analytics, April 2022.
      BibTeX TR2022-040 PDF
      • @inproceedings{Zhang2022apr,
      • author = {Zhang, Jing and Nikovski, Daniel N.},
      • title = {Algorithms for Fast Computation of Matrix Profiles of Time Series Under Unnormalized Euclidean Distances},
      • booktitle = {International Conference on Applied Statistics and Data Analytics},
      • year = 2022,
      • month = apr,
      • url = {https://www.merl.com/publications/TR2022-040}
      • }
  • MERL Contact:
  • Research Area:

    Data Analytics

Abstract:

We propose a novel algorithm to compute the Matrix
Profile (MP) under the unnormalized distance (useful for value-based similarity search) using two suitable data structures
(double-ended queue and segment tree). The algorithm has the same time/space complexity as the state-of-the-art algorithm for typical MP computation under the normalized `2 distance (useful for shape-based similarity search). We validate its efficiency and effectiveness through extensive numerical experiments and two real-world applications – anomaly detection in the NYC taxi data, as well as in a simulated communication network.
Depending on data and applications, we show that the valuebased similarity search could perform almost equally well as the shape-based similarity search, and sometimes outperform the latter significantly.
Index Terms—Matrix Profile, unnormalized Euclidean distance, double-ended queue, segment tree, anomaly detection