Política de Re-visita

La red es altamente cambiante. El tiempo que toma arañar una parte de ella se mide normalmente en semanas o meses. Para cuando un crawler ha acabado su trabajo, algunas de las páginas indexadas pudieron ser modificadas o eliminadas, y probablemente se crearon otras.

Para un SRI, hay un costo asociado a la no detección de un evento. Comúnmente se usan dos medidas de costo: frescura y edad(Cho y García Molina)^[1]

Frescura
Es una medida binaria que indica si la copia local de un docupento p está actualizada o no en un tiempo t. Se define como sigue:
Edad
Es una medida que indica que tan desactualizada está la copia local de un documento p en un tiempo t, y se define como sigue:

Coffman^[2] propone un modelo que equivale a la frescura: propone que un crawler debe minimizar la fracción de ttiempo que las páginas permanecen desactualizadas. El modelo propone el arañado de la red como una instancia del problema servir varias colas con un solo servidor. El crawler hace las veces del servidor mientras que los sitios webs hacen las de las colas. La llegada de un cliente se entiende como la modificación de una página y los tiempos de cambio son los intervalos entre accesos a página a un solo sitio web. Así, el tiempo medio de espera para un cliente es equivalente a la edad promedio

Se plantean entonces 2 objetivos (no equivalentes) para el crawler:

• Maximizar la frescura promedio de las páginas de la colección:
  en este caso el crawler se preocupa del número de páginas desactualizadas.
• Minimizar la edad promedio de las páginas de la colección:
  en este caso el crawler se preocupa de qué tan viejas son las copias locales de las páginas.

Cho y García-Molina (ibid) proponen dos simples políticas de revisita:

• Política uniforme:
  Todas las páginas se revisitan con igual frecuencia, sin importar sus tasas de cambio.
• Política proporcional:
  La tasa de re-visitas es proporcional a la tasa de cambio (estimadad) de cada página.

Los autores probaron que , en términos de frescura promedio, la política uniforme supera a la política proporcional. Según explican, cuando una página cambia muy a menudo, el crawler desperdicia tiempo tiempo tratando de re-arañarla muy rápido y aún así no podrá mantener fresca su copia.

Para mejorar la frescura, el crawler debe penalizar a los elementos que cambian muy a menudo^[3]. El método óptimo para maximizar la frescura promedio implica ignorar páginas que cambien muy frecuentemente, y el método óptimo para minimizar la edad promedio es usar frecuencias de acceso que crescan (asintótica, luego sublinealmente) con la tasa de cambio de cada página. En ambos casos, lo óptimo está más cerca de la política uniforme que de la política proporcional.

---

1. Cho, Junghoo; Hector Garcia-Molina (2000). "Synchronizing a database to improve freshness"

2. E. G. Coffman; Zhen Liu, Richard R. Weber (1998). "Optimal robot scheduling for Web search engines".

3. Cho, Junghoo; Hector Garcia-Molina (2003). "Estimating frequency of change".