PDF de programación - Recuperación de Información en la Web y Motores de Búsqueda

Recuperación de Información en
la Web y Motores de Búsqueda

Gabriel H. Tolosa
[email protected]



- 2015 -

RI en Web: Motores de Búsqueda



Motores de búsqueda

● Escenario/RI Web
● Arquitectura
● Recolección de páginas (Crawling)
● Ranking
● Queries y usuarios
● Escalabilidad (caching)



Motores de búsqueda

● ¿Son importantes?

● ~90% del tráfico a la mayoría de los sitios se

encuentra mediante un motor de búsqueda

● Son la primera interface entre los usuarios y la web

– En el caso de sitios comerciales (productos) estar más allá

de la posición 30 es ser “prácticamente” invisible.

● Atraen la mayor diversidad de usuarios que cualquier

sitio.

● ~ 85% de las sesiones de usuario incluyen el uso de

un MB



● ~ 90% de los usuarios los usan para navegar la web



Motores de búsqueda

● ¿Cuáles se usan?



http://searchenginewatch.com/



RI tradicional vs web



SRI tradicional

tokenization

Text

Transformation

Corpus

Indexing



Index



User
Query

Ranked list
------------
------------
------------
------------

Query

Transformation

Search

Ranking

Pero....

No lo
tenemos

Múltiples
formatos

User
Query

tokenization

Text

Transformation

Query

Transformation

Corpus

Indexing

Usuarios de
diferentes
contextos

Ranked list
------------
------------
------------
------------

Proceso
dinámico

Search

Ranking



Index



Tiene en
cuenta la
estructura

Arquitectura de un MB

Crawling

User
Query

Ranked list
------------
------------
------------
------------

Web

Repository

Query

Transformation

Global
analyzer

Metadata

Search

Ranking



Indexing
(+ Text Op.)

Index


Evolución de los MB

Primera generación

Solo utilizaban el texto en las páginas
Altavista, Exite, Lycos
Segunda generación

Analizan la estructura de enlaces de la web y los clicks
“Anchor text”. Google y PageRank

Tercera generación

Tratan de resolver “la necesidad detrás de la consulta”.
Ayudan al usuario: speell-checking, sugerencias, refinamiento
Integran múltiples fuentes (news, blogs, imágenes)
Análisis semántico básico. Aún están evolucionando!

Cuarta generación



(“Information supply”)

Incrementar el uso de contexto y la actividad del usuario!



Evolución de los MB

Còmo determinar:

¨la necesidad detràs de la consulta¨

Determinación del contexto

- Espacial (ubicación del usuario o del objetivo)
- Stream del query (respecto de los anteriores)
- Información personal (perfil)
- Explícito (elige el usuario, por ej. un MB vertical)
- Implícito (uso de Google Argentina, google.com.ar)

Uso del contexto

- Restricción de resultados (eliminar inapropiados)
- Modulación del ranking (genérico, personalizado)



Evolución de los MB

¿Y los usuarios?
Las consultas:

Las mayoría tienen de 1 a 3 términos (el 25% tiene 2)
Términos imprecisos
Uso subóptimo de la sintaxis (sólo ~10% con operadores)

Mucha variación en:

Necesidades
Expectativas
Conocimiento
Recursos (ancho de banda)

Comportamiento:

la primera


Sólo examinan unos pocos resultados (2-3 páginas), ~85% sólo

Poco refinamiento (~80 no modifica la consulta original)
La interface de búsqueda avanzada es poco utilizada



Crawling



El “corpus” web

● Creación no coordinada, distribuida (democrática)

● Ni de contenido ni de enlaces

● Diversidad

● No estructurado (txt, html)
● Semi-estructurado (XML, objetos 'anotados')
● Estructurado (BD), en menor medida.

● Tamaño: se duplica en pocos meses!
● Enlaces: 8/pág. en promedio
● Contenido dinámico

●

'On the fly'

● HTTP Get/Post

http://www.google.com/search?hl=en&q=graph+structure+in+de+the+web+slides&btnG=Search



● SPAM



Crawling → Obtener la colección

● “Encontrar” y recuperar páginas

automáticamente

● La web está constantemente cambiando
● Las páginas cambian
● La web no está bajo el control del propietario

del motor de búsqueda
● Se basa solo en la URL:

http://www.unlu.edu.ar/academia/unidades.html



[proto] [hosts] [path] [objeto]

Crawling → Obtener la colección

Web crawling <=> atravezar un grafo



Crawling → Atravezar el grafo



Crawling → Cuestiones

● ¿Cómo hacer el crawling?

● Calidad (las mejores páginas primero)
● Eficiencia (evitar duplicados)
● Cortesía (con los servidores)

● ¿Cuánto recolectar?

● Cobertura
● Cobertura relativa

● ¿Con qué frecuencia?

● “Frescura”



Crawling → Más específicamente

Para cada URL, el crawler:

● Solicita la resolución del nombre a un servidor DNS
● Abre una conexión con el servidor (IP) en un puerto

(usualmente 80)

● Envía una solicitud HTTP, generalmente usando la

primitiva GET

● Recupera el objeto y se parsea
● Finalmente, actualiza la lista de URLs (frontera)



Crawling → Frontera

URLs

procesadas

Web “no vista”

Pág.
iniciales

Web

URLs de
●“frontera”



Crawling → Control

● Existe un delay hasta recibir las respuestas

● Eficiencia → múltiples conexiones (hilos). Cientos

de páginas en paralelo

● Cuidado con sobrecargar servidores (políticas de

cortesía)
● Robots.txt

– User­agent: *
– Disallow: /privado/
– Disalow: /usuarios/
– Allow: /varios/publico/
– Sitemap: http://www.misitio.com.ar/sitemap.xml.gz



Sitemap ejemplo

<?xml version="1.0" encoding="UTF­8"?>
<urlset xmlns="http://www.google.com/schemas/sitemap/0.90">
  <url>
    <loc>http://www.sitemappro.com/</loc>
    <lastmod>2011­01­27T23:55:42+01:00</lastmod>
    <changefreq>daily</changefreq>
    <priority>0.5</priority>
  </url>
  <url>
    <loc>http://www.sitemappro.com/download.html</loc>
    <lastmod>2011­01­26T17:24:27+01:00</lastmod>
    <changefreq>daily</changefreq>
    <priority>0.5</priority>
  </url>
  <url>
    <loc>http://www.sitemappro.com/order.html</loc>
    <lastmod>2011­01­26T15:35:07+01:00</lastmod>
    <changefreq>daily</changefreq>
    <priority>0.5</priority>
  </url>
  <url>
    <loc>http://www.sitemappro.com/examples.html</loc>
    <lastmod>2011­01­27T19:43:46+01:00</lastmod>
    <changefreq>daily</changefreq>
    <priority>0.5</priority>
  </url>
  ...
  </urlset>



Ejemplo [Manning]



Crawling → Estrategias

● Clásicas → Bread-First y Depth-First
● Otras

→ URL ordering



Crawling → Estrategias

Overlap with
best x% by
indegree



x% crawled



Crawling → Otras cuestiones

● Escalabilidad
● Crawling distribuido
● Latencia/ancho de banda
● Profundidad
● Espejos/Duplicaciones
● Web SPAM → AIR
● DNS
● Robustez
● Cortesía/Estándares



● Explícita: robots.txt [www.robotstxt.org/wc/norobots.html]



●

Implícita: No sobrecargar un servidor

Queries



Lenguajes de Queries

● No hay un lenguaje standard para queries web

● No hay semántica explícita (c/ MB hace su

interpretación)

● Stemming, AND's... o no?

● Queries “Free-text” son el standard de facto

● “Cualquier cosa” que el usuario escriba
● No hay vocabulario controlado
● Se aceptan errores de ortografía
● Cuál es la diferencia con el lenguaje natural?
● Cuál es la diferencia con una “pregunta”?



Operadores comunes en MB



[Baeza-Yates & Maarek] Modern Information Retrieval, 2nd edition, 2011

Consultas

- Existen diferentes motivaciones para usar un MB
- Caracterización [Broder et al.]
● Informational – ”saber” acerca de algo (~40% / 65%)
● Navigational – ”ir” a algún lugar (~25% / 15%)
Aerolineas
Argentinas
● Transactional – ”hacer algo” (web-mediante) (~35% / 20%)

Algoritmos
evolutivos

● Access a service
● Downloads
● Shop

Canon S410

Clima en Luján

Imagen Ubuntu 11.04

● Areas “grises”



● Encontrar una buena páginas (HUB)

● Explorar para “ver que hay allí”

●

Alquiler auto Roma

Consultas

Ejemplo:
● Juan quiere comprar una impresora – Transactional Query
● Encuentra 3 posibles impresoras pero quiere más info acerca

de éstas – Infomational Query

● Luego, se decide por una Lexmark y necesita la URL donde
comprar (Lexmark, eBay, Mercadolibre, etc.) – Navigational
Query

● Juan necesita hacer la compra en línea de la elegida –

Transactional Query



Consultas

- La frecuencia de las consultas sigue una ley de Zipf con β = [0.6:1.4]
Ejemplo: Yahoo! R. Baeza-Yates, A. Gionis, F. P. Junqueira,V. Murdock,V. Plachouras,
and F. Silvestri, “Design trade-offs for search engine caching,” ACM Trans. Web, 2008.



Ranking



Resultados: SERP Layout



Resultados



Resultados



Ranking

● Recuperación de Información

● Términos incluir/excluir
● Matching parcial → scoring

● En la Web

● Frecuencia/ubicación de las palabras en el doc.
● Metadatos
● Existencia en directorio (si hay)
● Tamaño/Edad del documento
● Dominio
● Y $$$?

+ Estructura
de la WEB



Variables

De acuerdo a Matt Cutts [Ing. De Google] existen más de 200 variables
que se tienen en cuenta para el ranking
● Domain

● Content

- Age of Domain
- History of domain
- KWs in domain name
- Sub domain or root domain?
- TLD of Domain
- IP address of domain
- Location of IP address / Server

● Architecture

- HTML structure
- Use of Headers tags
- URL path
- Use of external CSS / JS files
- Authority Link (CNN, BBC, etc)

●



● Per Inbound Link

- Keyword density of page
- Keyword in Title Tag
- Keyword in Meta Description
- Keyword in KW in header tags (H1, etc.)
- Keyword in body text
- Freshness of Content
- Quality of website linking in
- Quality of web page linking in
- Age of website
- Age of web page
- Relevancy of page’s content
- Location of link (footer, navig., body)
- Anchor text if link
- Title attribute of link
- Alt tag of images linking
- Country specific TLD domain
- Authority TLD (.edu, .gov)
- Location of server

Variables

● Cluster of Links

●

- Uniqueness of Class C address.
Internal Cross Linking
- No of internal links to page
- Location of link on page
- Anchor text of FIRST text link
(Bruce Clay’s point at PubCon)

● Miscellaneous
- JavaScript Links
- No Follow Links

● Pending
- Performance / Load of a
webs