A Large-Scale Performance Study of Cluster-Based High-Dimensional Indexing
Résumé
High-dimensional clustering is a method that is used by some content-based image retrieval systems to partition the data into groups; the groups (clusters) are then indexed to accelerate the processing of queries. Recently, the Cluster Pruning approach was proposed as a very simple way to efficiently and effectively produce such clusters. While the original evaluation of the algorithm was performed within a text indexing context at a rather small scale, its simplicity and performance motivated us to study its behavior in an image indexing context at a much larger scale. We experiment with two collections of 72-dimensional state-of-the-art local descriptors, the larger collection containing 189 million descriptors. This paper summarizes the results of this study and shows that while the basic algorithm works fairly well, three extensions can dramatically improve its performance and scalability, accelerating both query processing and the construction of clusters, making Cluster Pruning a promising basis for building large-scale systems that require a clustering algorithm.
Le clustering en grandes dimensions est une méthode employée par certains systèmes de recherche d'images par le contenu pour partitionner l'espace en groupes. Les groupes sont ensuite indexés pour accélérer le traitement des requêtes. Récemment, une approche dite ``Cluster Pruning'' a été proposée comme permettant l'obtention simple, rapide et efficace de ces groupes. Alors que son évaluation originale s'est effectuée dans un contexte d'indexation de textes et à une échelle réduite, sa simplicité et ses performances ont été une forte motivation pour étudier son comportement à bien plus grande échelle, et dans un contexte image. Nous menons des expérimentations où sont utilisés des descripteurs locaux d'image appartenant à l'état de l'art et de dimension 72. Nous traitons plusieurs collections de descripteurs, dont la plus grande en contient 189 millions. Cet article présente une synthèse des résultats de cette étude et montre que l'algorithme original fonctionne relativement bien. Toutefois, trois extensions simples permettent d'améliorer de manière très importante ses performances et son aptitude à passer à l'échelle, en accélérant tant le traitement des requêtes que le temps de construction des groupes. Dotée de ces extensions, l'approche ``Cluster Pruning'' devient alors une brique essentielle pouvant servir aux systèmes grande échelle nécessitant la création de groupes de points.
Domaines
Multimédia [cs.MM]
Origine : Fichiers produits par l'(les) auteur(s)