FastDTW Distance

Introduction

FastDTW (Fast Dynamic Time Warping) is an approximation algorithm that provides a linear time complexity solution to compute the similarity between two time series. While maintaining a high degree of accuracy comparable to the traditional DTW algorithm, FastDTW significantly reduces the computational overhead, making it particularly suitable for analyzing large-scale time series datasets.

The algorithm addresses the quadratic time and space complexity limitations of traditional DTW through a multilevel approach that combines coarsening, refinement, and radius calculations to find an approximate optimal warping path.

Algorithm Overview

FastDTW operates through three main steps:

  1. Coarsening: Recursively creating a lower-resolution version of the time series by averaging adjacent points

  2. Low-Resolution Path Finding: Computing the warping path at the lowest resolution

  3. Refinement: Projecting and refining the path to higher resolutions while constraining the search to a narrow corridor around the projected path

Mathematical Definition

For two time series X and Y, FastDTW uses a radius parameter r and operates recursively:

\[\begin{split}FastDTW(X, Y, radius) = \begin{cases} DTW(X, Y) & \text{if } length(X) \leq radius \\ refinement(FastDTW(coarsen(X), coarsen(Y), radius)) & \text{otherwise} \end{cases}\end{split}\]

where: - \(coarsen(X)\) reduces the resolution of time series X - \(refinement(path)\) projects the warping path to a higher resolution - \(radius\) defines the width of the search corridor

Complexity Analysis

  • Time Complexity: O(N)

  • Space Complexity: O(N)

where N is the length of the input sequences.

Properties

  1. Approximate Solution: Provides a near-optimal warping path

  2. Linear Complexity: Achieves O(N) time complexity versus O(N²) for traditional DTW

  3. Radius Parameter: Controls the trade-off between accuracy and speed

  4. Multilevel Approach: Uses multiple resolutions to find the optimal path efficiently

Academic References

  1. Salvador, S., & Chan, P. (2007). “Toward accurate dynamic time warping in linear time and space.” Intelligent Data Analysis, 11(5), 561-580.

  2. Müller, M., et al. (2016). “Dynamic Time Warping.” In Information Retrieval for Music and Motion (pp. 69-84). Springer.

Use Cases

FastDTW is particularly valuable in:

  • Real-time sequence matching

  • Large-scale time series mining

  • Gesture recognition

  • Speech recognition

  • Financial data analysis

  • IoT sensor data processing

Implementation Details

In the distancia package, FastDTW is implemented with the following key parameters:

  • radius: Controls the accuracy vs. speed trade-off

  • min_window_size: Minimum size of the coarsened time series

  • dist_method: Distance measure used for point-to-point comparisons

Example Usage

from distancia import FastDTW

# Initialize FastDTW with radius parameter
fastdtw = FastDTW(radius=30)

# Calculate distance between two time series
distance = fastdtw.calculate(series1, series2)

Conclusion

FastDTW represents a significant advancement in time series analysis by providing a highly efficient approximation of Dynamic Time Warping. Its linear time complexity makes it practical for large-scale applications while maintaining accuracy comparable to traditional DTW. The algorithm’s adaptability through its radius parameter allows users to fine-tune the trade-off between computational efficiency and accuracy based on their specific needs.

Note

While FastDTW provides an approximate solution, its accuracy is generally sufficient for most practical applications, and its efficiency makes it the preferred choice for large-scale time series analysis.

See Also

  • DTW

  • MDTW