Scaling Group Testing Similarity Search

Ahmet Iscen 1 Laurent Amsaleg 1 Teddy Furon 1
1 LinkMedia - Creating and exploiting explicit links between multimedia fragments
Inria Rennes – Bretagne Atlantique , IRISA-D6 - MEDIA ET INTERACTIONS
Abstract : The large dimensionality of modern image feature vectors, up to thousands of dimensions, is challenging the high dimensional indexing techniques. Traditional approaches fail at returning good quality results within a response time that is usable in practice. However, similarity search techniques inspired by the group testing framework have recently been proposed in an attempt to specifically defeat the curse of dimensionality. Yet, group testing does not scale and fails at indexing very large collections of images because its internal procedures analyze an excessively large fraction of the indexed data collection. This paper identifies these difficulties and proposes extensions to the group testing framework for similarity searches that allow to handle larger collections of feature vectors. We demonstrate that it can return high quality results much faster compared to state-of-the-art group testing strategies when indexing truly high-dimensional features that are indeed hardly indexable with traditional indexing approaches.
Type de document :
Communication dans un congrès
ACM International Conference on Multimedia Retrieval 2016 , Jun 2016, New York, United States. <10.1145/2911996.2912010>
Liste complète des métadonnées


https://hal.inria.fr/hal-01304287
Contributeur : Ahmet Iscen <>
Soumis le : mardi 19 avril 2016 - 14:58:58
Dernière modification le : mercredi 2 août 2017 - 10:07:12
Document(s) archivé(s) le : mercredi 20 juillet 2016 - 13:10:01

Fichier

ScalableGroupTesting_hal.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Ahmet Iscen, Laurent Amsaleg, Teddy Furon. Scaling Group Testing Similarity Search. ACM International Conference on Multimedia Retrieval 2016 , Jun 2016, New York, United States. <10.1145/2911996.2912010>. <hal-01304287>

Partager

Métriques

Consultations de
la notice

329

Téléchargements du document

175