Graph index based query-by-example search on a large speech data set

This paper presents a neighborhood graph index approach for query-by-example search using dynamic time warping (DTW) on Gaussian mixture model (GMM) posteriorgram sequences. The approach is intended to achieve a significant speed-up of a spoken term detection (STD) task for resource-limited situations. The proposed method employs a degree-reduced k-nearest neighbor (k-DR) graph as an index. A set of k-DR graphs is pre-constructed off-line from a large number of GMM posteriorgram sequences. Given a query posteriorgram sequence, one k-DR graph is selected from the set as the index. By applying a newly introduced combination of greedy-search (GS) and breadth-first search (BFS) algorithms to the selected k-DR graph index, the proposed method efficiently achieves query-by-example STD. Experimental results on the MIT lecture corpus demonstrate that the proposed method works much faster than a state-of-art method by more than one order magnitude, keeping almost the same precision.