Les algorithmes top-k dans un contexte de recherche approximative par arrêt prématuré

Recherche approximative par arrêt prématuré : motivation

Comme nous l’avons indiqué dans le chapitre 1, plusieurs techniques sont proposées pour une recherche top-k approximative. Nous nous intéressons ici aux méthodes qui permettent, si besoin, de calculer le résultat exact. Plus précisément, nous considérons l’approximation par arrêt prématuré de l’exécution, avec retour d’un ensemble de k candidats susceptibles de former le top-k. Cette approche a l’avantage de la flexibilité, car elle permet d’allouer des durées d’exécution variables en fonction de la précision souhaitée, voire continuer jusqu’à la solution exacte. Cette technique est utilisée dans l’algorithme T Aθ [Fagin et al., 2002], proposée comme une variante de TA permettant une recherche top-k approximative. La différence entre les algorithmes TA et T Aθ se situe au niveau de la condition d’arrêt. Cette dernière est relaxée avec la valeur θ > 1, et l’algorithme s’arrête quand, au moins k candidats ont des scores supérieurs à Uunseen/θ. Si θ = 1, nous obtenons l’algorithme TA.

Par la baisse du seuil d’un facteur θ, T Aθ produit la même exécution que TA, à part l’arrêt, qui est réalisé plus tôt. Cette méthode produit une θ-approximation du top-k exact calculé dans TA : si nous considérons Ka l’ensemble des objets retournés par l’algorithme T Aθ, nous avons : ∀x ∈ Ka, ∀y /∈ Ka, θ × score(x) ≥ score(y), où les scores sont considérés dans l’intervalle [0, 1]. Définition 4. (θ − approximation) Étant donnée une requête top-k q sur une Base de Données D et une valeur θ > 1, le résultat Pk,θ(q) d’une recherche approximative du top-k est appelé θ-approximation, si, pour tout x ∈ Pk,θ(q) et pour tout y /∈ Pk,θ(q), nous avons θ × score(x) ≥ score(y). Notre objectif est de généraliser l’approche utilisée dans l’algorithme T Aθ dans un contexte de top-k avec des scores incomplets, et dans le cadre général de GF afin de pouvoir appliquer cette méthode à n’importe quel algorithme top-k.

Recherche approximative dans le cadre GF

Dans cette section, nous proposons une adaptation de la recherche approximative par arrêt prématuré au cadre général GF. L’objectif est de profiter de la capacité de GF à exprimer tous les algorithmes top-k pour généraliser cette technique à n’importe quel algorithme. L’algorithme 4, présente le cadre GF dans un contexte θ-approximation. Dans les paramètres d’entrée, θ est ajouté à la requête q et à l’ensemble des sources S. Aussi, les scores de chaque source Sj sont dans l’intervalle [0, maxj ] afin de pouvoir garder la même définition de la θ-approximation. Seule la condition d’arrêt change dans ce cas.

Nous avons vu dans le chapitre 2, que la condition d’arrêt permettant un résultat top-k exact avec des scores incomplets est donnée par la formule 2.2. Si nous considérons une solution approximative Ka composée de k candidats à un instant t de l’exécution d’un algorithme top-k dans le cadre GF, alors leurs scores sont éventuellement incomplets. Dans ce cas, la condition d’arrêt permettant de dire avec certitude que l’ensemble Ka est une θ-approximation du résultat exact, quel que soit le score exact de ces candidats, est donnée par le théorème suivant : Théorème 1. Une solution approximative Ka composée de k candidats à un moment de l’exécution d’un algorithme top-k, ayant des scores éventuellement incomplets, est sûrement une θ-approximation du top-k exact, ssi :

Évaluation de la qualité du résultat approximatif

Dans le contexte de GF, pour estimer la qualité d’une solution approximative retournée par un algorithme top-k, nous proposons une mesure de distance basée sur deux principes : • Dans le top-k, l’ordre et les scores finaux des candidats ne sont pas importants. • Parmi les k candidats retournés dans la solution approximative, uniquement les faux-positifs influencent et affectent la qualité. En d’autres termes, nous considérons que la qualité du résultat est donnée par la qualité des faux-positifs.