Recherche approximative de plus proches voisins efficace et sûre

Benjamin Mathon (1) , Teddy Furon (1) , Laurent Amsaleg (1) , Julien Bringer (2)

1 TEXMEX - Multimedia content-based indexing
2 Morpho

Cette communication présente une méthode de recherche approximative des plus proches voisins (APPV) modérément sûre mais très efficace. Nous partons d'une méthode de recherche APPV se basant sur des distances entre données quantifiées calculées à l'avance : les PQ-codes. Se plaçant dans le modèle honnête mais curieux dans lequel le serveur et l'utilisateur suivent le protocole mais sont capables de déduire de l'information sur les données transitées, nous analysons les menaces en terme de fuite d'information pour cette méthode. Pour empêcher une reconstruction du signal requête par le serveur, nous proposons une version des PQ-codes utilisant deux quantificateurs distincts pour le serveur et l'utilisateur. Les avantages de notre méthode sont (a) une perte significative d'information de la requête par le serveur (b) une base de taille fixée (c) aucune perte dans la qualité de la recherche.

Domaines: Théorie de l'information [cs.IT]; Théorie de l'information et codage [math.IT]; Traitement du signal et de l'image [eess.SP]; Traitement du signal et de l'image [eess.SP]

Benjamin Mathon, Teddy Furon, Laurent Amsaleg, Julien Bringer. Recherche approximative de plus proches voisins efficace et sûre. GRETSI, Sep 2013, Brest, France. pp.ID238. ⟨hal-00823879v2⟩