A large-scale performance study of cluster-based high-dimensional indexing
Authors:
Open Access
- 29 October 2010
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 31-36
Abstract
International audienceHigh-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 pointsKeywords
This publication has 9 references indexed in Scilit:
- Lost in quantization: Improving particular object retrieval in large scale image databases2008
- Finding near neighbors through cluster pruning2007
- A Binning Scheme for Fast Hard Drive Based Image Search2007
- Object retrieval with large vocabularies and fast spatial matching2007
- Scalability of local image descriptors2006
- Scalable Recognition with a Vocabulary Tree2006
- The Quality vs. Time Trade-off for Approximate Image Descriptor Search2005
- Distinctive Image Features from Scale-Invariant KeypointsInternational Journal of Computer Vision, 2004
- An efficient parts-based near-duplicate and sub-image retrieval system2004