sorting - utilidad - que son los buscadores de informacion
¿Cómo clasifica un motor de búsqueda millones de páginas en 1 segundo? (11)
Entiendo los conceptos básicos de la clasificación de los motores de búsqueda, incluidas las ideas de "índice inverso", "modelo de espacio vectorial", "similitud de coseno", "PageRank", etc.
Sin embargo, cuando un usuario envía un término de consulta popular, es muy probable que haya millones de páginas que contengan este término. Como resultado, un motor de búsqueda aún necesita ordenar estos millones de páginas en tiempo real. Por ejemplo, acabo de intentar buscar "Barack Obama" en Google. Muestra "Alrededor de 937,000,000 resultados (0.49 segundos)". ¿Clasificando sobre 900M artículos dentro de 0.5 segundos? ¡Eso realmente me sorprende!
¿Cómo clasifica un motor de búsqueda un número tan grande de elementos en 1 segundo? ¿Alguien puede darme algunas ideas intuitivas o señalar referencias?
¡Gracias!
ACTUALIZAR:
- La mayoría de las respuestas (incluidas algunas discusiones anteriores) hasta ahora parecen contribuir con el crédito al "índice inverso". Sin embargo, que yo sepa, el índice inverso solo ayuda a encontrar las "páginas relevantes". En otras palabras, por índice inverso, Google podría obtener las 900M páginas que contienen "Barack Obama" (de más de varios miles de millones de páginas). Sin embargo, todavía no está claro cómo "clasificar" estos millones de "páginas relevantes" según los hilos que he leído hasta ahora.
- Es improbable que el marco MapReduce sea el componente clave para la clasificación en tiempo real. MapReduce está diseñado para tareas por lotes. Al enviar un trabajo a un marco de MapReduce, el tiempo de respuesta suele ser de al menos un minuto, lo que aparentemente es demasiado lento para satisfacer nuestra solicitud.
Aquí tienes, lo busqué y ¡esto es lo que encontré! http://computer.howstuffworks.com/internet/basics/search-engine.htm
Como dijo Xiao, solo tienes que clasificar el top-k en lugar de la lista completa.
Google le dice que hay 937,000,000 resultados, pero no se los mostrará a usted. Si sigue desplazándose página tras página, después de un tiempo se truncarán los resultados :)
Esta es mi teoría ... Es muy imposible que usted sea el primero en buscar una palabra clave. Por lo tanto, para cada palabra clave (o una combinación) buscada en un motor de búsqueda, mantiene una serie de enlaces a páginas web relevantes. Cada vez que hace clic en un enlace en los resultados de búsqueda, recibe una votación sobre el hashset de esa combinación de palabras clave. Desafortunadamente, si usted es el primero, guarda su palabra clave de búsqueda (para sugerir búsquedas futuras) e inicia el hashing de esa palabra clave. Así que terminas con menos resultados o ninguno. La clasificación de la página como usted podría saber depende de muchos otros factores, como los vínculos de retroceso, no. De páginas que hacen referencia a una palabra clave en seaech. etc.
Hay dos factores principales que influyen en el tiempo que le lleva obtener una respuesta de su motor de búsqueda.
La primera es si está almacenando su índice en el disco duro. Si está utilizando una base de datos, es muy probable que esté utilizando el disco duro al menos un poco. Desde un arranque en frío, sus consultas serán lentas hasta que los datos necesarios para esas consultas se hayan introducido en la memoria caché de la base de datos.
El otro es tener un caché para sus consultas populares. Se tarda mucho más en buscar una consulta que en devolver los resultados de un caché. Ahora, el tiempo de acceso aleatorio para un disco es demasiado lento, por lo que necesitan tenerlo almacenado en la RAM.
Para resolver estos dos problemas, Google utiliza memcached. Es una aplicación que almacena en caché la salida del motor de búsqueda de Google y transmite resultados un tanto antiguos a los usuarios. Esto está bien porque la mayoría de las veces la web no cambia lo suficientemente rápido como para que sea un problema, y debido a la importante coincidencia en las búsquedas. Puede estar casi seguro de que Barack Obama ha sido buscado recientemente.
Otro problema que afecta la latencia del motor de búsqueda es la sobrecarga de la red. Google ha estado utilizando una variante personalizada de Linux (IIRC) que se ha optimizado para su uso como servidor web. Se las han arreglado para reducir parte del tiempo que lleva comenzar a convertir los resultados en una consulta.
En el momento en que una consulta llega a sus servidores, el servidor responde inmediatamente al usuario con el encabezado de la respuesta HTTP, incluso antes de que Google haya terminado de procesar los términos de la consulta.
Estoy seguro de que también tienen un montón de otros trucos bajo la manga.
EDITAR: También mantienen sus listas invertidas ordenadas, desde el proceso de indexación (es mejor procesar una vez que para cada consulta).
Con estas listas pre-ordenadas, la operación más costosa es la intersección de listas. Aunque estoy bastante seguro de que Google no se basa en un modelo de espacio vectorial, entonces la intersección de la lista no es un factor tan importante para ellos.
Los modelos que dan mejores resultados según la literatura son los modelos probabilísticos. Como ejemplo, puede que desee buscar Okapi BM25. Lo hace bastante bien en la práctica dentro de mi área de investigación (Recuperación de XML). Cuando se trabaja con modelos probabilísticos, tiende a ser mucho más eficiente procesar el documento a la vez en lugar del término a la vez. Lo que esto significa es que, en lugar de obtener una lista de todos los documentos que contienen un término, examinamos cada documento y lo clasificamos según los términos que contiene nuestra consulta (omitir documentos que no tienen términos).
Pero si queremos ser inteligentes, podemos abordar el problema de una manera diferente (pero solo cuando parece ser mejor). Si hay un término de consulta que es extremadamente raro, podemos clasificarlo primero, porque tiene el mayor impacto. Luego nos ubicamos en el siguiente mejor término, y continuamos hasta que hayamos determinado si es probable que este documento esté dentro de nuestros mejores k resultados.
La pregunta sería realmente relevante si estuviéramos seguros de que la clasificación estaba completa. Es muy posible que el orden provisto sea aproximado.
Dada la fluidez de los resultados del ranking, ninguna respuesta que parezca razonable podría considerarse incorrecta. Por ejemplo, si se excluyera una sección completa de la web de los resultados principales, no lo notaría, siempre que se incluyeran más adelante.
Esto les da a los desarrolladores un grado de latitud que no está disponible en casi todos los otros dominios.
La verdadera pregunta es: ¿con qué precisión coinciden los resultados con el rango real asignado a cada página ?
No hay forma de que espere obtener una respuesta precisa a esta pregunta aquí;) De todos modos, aquí hay algunas cosas que debe considerar: Google utiliza una infraestructura única en cada parte. Ni siquiera podemos adivinar el orden de complejidad de su equipo de red o el almacenamiento de su base de datos. Eso es todo lo que sé sobre el componente de hardware de este problema.
Ahora, para la implementación del software, como dice el nombre, el PageRank es un rango en sí mismo. No clasifica las páginas cuando ingresas a la consulta de búsqueda. Supongo que lo clasifica en una parte totalmente independiente de la infraestructura cada hora. Y ya sabemos que los robots rastreadores de Google están recorriendo la Web 24/7, por lo que asumo que las nuevas páginas se agregan a un mapa hash "sin clasificar" y luego se clasifican en la siguiente ejecución del algoritmo.
A continuación, cuando escribe su consulta, miles de CPU analizan de forma independiente miles de partes diferentes de la base de datos de PageRank con un factor de separación. Por ejemplo, si el factor de separación es 10, una máquina consulta la parte de la base de datos que tiene valores de PageRank de 0-9.99, la otra consulta la base de datos de 10-19.99, etc. Dado que los recursos no son un obstáculo para Google, pueden establecer el factor de separación es tan bajo (por ejemplo, 1) para que cada máquina consulte menos de 100k páginas, lo que no es demasiado para su hardware. Luego, cuando necesitan compilar los resultados de su consulta, ya que saben qué máquina clasifica exactamente qué parte de la base de datos pueden usar el principio de " llenar el grupo ". Sea n el número de enlaces en cada página de Google. El algoritmo que combina las páginas devueltas de las consultas ejecutadas en todas esas máquinas contra todas las diferentes partes de la base de datos solo necesita llenar los primeros n resultados. Así que toman los resultados de la consulta de la máquina contra el rango más alto de la base de datos. Si es mayor que n, se terminan, si no se mueven a la siguiente máquina. Esto toma solo O (q * g / r) donde s es la cantidad de páginas que Google sirve, g es el factor de separación yr es el valor más alto de PageRank. Esta suposición es alentada por el hecho de que cuando pasa a la segunda página, su consulta se ejecuta nuevamente (observe el diferente tiempo que se tarda en generarla).
Estos son solo mis dos centavos, pero creo que soy bastante acertado con esta hipótesis.
EDITAR: es posible que desee revisar esto por la complejidad de las consultas de alto orden.
No sé lo que realmente hace Google, pero seguramente usan aproximación. Por ejemplo, si la consulta de búsqueda es ''Motor de búsqueda'', el número de resultados será = (número de documentos donde hay una o más apariciones de la palabra ''búsqueda'' + número de documentos donde hay una o más apariciones de la palabra ''motor''). Esto se puede hacer en O (1) complejidad de tiempo. Para más detalles, lea la estructura básica de Google http://infolab.stanford.edu/~backrub/google.html .
Respecto a tu actualización:
Es improbable que el marco MapReduce sea el componente clave para la clasificación en tiempo real. MapReduce está diseñado para tareas por lotes. Al enviar un trabajo a un marco de MapReduce, el tiempo de respuesta suele ser de al menos un minuto, lo que aparentemente es demasiado lento para satisfacer nuestra solicitud.
MapReduce no solo está diseñado para tareas por lotes. Existen bastantes marcos de MapReduce que admiten la computación en tiempo real: Apache Spark , Storm , Infinispan Distributed Executor , Hazelcast Distributed Executor Service .
De vuelta a su pregunta, MapReduce es la clave para distribuir la tarea de consulta a varios nodos y luego fusionar el resultado.
También creo que el uso de bases de datos NoSQL en lugar de RDBMS ayuda.
Las bases de datos NoSQL se escalan horizontalmente mejor y no generan cuellos de botella. Chicos grandes como Google Facebook o Twitter los usan.
Como otros comentarios / respuestas sugirieron que los datos podrían estar ya ordenados, y están devolviendo compensaciones de los datos encontrados en lugar de todo el lote.
La pregunta real no es cómo clasifican tantos resultados tan rápidamente, sino cómo lo hacen cuando decenas o cientos de millones de personas en todo el mundo consultan Google al mismo tiempo xD
Tengo una respuesta de una palabra para usted: QuickSort!
Una posible estrategia es clasificar el top-k en lugar de la lista completa.
Por ejemplo, para encontrar los primeros 100 resultados de 1 millón de aciertos, por algoritmo de selección, la complejidad del tiempo es O ( n log k ). Como k = 100 y n = 1,000,000, en la práctica podríamos ignorar log ( k ).
Ahora, solo necesita O ( n ) para obtener los 100 mejores resultados de 1 millón de visitas.