This C++ library implements fast nearest-neighbor retrieval under the dynamic time warping (DTW). This library includes the dynamic programming solution, a fast implementation of the LB_Keogh lower bound, as well as a improved lower bound called LB_Improved. This library was used to show that LB_Improved can be used to retrieve nearest neighbors three times on several data sets including random walks time series or shape time series.

Code sample:

   #include "dtw.h"
  (...)
  // compute the DTW between two vectors:
  double fd = mDTW.fastdynamic(x,y);
  // to seek a nearest neighbor, construct a LB_Improved object:
  LB_Improved pruner = new LB_Improved(targetvector, constraint);// constraint can be 10% of vector length
  // then repeatedly call the test method, which returns the best distance so far
  double bestdistancesofar = pruner.test(candidate);
  // the test method is typically much cheaper than a full DTW

The library assumes that your time series have the same length. If they don't, you need to preprocess them (perhaps with linear interpolation) so that they have the same length.

Reference:

- Daniel Lemire, Faster Retrieval with a Two-Pass Dynamic-Time-Warping Lower Bound, Pattern Recognition Volume 42, Issue 9, September 2009, Pages 2169-2180.

Requirement:

- Spatial Index Library (for R-tree)

Recommended:

- SWIG (for interaction)

Operating system:

- Built under MacOS 10.4. Makefile provided. The library can be adapted to any Unix-like system (including Linux)