Comment les moteurs de recherche effectuent-ils le fonctionnement 'ET'?

Question

Tenir compte des résultats de recherche suivants:

• Google for 'David' - 591 millions coups sûrs en 0,28 sec
• Google for 'John' - 785 millions coups sûrs en 0,18 sec

OK. Les pages sont indexées, il suffit de rechercher le nombre et les premiers éléments de la table d'index, donc la vitesse est compréhensible.

considèrent maintenant la recherche suivante avec opération ET:

• Google for 'David John' ('David' ET 'John') - 173 millions frappe en 0,25 sec

Cela me fait tic tac ;) Comment les moteurs de recherche peuvent-ils obtenir le résultat des opérations ET sur des ensembles de données gigantesques si rapidement? Je vois les deux façons suivantes de mener la tâche et les deux sont terribles:

1. Vous effectuez la recherche de 'David'. Prenez la gigantesque table temporaire et lancez une recherche sur "John". TOUTEFOIS, la table temporaire n'est pas indexée par 'John', donc la recherche de force brute est nécessaire. Cela ne calcule pas en 0,25 s, peu importe ce que vous avez.
2. Indexation par tous les mots possibles combinaisons comme 'David John'. Puis nous faisons face à une explosion combinatoire sur le nombre de clés et même pas Google a la capacité de stockage pour gérer cela.

Et vous pouvez ET ensemble as many search phrases as you want et vous obtenez toujours des réponses en moins de 0,5 sec! Comment?

Answer 1

Ce que Markus a écrit à propos de Google traitant la requête sur plusieurs machines en parallèle est correct.

En outre, il existe des algorithmes information retrieval qui facilitent un peu ce travail. La façon classique de le faire est de construire un inverted index qui se compose de listes de messages - une liste pour chaque terme de tous les documents qui contiennent ce terme, dans l'ordre. Lorsqu'une requête avec deux termes est recherchée, conceptuellement, vous devez prendre les listes de messages pour chacun des deux termes ('david' et 'john'), et les parcourir, en recherchant les documents qui se trouvent dans les deux listes . Si les deux listes sont ordonnées de la même manière, cela peut être fait en O (N). Certes, N est encore énorme, ce qui explique pourquoi cela sera fait sur des centaines de machines en parallèle.

En outre, il peut y avoir des astuces supplémentaires. Par exemple, si les documents les mieux classés étaient placés plus haut sur les listes, alors peut-être que l'algorithme pourrait décider qu'il a trouvé les 10 meilleurs résultats sans parcourir les listes entières. Il faudrait ensuite deviner au nombre de résultats restant (en fonction de la taille des deux listes).

Answer 2

J'ai fait quelque chose de similaire à cela il y a des années sur une machine 16 bits. L'ensemble de données avait une limite supérieure d'environ 110 000 enregistrements (c'était un cimetière, donc une limite finie sur les sépultures), donc j'ai mis en place une série de bitmaps contenant chacun 128K bits.

La recherche de "david" résultant de moi définissant le bit pertinent dans l'une des bitmaps pour signifier que l'enregistrement avait le mot "david" en elle. A fait la même chose pour 'john' dans un second bitmap. Ensuite, tout ce que vous devez faire est un binaire 'et' des deux bitmaps, et le bitmap qui en résulte vous indique quels numéros d'enregistrement avaient à la fois 'david' et 'john'. L'analyse rapide de l'image bitmap résultante vous renvoie la liste des enregistrements correspondant aux deux termes.

Cette technique ne fonctionnerait pas pour google cependant, alors considérez ceci ma valeur de $ 0.02.

Answer 3

Je pense que vous approchez le problème du mauvais angle.

Google ne possède pas de tables/index sur une seule machine. Au lieu de cela, ils partitionnent leur ensemble de données sur leurs serveurs. Les rapports indiquent that as many as 1000 physical machines are involved in every single query!Avec cette quantité de puissance de calcul, il est «simplement» (utilisé de façon très ironique) de s'assurer que chaque machine termine son travail en une fraction de seconde.

La lecture de la technologie et de l'infrastructure de Google est très inspirante et hautement éducative. Je recommande de lire sur BigTable, MapReduce et le Google File System.

Google a un archive of their publications disponible avec beaucoup d'informations juteuses sur leurs technologies. This thread on metafilter fournit également un aperçu de la quantité énorme de matériel nécessaire pour exécuter un moteur de recherche.

Answer 4

Je ne sais pas comment Google, mais je peux vous dire comment je a fait quand un client quelque chose nécessaire similaire:

Il commence par un index inversé, tel que décrit par Avi. C'est juste une liste de table, pour chaque mot dans chaque document, l'identification de document, le mot, et un score pour la pertinence du mot dans ce document. (Une autre approche consiste à indexer chaque aspect du mot individuellement avec sa position, mais cela n'était pas nécessaire dans ce cas.)

De là, c'est encore plus simple que la description d'Avi - il n'est pas nécessaire de faire une recherche séparée pour chaque terme. opérations sommaires de base de données standard peuvent facilement le faire en un seul passage:

SELECT document_id, sum(score) total_score, count(score) matches FROM rev_index 
WHERE word IN ('david', 'john') GROUP BY document_id HAVING matches = 2 
ORDER BY total_score DESC 

Cela renverra les ID de tous les documents qui ont des scores pour (c.-à-apparaissent les deux mots) à la fois « David » et « John », commandé par une certaine approximation de la pertinence et prendra à peu près le même temps à exécuter indépendamment de combien ou peu de termes que vous recherchez, puisque IN performance n'est pas beaucoup affectée par la taille de l'ensemble cible et il utilise un simple count pour déterminer si tous les termes ont été appariés ou non.

Notez que cette méthode simpliste ajoute simplement le score «David» et le score «John» ensemble pour déterminer la pertinence globale; il ne prend pas la commande/proximité/etc. des noms en compte. Encore une fois, je suis sûr que google tient compte de cela dans leurs scores, mais mon client n'en avait pas besoin.