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