Fast similarity search on a large speech data set with neighborhood graph indexing

This paper presents a novel graph-based approach for solving a problem of fast finding a speech model acoustically similar to a query model from a large set of speech models. Each speech model in the set is represented by a Gaussian mixture model and dissimilarity from a GMM to another is measured with a Kullback-Leibler divergence (KLD). Conventional pruning techniques based on the triangle inequality for fast similarity search are not available because the model space with a KLD is not a metric space. We propose a search method that is characterized by an index of a degree-reduced nearest neighbor (DRNN) graph. The search method can efficiently find the most similar (closest) GMM to a query, exploring the DRNN graph with a best-first manner. Experimental evaluations on utterance GMM search tasks reveal a significantly low computational cost of the proposed method.