Balancing clusters to reduce response time variability in large scale image search - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2011

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

Romain Tavenard
Hervé Jégou
  • Fonction : Auteur
  • PersonId : 833473
Laurent Amsaleg

Résumé

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.
Fichier principal
Vignette du fichier
cbmi2011_preprint.pdf (218.76 Ko) Télécharger le fichier
Vignette du fichier
cbmi.png (11.04 Ko) Télécharger le fichier
tavenardCBMI11.pdf (108.92 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Format : Figure, Image
Format : Autre
Loading...

Dates et versions

inria-00576886 , version 1 (16-03-2011)
inria-00576886 , version 2 (17-06-2011)

Identifiants

  • HAL Id : inria-00576886 , version 2

Citer

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. ⟨inria-00576886v2⟩
526 Consultations
316 Téléchargements

Partager

Gmail Facebook X LinkedIn More