Interrogation de bases de données de graphes : Une approche basée sur un skyline par similarité

Katia Abbaci (1) , Allel Hadjali (1) , Ludovic Liétard (1) , Daniel Rocacher (1)

1 PILGRIM - Gradedness, Imprecision, and Mediation in Database Management Systems

L'un des problèmes fondamentaux des bases de données de graphes est la recherche de graphes similaires à une requête à graphe. Les approches existantes traitant ce problème s'appuient, généralement, sur une seule mesure de similarité entre les structures de graphes. Dans cet article, nous proposons une approche où la similarité entre graphes n'est plus un scalaire unique mais un vecteur de scalaires. Pour cela, nous utilisons le concept de skyline par simi- larité d'une requête à graphe défini par un sous-ensemble de graphes, de la base de données interrogée, qui sont les plus similaires à la requête au sens de Pa- reto. L'idée est d'effectuer une comparaison multidimensionnelle entre graphes en termes de d mesures de similarité locales et d'identifier les graphes qui sont maximalement similaires au sens d'une relation de dominance par similarité. Une méthode pour raffiner le résultat de la recherche est aussi discutée en s'ap- puyant sur le critère de diversité entre les graphes.

Domaines: Base de données [cs.DB]; Recherche d'information [cs.IR]

Katia Abbaci, Allel Hadjali, Ludovic Liétard, Daniel Rocacher. Interrogation de bases de données de graphes : Une approche basée sur un skyline par similarité. Conférence Maghrébine sur l'Extraction et la Gestion des Connaissances (EGC-M), Dec 2010, Algeria. pp.46-57. ⟨hal-00670672⟩