La stratégie Breadth-Refine

Candidats

L’algorithme Breadth-Refine considère tout objet retourné suite à un accès séquentiel comme un candidat. Le candidat est représenté par un couple (identifiant, intervalle de score). Pour un candidat c, l’intervalle de score [L(c), U(c)], est maintenu tant que son score final n’est pas connu. Les valeurs L(c) et U(c) sont respectivement le score minimum possible et le score maximum possible que peut avoir le candidat c. Ces deux valeurs (bornes) sont calculées en agrégeant les scores du candidat dans les sources où il a été déjà retourné, avec les valeurs minimales et maximales des autres sources.
L(c) = F(l1; :::; lm), lj =score(c, Sj) si c a été retourné dans Sj, sinon lj = minj
U(c) = F(u1; :::; um), uj = score(c; Sj) si c a été retourné dans Sj, sinon uj = crtmaxj.
Dans la liste des candidats, nous notons Lk, respectivement Uk la kème valeur dans l’ordre décroissant de L(c), respectivement U(c) parmi les candidats. Si le nombre de candidats est inférieur à k, Lk et Uk prennent la valeur nil.
Un candidat est appelé viable s’il a des chances d’intégrer le top-k final. La condition de viabilité pour un candidat c est U(c) Lk. Avec la monotonicité il est simple de prouver qu’un candidat non viable restera ainsi jusqu’à la fin de l’exécution de l’algorithme et peut être supprimé. Nous appelons Uunseen la valeur maximale possible du score global d’un objet qui n’est pas encore un candidat (n’a pas été retourné par un accès trié). Initialement Uunseen = F(max1; :::; maxm).
Nous considérons deux ordres différents pour les candidats. Le premier permet d’avoir la liste des candidats triée dans l’ordre décroissant des scores maximum, nous appelons dans le reste du manuscrit l’ensemble des k meilleurs candidats dans cet ordre : Uk. Le deuxième classement permet d’avoir la liste des candidats triée dans l’ordre décroissant des scores minimum, nous appelons l’ensemble des k meilleurs candidats dans cet ordre Lk.

Cadre Générique pour le traitement des requêtes top-k

Nous proposons tout d’abord un cadre permettant d’exprimer tous les algorithmes top-k de la même manière, afin de pouvoir comparer les différentes stratégies utilisées. Le Cadre Générique (Generic Framework-GF) pour le traitement de requêtes top-k de sélection, considère un contexte où l’accès aux scores est coûteux, et chaque accès à une source permet de retourner un seul objet. Dans GF, nous consi-dérons un algorithme top-k comme une suite d’accès aux sources, où chaque accès permet de découvrir une information concernant un seul objet. Ce que nous appelons ici information est simplement le score local d’un objet de la base permettant de mesurer la pertinence de l’objet pour un critère donné. En dé-couvrant progressivement ces informations, chaque étape de l’algorithme doit être un pas de plus vers le résultat final top-k.
L’algorithme 2 présente GF, qui prend comme paramètres d’entrée une requête de sélection q et un ensemble de sources S (toutes les configurations de types d’accès sont possibles). La requête q spécifie la valeur de k (nombre d’objets à retourner dans le résultat), et la fonction d’agrégation monotone F, alors que l’ensemble des sources S matérialise les scores retournés par les prédicats de classement de la requête.
Dans GF , les algorithmes top-k maintiennent un ensemble de candidats avec leurs intervalles de scores, cet ensemble est initialement vide. Tous les algorithmes maintiennent aussi un seuil Uunseen, sa valeur est initialisée en agrégeant les scores les plus élevés maxi dans les sources. Les algorithmes peuvent maintenir aussi d’autres variables locales spécifiques à leurs stratégies. La fonction monotone F garantit que le seuil Uunseen et les scores maximum des candidats n’augmentent jamais, elle garantit aussi que les scores minimum des candidats ne diminuent jamais durant l’exécution de l’algorithme.
A chaque étape, un type d’accès est d’abord choisi en utilisant la fonction générique SortedAccessCondition qui indiquera si le prochain accès est séquentiel ou direct. Ensuite une source permettant ce type d’accès est sélectionnée pour effectuer un seul accès.
Si un accès séquentiel est décidé, une source Sj est sélectionnée en utilisant la fonction BestSortedSource, pour l’interroger et retourner un objet suite à l’appel de la fonction getN ext. L’objet retourné sous forme d’un couple identifiant-score est utilisé pour mettre à jour la valeur du seuil Uunseen, l’ensemble des can-didats et éventuellement les variables locales. Cet objet est ajouté à la liste des candidats s’il est rencontré pour la première fois, ou simplement mis à jour en considérant le score local retourné. En même temps, l’intervalle de score de chaque candidat dont le score local dans la source Sj est encore inconnu est mis à jour. Cette mise à jour permet aussi d’éliminer les candidats non-viables. Un candidat c avec un score maximum U(c) < Lk est considéré comme non-viable car il n’intègrera jamais le top-k final puisqu’il existe au moins k candidats avec de meilleurs scores et qui le resteront.
Dans le cas d’un accès direct, la fonction ChooseCandidate choisit un candidat c, ensuite, la fonction BestRandomSource sélectionne une R-source ou une SR-source à interroger pour retourner le score local de c. L’accès à la source se fait avec la fonction getScore qui permet de retourner le score local du candidat, ensuite, la liste des candidats et éventuellement les variables locales sont mises à jour. Dans la liste des candidats, la mise à jour ne concerne que l’intervalle de score du candidat en question c, et la vérification de l’existence de nouveaux candidats non-viables.
La condition d’arrêt des algorithmes top-k est contrôlée par la fonction générique StopCondition qui dépend du type de résultat final souhaité par l’algorithme, par exemple des candidats avec des scores exacts ou avec des intervalles de scores. L’arrêt le plus rapide pour un résultat final est obtenu par la condition suivante : StopCondition (jcandidatesj = k ^ Lk Uunseen) (2.2)
Cette condition signifie que le nombre de candidats viables est k, donc candidates = Uk = Lk, et qu’aucun objet inconnu ne peut intégrer le top-k. Il est simple de montrer que cette condition est nécessaire et suffisante pour garantir que l’ensemble des k candidats est un résultat correct.
En effet, si la condition soit remplie, nous disposons de k candidats viables qui ne peuvent pas être dépassés par des objets non vus (Uunseen Lk), donc les k candidats forment un top-k correct.
Au contraire, si la condition n’est pas remplie, alors soit jcandidatsj 6= k et donc candidates ne peut pas constituer le top-k, soit Uunseen > Lk, donc il est possible qu’un objet non vu dépasse le candidat ayant le score minimum Lk.
D’autres conditions sont nécessaires pour assurer des propriétés supplémentaires du résultat final, tel que l’ordre dans le résultat ou les scores exacts des candidats.
Les caractéristiques du résultat exact obtenu par cette condition sont les suivantes :
• Les scores exacts des k candidats retournés ne sont pas forcément calculés, on peut ne disposer que d’intervalles de score.
• L’ensemble des candidats retournés n’est pas trié par score. Un ordre peut être établi entre deux candidats c1 et c2 seulement si L(c1) U(c2) ou L(c2) U(c1), ce qui n’est pas garanti par la condition d’arrêt.

Exemples d’algorithmes top-k exprimés dans GF

Il est simple de montrer que tout algorithme top-k dans le contexte présenté précédemment peut s’expri-mer dans GF. En effet, pour une requête top-k et un ensemble de sources, chaque algorithme peut être vu comme une séquence d’accès à ces sources, suivis de la mise à jour des structures internes (candidates, Uunseen, autres variables). Cette séquence peut être obtenue grâce à une suite de décisions concernant le type à effectuer, ainsi que la source à interroger et le candidat à évaluer dans le cas d’un accès direct, ce que fait GF. Intuitivement, pour toute séquence, nous pouvons définir de façon appropriée les fonctions SortedAccessCondition, BestSortedSource, ChooseCandidate, BestRandomSource, et StopCondition pour générer cette séquence avec GF.
Nous signalons que ceci n’est pas réalisable avec l’algorithme NC [Hwang and Chang, 2007], dans lequel à chaque étape de l’exécution, la première opération consiste à choisir un candidat parmi les k candidats de Uk, ensuite une source est choisie parmi celles où le candidat en question n’a pas été retrouvé.

CADRE GÉNÉRIQUE POUR LE TRAITEMENT DES REQUÊTES TOP-K

Cette stratégie appliquée dans le cadre NC n’est pas compatible avec des algorithmes qui fixent un ordre des sources à interroger, comme dans NRA, car une source S ne sera jamais sélectionnée si les scores des candidats dans Uk sont déjà connus dans S.
Contrairement à NC, le cadre GF que nous proposons est compatible avec tous les algorithmes top-k dans notre contexte. Nous présentons dans la suite trois exemples d’algorithmes top-k exprimés avec GF : NRA pour les algorithmes sans accès direct, TA pour ceux avec SR-sources et MPro pour les algorithmes avec accès directs contrôlés.
L’algorithme NRA exprimé dans GF
L’algorithme NRA peut être exprimé dans GF de la manière suivante :
• SortedAccessCondition : retourne à chaque fois true, puisque NRA considère uniquement des sources triées.
• BestSortedSource : retourne simplement la source suivante (stratégie round-robin). Une variable locale est nécessaire pour indiquer le numéro d’ordre de la prochaine source à consulter.
• ChooseCandidate et BestRandomSource ne seront pas considérées puisque la fonction SortedAc-cessCondition retourne toujours true.
• StopCondition : utilise la condition 2.2.
L’algorithme TA exprimé dans GF
Nous montrons ici une façon pour exprimer l’algorithme TA dans GF. TA appartient aux algorithmes top-k considérant uniquement des sources de données de types SR-sources. Les fonctions génériques de GF peuvent être instancier de la manière suivante. A noter que des variables locales sont nécessaires pour indiquer la prochaine source pour un accès séquentiel (comme dans NRA) et pour indiquer le nombre d’accès directs nécessaires pour l’évaluation complète du candidat découvert lors du dernier accès sé-quentiel.
• SortedAccessCondition : retourne true si le nombre d’accès directs restants est 0.
• BestSortedSource : Comme dans NRA, cette fonction retourne à chaque fois la source suivante. A noter que suite à l’accès séquentiel, si l’objet trouvé est déjà candidat alors le nombre d’accès directs restants reste 0, ce qui produira un nouvel accès séquentiel la prochaine fois. Sinon, le cycle d’accès directs est enclenché en initialisant le nombre d’accès directs à m 1.
• ChooseCandidate : le candidat choisi est celui découvert lors du dernier accès séquentiel.
• BestRandomSource : pour effectuer les accès directs, TA utilise la même méthode que BestSor-tedSource pour le parcours successif des sources en évitant la source où le dernier accès séquentiel a été réalisé.
• StopCondition : retourne true si le score du kème candidat est supérieur à Uunseen, ce qui est en fait équivalent à 2.2.
A noter que les algorithmes top-k pour SR-sources, de type TA peuvent éviter de maintenir les candi-dats avec des intervalles de score, puisqu’ils calculent immédiatement le score final de chaque nouveau candidat retourné suite à un accès séquentiel. Néanmoins, nous nous plaçons dans un contexte où l’opé-ration la plus coûteuse est l’accès aux sources et nous pouvons donc laisser de côté l’amélioration de la gestion des candidats obtenue par ce type d’algorithme. La version de TA obtenue par instanciation de GF est donc tout à fait acceptable ici.

L’algorithme MPro exprimé dans GF

Comme exemple d’algorithme top-k avec accès directs contrôlés, nous présentons ici l’instanciation de MPro dans GF :
• SortedAccessCondition : cette fonction retourne true, si un objet non vu peut devenir le meilleur de Uk, l’ensemble des k candidats avec les meilleurs scores maximum. Plus précisément, un accès séquentiel est décidé quand U1 < Uunseen.
• BestSortedSource : MPro choisit la seule source triée disponible.
• ChooseCandidate : retourne le meilleur candidat de Uk.
• BestRandomSource : MPro établit un ordre fixe de parcours des sources non triées pour les accès directs, BestRandomSource retourne la source suivante selon cet ordre.
• StopCondition : retourne true si les candidats dans Uk ont des scores exacts (pas des intervalles de scores), et le score du kème candidat est supérieur à Uunseen (Uk Uunseen). Une variante avec des scores incomplets peut aussi être obtenue en utilisant la condition 2.2.
Avec cette capacité d’exprimer tous les algorithmes top-k, le cadre GF simplifie la comparaison entre les différentes stratégies utilisées dans les algorithmes top-k, car elle met en évidence les paramètres qui font la différence entre ces algorithmes.
Dans la suite de ce chapitre, nous présentons la stratégie BR et les variantes d’algorithmes que nous proposons pour le traitement des requêtes top-k de sélection.