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

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)