Balancing clusters to reduce response time variability in large scale image search

Romain Tavenard 1 Hervé Jégou 1 Laurent Amsaleg 1
1 TEXMEX - Multimedia content-based indexing
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, Inria Rennes – Bretagne Atlantique
Abstract : Many algorithms for approximate nearest neighbor search in high-dimensional spaces partition the data into clusters. At query time, for efficiency, an index selects the few (or a single) clusters nearest to the query point. Clusters are often produced by the well-known k-means approach since it has several desirable properties. On the downside, it tends to produce clusters having quite different cardinalities. Imbalanced clusters negatively impact both the variance and the expectation of query response times. This paper proposes to modify k-means centroids to produce clusters with more comparable sizes without sacrificing the desirable properties. Experiments with a large scale collection of image descriptors show that our algorithm significantly reduces the variance of response times without severely impacting the search quality.
Type de document :
Communication dans un congrès
International Workshop on Content-Based Multimedia Indexing (CBMI 2011), Jun 2011, Madrid, Spain. 2011
Liste complète des métadonnées

Littérature citée [1 références]  Voir  Masquer  Télécharger


https://hal.inria.fr/inria-00576886
Contributeur : Hervé Jégou <>
Soumis le : vendredi 17 juin 2011 - 10:36:05
Dernière modification le : lundi 2 octobre 2017 - 10:42:01
Document(s) archivé(s) le : lundi 5 décembre 2016 - 04:23:40

Identifiants

  • HAL Id : inria-00576886, version 2

Collections

Citation

Romain Tavenard, Hervé Jégou, Laurent Amsaleg. Balancing clusters to reduce response time variability in large scale image search. International Workshop on Content-Based Multimedia Indexing (CBMI 2011), Jun 2011, Madrid, Spain. 2011. 〈inria-00576886v2〉

Partager

Métriques

Consultations de
la notice

419

Téléchargements du document

231