Initialization of dynamic time warping using tree-based fast Nearest Neighbor

Abstract

An efficient way to perform Dynamic Time Warping (DTW) search is by using the LBKeogh lower bound, which can eliminate a large number of candidate vectors out of the search process. Although effective, LBKeogh begins the DTW search using the first candidate vector, which is typically arbitrarily chosen. In this work, we propose initializing the LBKeogh-based DTW search using the Euclidean Distance Nearest Neighbor, derived by a fast tree-based Nearest Neighbor technique. Our experimental results suggest that, on one hand, this simple NN-based approach is quite accurate for trajectory classification of digit and letter gesturing and can initialize the DTW search very efficiently, thus requiring about 20% less search time than existing DTW implementations without any drop in recognition accuracy. © 2016 Elsevier B.V. All rights reserved.