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.
Bibliographic reference. Zhang, Yaodong / Glass, James (2011): "A piecewise aggregate approximation lower-bound estimate for posteriorgram-based dynamic time warping", In INTERSPEECH-2011, 1909-1912.