WWW: Máquinas de Búsqueda

M. Andrea Rodríguez TastetsDIIC - Universidad de Concepción

http://www.inf.udec.cl/~andrea

Ranking

Modelos más usados: Boolean o Vector y sus variaciones

Ranking tiene que ser realizado con acceso sólo a los índices y no el texto

Acerca de los algoritmos, la información es secreta y es casi imposible tener una medida de recall

Ranking

Yuwono y Lee (1997) propusieron tres algoritmos de ranking (plus tf-idf scheme):• Boolean spread (Boolean clásico más “simplified

link analysis”) • Most-cited (basado sólo en los términos incluidos

en páginas que tienen un link a las páginas en la respuesta)

• Vector Spread Activation (Vector space model y spread activation model) (relativamente superior, 75%)

• Boolean spread y vector spread usan modelos clásicos extendidos con páginas apuntadas por páginas en la respuesta o páginas que apuntan a la respuesta.

Ranking

Algunos nuevos algoritmos también usan información de hyperlink

Diferencia importante entre la Web y IR en databases: el número de hyperlinks que apuntan a una página refleja una medida de popularidad y calidad.

Links entre páginas frecuentente indican una relación entre ellas.

Ranking

Ejemplos de rankings basados en análisis de links:• WebQuery, el cual permite browsing visual de

páginas Web. Toma un conjunto de páginas Web y las ordena en base a cuán conectadas están. También extiende el conjunto de páginas a un conjunto de páginas altamente conectadas.

Ranking

WebQuery

Ranking

Ranking de Kleinberg depende de la consulta y considera el conjunto de páginas S que apunta a o son apuntadas por la respuesta. • Páginas que tienen muchos links que apuntan a ellas

en S son llamadas autoridades (authorities)• Páginas que tienen muchos links de salida son

llamadas conectores (hubs) Mejores páginas authorities vienen de links de entrada

desde buenos conectores (hubs) y buenos hubs vienen de enlaces de salida de buenas authorities.

Ranking

  

∑→⎯∈

=upSu

uApH )()(

∑→⎯∈

=pvSv

vHpA )()(

Ranking

PageRank simula un usuario que navega aleatoriamente en la Web, quien salta a una página aleatoria con probabilidad q o que sigue un hyperlink aleatorio (en la página actual) con probabilidad 1 - q.

Este proceso es modelado como una cadena de Markov, donde la probabilidad estacionaria de estar en cada página puede ser calculada.

Sea C(a) el número de enlaces de salida de una página a y suponga que página a está apuntada por páginas p1 a pn

Ranking∑=

−+=n

i i

i

pC

pPRqqaPR

1 )(

)()1()(

Crawling la Web

• Comienza con un conjunto de URLs y desde ellos extrae los URLs, los cuales son seguidos recursivamente en un enfoque breadth-first o depth-first.

• Máquinas de búsqueda permiten a usuarios enviar los sitios Web top que serán agregados a la lista de URL.

• Una variación es comenzar con un conjunto de URL populares,porque se espera que ellas tengan frecuentes requerimientos de información.

Crawling• Ambos casos trabajan bien para un crawler, pero es

difícil coordinar muchos crawlers de manera de evitar visitar la misma página más que una vez en un recorrido.

• Otra técnica es dividir la Web usando códigos de países o nombre de Internet, y asignar un o más robots a cada partición.

• Considerando como la Web es atravezada, el índice de máquina de búsqueda puede ser pensada de una forma análoga a las estrellas en el cielo. Lo que uno ve no existe tal cual, ya que la luz ha atravezado diferentes distancias hasta nuestro ojo.

Crawling

• Similarmente, páginas Web referenciadas en un índice son también exploradas en diferentes momentos.

• Cuán actualizadas son las páginas Web en un índice? Las páginas son de un día a un dos meses viejas. Por esta razón, muchas máquinas de búsqueda muestran en la respuesta la fecha cuando la página fue indexada.

• El porcentaje de enlaces inválidos almacenados en

máquinas de búsqueda varía de 2 a 9%

Crawling

• Usuarios crean páginas que son recorridas o indexadas después de unos pocos días o semanas.

• Algunas máquinas atraviezan la Web “completa”, mientras otros seleccionan sólo un cierto subconjunto de depth de recorrdio.

• Han páginas que aprenden la frecuencia de cambio de una página y la visita de acuerdo a eso.

• Los crawlers actuales son capaces de atravezar hasta 10 millines de páginas Web en un día.

Crawling El orden que los URL son visitados es importante:

• Usando una política breadth first, se busca todas las páginas enlazadas a la actual primero. Esto es bueno para sitios que están bien estructurados por tópicos relacionados. Por otro lado, la cobertura puede ser amplia pero poco profunda y un servidor Web puede ser bombardeado por muchos requerimientos.

• En el caso de depth first, se sigue el primer enlace y así sucesivamente hasta no se puede ir más profundo.

• Un buen esquema de ordenamiento puede hacer la diferencia para visitar las mejores páginas primero (PageRank)

Crawling Esquema de ordamiento alternativos:

• Estrategias con ninguna información adicional: backlink-count batch-pagerank partial-pagerank OPIC (weighted backlink strategy) largest site first.

• Estrategias con información histórica• Estrategias con toda la información

Crawling

Crawling Debido a que los robots pueden sobrepasar un

servidor y usar ancho de banda significativo de la Internet, un conjunto de guías para la conducta de robots debe ser desarrollada.

Crawlers puden tener problemas con páginas HTML que usan mapas o frames. Adicionamente, páginas generadas dinámicamente no pueden ser indexadas como tampoco, páginas protegidas por password.

Indices La mayoría de los índices son variaciones del

índice invertido. • Un archivo invertido es una lista de palabras

ordenadas, cada una de las cuales apunta a las páginas donde existe.

• Algunas máquinas de búsqueda usan eliminación de stopwords para reducir el tamaño del índice. Normalización puede incluir remover puntuación y múltiple espacios.

• Dar al usuario alguna idea acerca del documento recuperado, el índice entrega una descripción corta de la página Web.

Indices

• Asumiendo que 500 bytes son usados para almacenar un URL y una descripción, se necesitan 50Gb para almaenar 100 millones de páginas

• Como el usuario recibe inicialmente sólo un subconjunto de la respuesta completa a una consulta, las máquinas de búsqueda almacenan la respuesta completa.

Indices Técnicas de indexación pueden reducir el espacio del

archivo invertido hasta un 30% de tamaño del texto (menos si stopwords son eliminadas). Para 100 millones de páginas, esto implica 15 Gb de disco duro.

Una consulta es respondida por un búsqueda binaria en la lista ordenada de palabras de un archivo invertido.

Búsqueda por múltiple palabras, los resultados tienen que ser combinados para general una respuesta final.

Problema: frecuencia de la palabra

Indices Archivos invertidos pueden también

apuntar a la posición exacta de ocurrencia de una palabra, pero es muy costoso.

Tener la posición exacta permite responder preguntas de frases o proximidad.

Actualmente no se conoce cómo las máquinas de búsqueda permiten búsqueda por frases.

Indices

Apuntar a una página o una posición es una indicación de la granularidad de un índice.

Los índices pueden ser menos densos si apuntan a un bloque lógico• Reduce la varianza dada por los tamaños

de documentos, haciendo bloques del mismo tamaño.

• Reduce el tamaño de los punteros• Reduce el número de referencias