INTERSPEECH 2011 12th Annual Conference of the International Speech Communication Association Florence, Italy August 27-31. 2011

A Piecewise Aggregate Approximation Lower-Bound Estimate for Posteriorgram-Based Dynamic Time Warping

Yaodong Zhang, James Glass

MIT, USA

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.

Full Paper

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.