La idea básica es usar un índice invertido. Esto significa para cada palabra mantener una lista de documentos en la web que la contienen.
La respuesta a una consulta corresponde a la recuperación de los documentos coincidentes (esto se hace básicamente intersectando las listas para las palabras de consulta correspondientes), procesando los documentos (extrayendo señales de calidad correspondientes al documento, par de consultas), clasificando los documentos (utilizando la calidad del documento señales como Page Rank y señales de consulta y consultas / señales de documentación) y luego devuelven los 10 documentos principales.
Aquí hay algunos trucos para hacer la parte de recuperación de manera eficiente:
– distribuir todo en miles y miles de máquinas
– hazlo en la memoria
– almacenamiento en caché
– mirando primero la palabra de consulta con la lista de documentos más corta
– mantener los documentos en la lista en orden inverso de pagerank para que podamos detenernos temprano una vez que encontremos suficientes coincidencias de buena calidad
– Mantenga listas de pares de palabras que aparecen juntas frecuentemente
– Fragmento por ID de documento, de esta forma la carga se distribuye de manera uniforme y la intersección se realiza en paralelo.
– comprime los mensajes que se envían a través de la red
etc.
- ¿Cómo funciona el algoritmo DeepMind?
- ¿Existe un libro o sitio web que describa los problemas y luego le solicite la estructura de datos / algoritmos más apropiados necesarios para resolver el problema?
- En programación de computadoras, ¿cómo es recursivo el proceso de evaluación?
- ¿Cuánta recopilación y análisis de datos se destina a la optimización del tiempo de los semáforos en una ciudad?
- ¿Cuál es una versión más amigable para principiantes de CLRS para algoritmos de aprendizaje? ¿Estaría rompiendo la entrevista de codificación?
Jeff Dean en esta gran charla explica bastantes partes de la infraestructura interna de Google. Menciona algunas de las ideas anteriores en la charla.
Él pasa por la evolución del diseño de servicio de búsqueda de Google y por MapReduce mientras da consejos generales sobre la construcción de sistemas a gran escala.
Aquí hay un enlace a sus diapositivas:
www.stanford.edu/class/ee380/Abstracts/101110-slides.pdf
En cuanto a la complejidad, es bastante difícil de analizar debido a todas las partes móviles, pero Jeff menciona que la latencia por consulta es de aproximadamente 0.2 sy que cada consulta toca en promedio 1000 computadoras.