Matrix Profile

The core computational kernel that calculates the z-normalized Euclidean distance between a query subsequence and every other subsequence in a time series. This is performed using the MASS (Mueen's Algorithm for Similarity Search) algorithm, which leverages Fast Fourier Transforms to compute all sliding dot products in O(n log n) time. The result is a vector of distances that forms one column of the Matrix Profile, enabling the identification of the nearest non-self match for every subsequence.

A discord is a subsequence that has the maximum distance to its nearest non-self match, making it the most anomalous pattern in a time series. The Matrix Profile annotates every subsequence with this distance, so finding the top-K discords is a simple scan for the largest values. In financial fraud, a discord might represent an unusual burst of micro-transactions, a sudden change in spending velocity, or a transaction sequence that deviates from all historical behavioral templates.

A motif is a subsequence that has the minimum distance to its nearest non-self match, representing a repeated, conserved pattern. The Matrix Profile makes motif discovery trivial: scan for the smallest values. In financial contexts, motifs can reveal recurring legitimate behaviors—such as regular payroll deposits or subscription billing cycles—which can then be used to establish a baseline of normality against which discords are contrasted.

By analyzing the Matrix Profile Index—which stores the location of each subsequence's nearest neighbor—one can detect time series regimes, or abrupt changes in the underlying generative process. When the nearest neighbor for a subsequence is temporally distant, it signals a shift in dynamics. This is critical for detecting the onset of a new fraud campaign, where the statistical signature of transactions changes suddenly and persistently.

An extension that handles multivariate time series by computing a Matrix Profile over multiple dimensions simultaneously. Instead of a single distance, it maintains a vector of distances per dimension and selects the dimension that provides the best nearest neighbor for each subsequence. This is essential for financial fraud detection, where a single anomalous event may manifest across correlated streams: transaction amount, merchant category code, geolocation, and inter-transaction time.

STOMP (Scalable Time series Ordered-search Matrix Profile) is the optimized algorithm for computing the Matrix Profile exactly. It exploits the fact that distance profiles for adjacent subsequences share significant computation, using a recursive update formula to compute the next column in O(1) amortized time after the first O(n log n) initialization. This makes it feasible to compute the full Matrix Profile for streaming financial transaction data with millions of data points.

A discord is the subsequence within a time series that has the maximum distance to its nearest non-self match. It represents the most statistically significant anomaly in the dataset.

• Definition: argmax(min(D[i,j])) for all non-trivial matches
• Financial Application: Identifies a single fraudulent transaction sequence that is maximally different from all legitimate spending patterns
• Key Property: Unlike threshold-based methods, discords are parameter-free and do not require a pre-defined anomaly model
• Example: In credit card transactions, a discord might reveal a sudden high-value purchase in a foreign country completely unlike the cardholder's history

A motif is the subsequence pair with the minimum distance in a time series, representing the most repeated or conserved pattern. It is the conceptual inverse of a discord.

• Definition: argmin(D[i,j]) for non-overlapping subsequences
• Financial Application: Identifies recurring legitimate transaction patterns, such as regular monthly bill payments or salary deposits
• Top-K Motifs: The algorithm can efficiently extract the K most similar repeating subsequences to build a dictionary of normal behaviors
• Utility: Motifs serve as the baseline for defining normality, against which discords are contrasted

Scalable Time series Ordered-search Matrix Profile (STOMP) is an exact, ultra-fast algorithm for computing the Matrix Profile. It exploits the redundancy in distance calculations between overlapping subsequences.

• Mechanism: Uses the Fast Fourier Transform (FFT) to compute dot products between a query and all sliding windows in O(n log n) time
• Advantage: Eliminates the need for an index structure; all calculations are performed in-place on the raw time series
• Financial Relevance: Enables real-time discord discovery on high-velocity payment streams without pre-training
• Derivative: The STAMP algorithm is the anytime, parallelizable predecessor; SCRIMP++ is an anytime diagonal version

MASS is the foundational computational kernel underlying all modern Matrix Profile algorithms. It computes the z-normalized Euclidean distance between a query subsequence and every possible subsequence in a much longer time series.

• Core Insight: Uses convolution and cumulative sum pre-computation to calculate all sliding dot products in one pass
• Distance Metric: D[i] = sqrt(2m * (1 - (Q·T[i] - m*μ_Q*μ_T[i]) / (m*σ_Q*σ_T[i])))
• Significance: MASS is the engine that makes STOMP and STAMP possible; it is the most optimized known method for this specific distance computation
• Financial Use: Rapidly scans historical transaction logs to find all occurrences similar to a newly flagged fraudulent pattern

An extension of the Matrix Profile to multivariate time series, enabling the discovery of discords and motifs across multiple correlated dimensions simultaneously.

• Challenge: Naively combining dimensions loses the semantic meaning of the relationship between variables
• Solution: Computes the Matrix Profile for each dimension independently, then combines them using a user-defined aggregation function or by finding the minimum distance across all dimensions
• Financial Application: Analyzes transaction amount, merchant category code, and geolocation jointly to detect anomalies where only the combination of features is suspicious
• MDL-based Variant: Uses Minimum Description Length to automatically select the most informative subset of dimensions

An annotation vector is a user-defined or algorithmically derived sequence that masks or weights regions of a time series to prevent trivial matches from dominating the Matrix Profile.

• Purpose: Suppresses known patterns (e.g., weekends, holidays) so the algorithm focuses on discovering novel anomalies
• Financial Context: An annotation vector can encode known fraud attack periods, system downtime, or recurring settlement cycles to prevent the model from flagging expected deviations
• Semantic Separation: Allows the separation of "interesting" anomalies from "known" anomalies, drastically reducing false positives in production fraud systems
• Implementation: Applied as a multiplicative or additive penalty to the distance matrix before extracting discords