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

Romain Tavenard 1 Laurent Amsaleg 1 Hervé Jégou 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, in order to avoid exhaustive search, 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 seriously impacting the search quality.
Type de document :
Rapport
[Research Report] RR-7387, INRIA. 2010
Liste complète des métadonnées


https://hal.inria.fr/inria-00519490
Contributeur : Romain Tavenard <>
Soumis le : mardi 21 septembre 2010 - 09:48:31
Dernière modification le : vendredi 13 janvier 2017 - 14:20:18
Document(s) archivé(s) le : jeudi 30 juin 2011 - 13:29:19

Fichiers

RR-7387.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00519490, version 1
  • ARXIV : 1009.4739

Citation

Romain Tavenard, Laurent Amsaleg, Hervé Jégou. Balancing clusters to reduce response time variability in large scale image search. [Research Report] RR-7387, INRIA. 2010. <inria-00519490>

Partager

Métriques

Consultations de
la notice

260

Téléchargements du document

173