Abstract
We introduce a clustering method that combines the flexibil- ity of Gaussian mixtures with the scaling properties needed to construct visual vocabularies for image retrieval. It is a variant of expectation- maximization that can converge rapidly while dynamically estimating the number of components. We employ approximate nearest neighbor search to speed-up the E-step and exploit its iterative nature to make search incremental, boosting both speed and precision. We achieve supe- rior performance in large scale retrieval, being as fast as the best known approximate k-means.