A piecewise aggregate approximation lower-bound estimate for posteriorgram-based dynamic time warping
Yaodong Zhang, James Glass · 2011
In this paper, we propose a novel lower-bound estimate for dynamic time warping (DTW) methods that use an inner product distance on multi-dimensional posterior probability vectors known as posteriorgrams. Compared to our previous work, the new lower-bound estimate uses piecewise aggregate approximation (PAA) to reduce the time required for calculating the lower-bound estimate. We describe the PAA lower-bound construction process and prove that it can be efficiently used in an admissible K nearest neighbor (KNN) search. The amount of computational savings is quantified by a set of unsupervised spoken keyword spotting experiments. The results show that the newly proposed PAA lower-bound is able to speed up DTW-KNN search by 28 % without affecting the keyword spotting performance. Index Terms: dynamic time warping, lower-bound, posteriorgram 1.