TR2022-041

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

    •  Zhang, J., Nikovski, D.N., "Algorithms for Fast Computation of Pan Matrix Profiles of Time Series Under Unnormalized Euclidean Distances", International Conference on Applied Statistics and Data Analytics, April 2022.
      BibTeX TR2022-041 PDF
      • @inproceedings{Zhang2022apr3,
      • author = {Zhang, Jing and Nikovski, Daniel N.},
      • title = {Algorithms for Fast Computation of Pan 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-041}
      • }
  • MERL Contact:
  • Research Area:

    Data Analytics

Abstract:

We propose an approximation algorithm called
LINKUMP to compute the Pan Matrix Profile (PMP) under the unnormalized distance (useful for value-based similarity search) using double-ended queue and linear interpolation. The algorithm has comparable time/space complexities as the stateof-the-art algorithm for typical PMP computation under the normalized `2 distance (useful for shape-based similarity search).
We validate its efficiency and effectiveness through extensive numerical experiments and a real-world anomaly detection application.