Para los que nos dedicamos a esto de internet, pocas cosas hay tan deliciosas como leer el proyecto de fin de carrera de Sergey Brin y Lawrence Page. En este documento de tan sólo 20 páginas llamado “The anatomy of a large scale hypertextual  web search engine” estos dos adolescentes comienzan con una frase que con el paso de los años suena adorable:

“En este documento presentamos Google, un prototipo de buscador de gran tamaño, que hace un uso intensivo de la estructura presente en el hipertexto.”

¿no me digan que no es adorable? ¿quien no se imagina leyendo el proyecto fin de carrera de su hijo, que está a punto de convertirse en uno de los hombres más famosos del planeta?

En este post vamos a comentar dos cuestiones que se tratan en dicho documento: como trata Google la búsqueda simple y la búsqueda compleja.

Búsqueda simple

En una búsqueda simple como ‘aragon’, Google lo tiene relativamente sencillo. Previamente ha contado para cada página que ha descubierto cuantas veces aparece cada palabra que conoce en cada una de las diferentes posiciones que puede ocupar en una página. Fijaros que hay billones de páginas, centenares de miles de palabras diferentes, y decenas de posiciones posibles en las que una palabra puede estar en una página. Estamos realmente ante un índice inverso gigantesco. Cuando estos estudiantes construyeron su juguete indexaron 24 millones de páginas. La infraestructura que se requiere para generar el índice inverso de ese volumen de documentos es considerable. Por aquel entonces conceptos como “computación en la nube” estaban en pañales, así que básicamente lo que hicieron fue diseñar un sistema bastante eficiente que pudiera crecer con cpus de segunda mano. Tal que así:

Busqueda compleja

Si el índice inverso para búsqueda simple es imenso, se queda pequeño en comparación al indice inverso ene-dimensional que se utiliza cuando se hace una búsqueda compleja.

En este caso, importa no solo la frecuencia de aparición de cada palabra en cada documento, sino también la distancia entre ellas. Para una búsqueda como “aragon en internet” lo primero que se hace es un tratamiento previo. En este ejemplo “en” es descartada por estar en una lista de palabras neutras, y probablemente “aragón” e “internet” se contrastan con diccionarios de raíces y sinónimos para reducir las dimensiones del problema a resolver.

Luego, se consulta una matriz que describe para cada posible par de palabras su frecuencia de aparición en cada uno de los elementos de página posibles. Observad que eso hace crecer todavía más el índice inverso puesto que hemos de guardar para cada página cada posible combinación de dos palabras presentes en el documento.

Desde luego, esta es una versión bastante “abierta del problema”. Probablemente por el camino, ambos investigadores encontraron diversos métodos para comprimir la información y reducir las dimensiones del problema, como lo muestran sus estadísticas finales:

147GB de páginas webs indexadas

37GB de tamaño del índice inverso

No está mal! El  índice inverso solo incrementa un 25% el espacio necesario de Google. Dicho de otra manera, hacer eso que sea que hace también, solo le consume un 25% de espacio en disco más respecto a los competidores que tenía por aquel entonces.

Desde ese día el algoritmo ha sido mejorado en multitud de ocasiones como demuestran la gran cantidad de patentes solicitadas por Google, pero los conceptos básicos del buscador no han cambiado tanto.

Tags: algoritmo pagerank, busqueda multiple, busqueda simple, posicionamiento en buscadores, que es pagerank, SEM, SEO

Esta entrada se escribió en Miércoles, Septiembre 16th, 2009 a las 17:34 y está archivado en Sin categoría.