Traitement et optimisation des requêtes

Le traitement des requêtes est l'ensemble des algorithmes qui parcourent un index inversé pour évaluer une requête, et les techniques d'optimisation accélèrent ce processus en évitant le travail inutile.

Definition

Le traitement et l'optimisation des requêtes consistent en la conception d'algorithmes qui calculent les documents correspondants ou les mieux classés pour une requête en parcourant les publications inversées (inverted postings), ainsi qu'en des techniques d'élagage (pruning) et d'ordonnancement qui minimisent les documents évalués et les publications lues sans modifier (ou en limitant la modification de) le résultat.

Scope

Ce sujet couvre la manière dont les requêtes sont évaluées efficacement par rapport à un index inversé : l'intersection et la fusion des listes de publications (postings-list) pour les requêtes booléennes, les stratégies document-par-document (document-at-a-time) et terme-par-terme (term-at-a-time) pour la recherche classée, et l'optimisation top-k via des algorithmes d'élagage dynamique (dynamic pruning) tels que MaxScore et WAND qui ignorent les documents ne pouvant pas figurer parmi les meilleurs résultats. Il aborde les pointeurs de saut (skip pointers), le réordonnancement des requêtes et la recherche hiérarchisée ou à deux niveaux, en se concentrant sur l'efficacité algorithmique du retour des résultats plutôt que sur le modèle de classement ou l'encodage de l'index.

Core questions

• Comment les listes de publications (postings lists) sont-elles intersectées ou fusionnées pour évaluer les requêtes booléennes et classées ?
• Quelle est la différence entre l'évaluation document-par-document (document-at-a-time) et terme-par-terme (term-at-a-time) ?
• Comment les résultats top-k peuvent-ils être trouvés sans évaluer entièrement chaque document candidat ?
• Comment les méthodes d'élagage dynamique (dynamic pruning) telles que MaxScore et WAND ignorent-elles les documents en toute sécurité ?
• Comment les pointeurs de saut (skip pointers) et le réordonnancement des requêtes réduisent-ils le travail ?

Key concepts

• intersection et fusion des publications (postings)
• évaluation document-par-document (document-at-a-time)
• évaluation terme-par-terme (term-at-a-time)
• recherche top-k
• élagage dynamique (dynamic pruning) (MaxScore, WAND)
• pointeurs de saut (skip pointers)
• réordonnancement des termes de requête
• recherche à deux niveaux / hiérarchisée

Key theories

Évaluation document-par-document (document-at-a-time) vs. terme-par-terme (term-at-a-time)

La recherche classée peut progresser à travers les publications de tous les termes de la requête dans l'ordre des documents, accumulant le score de chaque document en une seule fois, ou traiter entièrement les publications d'un terme avant le suivant ; le choix affecte l'utilisation de la mémoire, les opportunités d'élagage et le comportement du cache.

Élagage dynamique (dynamic pruning) pour la recherche top-k

En maintenant le score du k-ième meilleur document actuel et en utilisant des bornes de score maximales par terme, des algorithmes tels que MaxScore et WAND ignorent les documents qui ne peuvent manifestement pas entrer dans le top-k, renvoyant les mêmes résultats classés beaucoup plus rapidement.

Clinical relevance

Un traitement efficace des requêtes est ce qui rend possible la recherche interactive à faible latence sur des milliards de documents. Les techniques d'élagage dynamique (dynamic pruning) telles que WAND sont implémentées dans des moteurs de recherche et des bibliothèques de recherche open source largement utilisés, contrôlant directement le temps de réponse et le coût de service à l'échelle.

History

Les stratégies et optimisations fondamentales d'évaluation des requêtes ont été systématisées par Turtle et Flood en 1995. À mesure que la recherche web s'est développée, l'optimisation top-k est devenue essentielle, et l'algorithme WAND de Broder et ses collègues en 2003 a popularisé l'élagage dynamique sûr (safe dynamic pruning). Les variantes ultérieures basées sur des blocs ont encore accéléré l'évaluation, et ces méthodes sont désormais standard dans les moteurs de recherche en production.

Key figures

• Howard Turtle
• Andrei Z. Broder
• David Carmel
• W. Bruce Croft

Seminal works

• turtle1995
• broder2003
• manning2008

Frequently asked questions

Qu'est-ce que la recherche top-k ?

La recherche top-k signifie ne renvoyer que les k documents ayant les scores les plus élevés pour une requête plutôt que d'évaluer et de classer l'ensemble de la collection. Étant donné que les utilisateurs ne voient que les premiers résultats, les systèmes exploitent cette particularité pour ignorer les documents qui ne peuvent pas atteindre le top k, ce qui permet d'économiser un travail considérable.

Les méthodes d'élagage (pruning) comme WAND sont-elles sans perte ?

Dans leur forme sûre de base, oui : MaxScore et WAND ignorent uniquement les documents qui ne peuvent manifestement pas entrer dans le top-k, de sorte qu'ils renvoient exactement les mêmes résultats classés qu'une évaluation exhaustive, mais plus rapidement. Les variantes approximatives échangent une petite quantité de précision contre une vitesse supplémentaire.