A Group Testing Framework for Similarity Search in High-dimensional Spaces

Miaojing Shi 1 Teddy Furon 2, 3 Hervé Jégou 3, 2
2 TEXMEX - Multimedia content-based indexing
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, Inria Rennes – Bretagne Atlantique
3 LinkMedia - Creating and exploiting explicit links between multimedia fragments
IRISA-D6 - MEDIA ET INTERACTIONS, Inria Rennes – Bretagne Atlantique
Abstract : This paper introduces a group testing framework for detecting large similarities between high-dimensional vectors, such as descriptors used in state-of-the-art description of multimedia documents. At the crossroad of multimedia information retrieval and signal processing, we produce a set of group representations that jointly encode several vectors into a single one, in the spirit of group testing approaches. By comparing a query vector to several of these intermediate representations, we screen the large values taken by the similarities between the query and all the vectors, at a fraction of the cost of exhaustive similarity calculation. Unlike concurrent indexing methods that suffer from the curse of dimensionality, our method exploits the properties of high-dimensional spaces. It therefore complements other strategies for approximate nearest neighbor search. Our preliminary experiments demonstrate the potential of group testing for searching large databases of multimedia objects represented by vectors. We obtain a large improvement in terms of the theoretical complexity, at the cost of a small or negligible decrease of accuracy. We hope that this preliminary work will pave the way to subsequent works for multimedia retrieval with limited resources.
Type de document :
Communication dans un congrès
ACM Multimedia, Nov 2014, Orlando, United States. 2014, 〈http://acmmm.org/2014/〉. 〈10.1145/2647868.2654895〉
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger

Contributeur : Hervé Jégou <>
Soumis le : mardi 21 avril 2015 - 15:47:11
Dernière modification le : mardi 16 janvier 2018 - 15:54:26
Document(s) archivé(s) le : mercredi 19 avril 2017 - 02:22:15


Fichiers produits par l'(les) auteur(s)



Miaojing Shi, Teddy Furon, Hervé Jégou. A Group Testing Framework for Similarity Search in High-dimensional Spaces. ACM Multimedia, Nov 2014, Orlando, United States. 2014, 〈http://acmmm.org/2014/〉. 〈10.1145/2647868.2654895〉. 〈hal-01062531v3〉



Consultations de la notice


Téléchargements de fichiers