Les bases actuelles de données multimédia nécessitent des outils de plus en plus avancés pour pouvoir être parcourues avec efficacité. Dans ce contexte, la recherche en interaction avec un utilisateur est une approche qui permet de résoudre des requêtes à la sémantique complexe avec rapidité, sans pour autant nécessiter un haut niveau d'expertise utilisateur. Parmi les différents éléments intervenant dans la conception d'un système de recherche interactive, deux parties essentielles interviennent: l'indexation et la similarité entre les documents multimédia, et la gestion du processus interactif. Dans le contexte de la recherche multimédia par le contenu, on s'appuie sur des descriptions visuelles extraites automatiquement des documents. Suite à cette étape initiale, il est nécessaire de produire des structures de données, appelées index, ainsi qu'une métrique capable de comparer ces structures. Pour ce faire, nous proposons de représenter un document sous la forme d'un graphe, où chaque sommet du graphe représente une partie du document (région, point d'intérêt, ...) et chaque arête du graphe représente une relation entre deux parties du document. Puis, nous introduisons des métriques associées, sous la forme de fonctions noyaux sur graphes, qui permettent d'utiliser ces représentations complexes avec les méthodes d'apprentissages Hilbertiennes, telle que les SVMs. La gestion du processus interactif entre le système et un utilisateur a fait d'important progrès grâce à l'approche dite par apprentissage actif. Les premières approches proposent des critères pertinents pour la sélection de document à faire annoter par l'utilisateur, dans le but de trouver les documents recherchés au plus vite. Dans ce contexte, nous proposons d'aller plus loin en nous intéressant à la fabrication "en ligne" d'index et métriques associées en fonction de la nature de la recherche. En d'autres termes, nous proposons de remplacer le schéma traditionnel, où un unique index général est utilisé, par un schéma d'indexation active, où chaque utilisateur dispose d'un index dédié à sa requête.