Estimating Absolute Web Crawl Coverage From Longitudinal Set Intersections

Resumen Técnico: Estimación de la Cobertura Absoluta de Rastreo Web

1. El Problema

La preservación de la web mediante archivos (web archives) es fundamental, pero cuantificar la completitud o cobertura de un rastreo (crawl) sigue siendo un desafío mayor.

• Limitación fundamental: Un rastreo web aislado no permite determinar qué fracción del espacio web rastreado (el conjunto de todas las URLs que podrían ser capturadas) ha sido realmente capturado. Se conoce el número de URLs recolectadas ($M$), pero no el tamaño total del universo de URLs rastreadas ($N$).
• Definición de cobertura: La cobertura se define como $c = M/N$. Sin conocer $N$, es imposible calcular $c$.
• Limitaciones de enfoques anteriores:
  • Comparación entre motores: Métodos como los de Bharat y Broder (1998) solo ofrecen tamaños relativos (ej. "El motor A es 2.3 veces más grande que el B"), no absolutos.
  • Datos de verdad fundamental (Ground Truth): Enfoques basados en entidades requieren conjuntos de datos externos específicos y solo miden la cobertura para esa clase de entidades, no para todo el espacio de URLs.
  • Falta de métodos autocontenidos: No existía un método robusto para estimar la cobertura absoluta utilizando únicamente los datos históricos de un solo archivo de rastreo.

2. Metodología Propuesta

Los autores proponen un método para estimar la cobertura absoluta utilizando exclusivamente datos longitudinales (múltiples rastreos secuenciales del mismo archivo) mediante un modelo de urna y análisis de intersecciones de conjuntos.

• El Modelo de Urna:
  • Se modela el espacio web rastreado como una urna con $N$ URLs únicas.
  • Turnover (Rotación): En cada paso de tiempo (entre rastreos consecutivos), una fracción $(1-\alpha)$ de las URLs desaparece y es reemplazada por nuevas, manteniendo $N$ constante. El parámetro $\alpha$ representa la persistencia temporal.
  • Muestreo: Cada rastreo extrae $M$ URLs de la urna.
• Intersección Temporal y Decaimiento:
  • La probabilidad de que una URL capturada en el tiempo $t=1$ reaparezca en el tiempo $T$ depende de su supervivencia ($\alpha^{T-1}$) y de la probabilidad de ser muestreada nuevamente ($M/N = c$).
  • La fracción esperada de superposición (contenimiento) entre dos rastreos separados por un tiempo $T$ se modela como:
    $$f(T) = c \cdot \alpha^{T-1}$$
  • Donde:
    • $c$: La cobertura absoluta (intercepto en $T=0$).
    • $\alpha$: La tasa de persistencia anual (pendiente en escala logarítmica).
• Procedimiento de Estimación:
  1. Calcular las intersecciones empíricas entre pares de rastreos ($g(u_i, u_j) = |u_i \cap u_j| / |u_i|$).
  2. Transformar los datos a escala logarítmica: $\log(g) = \log(c) + |i-j| \cdot \log(\alpha)$.
  3. Aplicar una regresión lineal (mínimos cuadrados ordinarios) para ajustar los datos observados.
  4. El intercepto de la regresión proporciona la estimación de la cobertura $c$, y la pendiente proporciona la tasa de decaimiento $\alpha$.
• Corrección de Sesgo: El modelo introduce un coeficiente de sesgo ($R_{ij}$) para detectar desviaciones del muestreo uniforme (ej. si el rastreador tiende a volver a los mismos subgrafos), aislado como el residuo en la regresión.

3. Contribuciones Clave

1. Método Autocontenido: Es la primera metodología capaz de estimar la cobertura absoluta de un rastreo sin necesidad de datos externos, verdades fundamentales (ground truth) o comparaciones con otros rastreadores.
2. Fundamentación Teórica: Conecta la teoría de modelos de urna (común en ecología para estimar poblaciones) con la dinámica de rastreo web, demostrando que las intersecciones temporales de un solo archivo pueden sustituir a las muestras independientes requeridas por métodos de captura-recaptura tradicionales.
3. Generalización: El enfoque es aplicable a cualquier rastreo enfocado longitudinal (focused crawl), independientemente de la configuración específica, siempre que existan múltiples iteraciones en el tiempo.

4. Resultados (Caso de Estudio: Web Académica Alemana)

El método se aplicó a la Web Académica Alemana (GAW), un conjunto de 15 rastreos semestrales realizados entre 2013 y 2021 (aprox. 100 millones de registros).

• Cobertura Estimada: Se determinó que cada rastreo captura aproximadamente el 46% del espacio de URLs rastreadas (cGAW) en el régimen de configuración estable.
• Persistencia de Contenido: La tasa de persistencia anual ($\alpha$) se estimó en 0.73, lo que implica una rotación anual de URLs del 27% y una vida media (half-life) de las URLs de aproximadamente 2.2 años. Esto es consistente con estudios previos sobre la vida media de la web.
• Tendencias Temporales: El análisis de regresiones individuales por año mostró una tendencia al alza en la cobertura a lo largo del tiempo (de 2013 a 2021), lo que sugiere una mejora en la eficiencia del rastreo o una reducción en el tamaño de la población rastreada.
• Validación: Los datos empíricos mostraron un ajuste excelente al modelo teórico ($R^2 = 0.95$), y las simulaciones estocásticas del modelo de urna replicaron perfectamente la relación observada.

5. Significado e Implicaciones

• Para Operadores de Archivos: Proporciona una herramienta interna para evaluar la calidad y completitud de sus archivos sin depender de recursos externos costosos o imposibles de obtener. Permite tomar decisiones informadas sobre la frecuencia de los rastreos basándose en la estabilidad de la población objetivo.
• Para Investigadores: Permite cuantificar la incertidumbre en los conjuntos de datos web utilizados para tareas de aprendizaje automático (como el entrenamiento de LLMs), sabiendo qué fracción del universo objetivo se ha capturado.
• Limitaciones:
  • Asume que el tamaño de la población ($N$) es relativamente constante durante el periodo de estudio (puede fallar en dominios de crecimiento explosivo).
  • La estimación es ponderada por la configuración del rastreo (sesgo de muestreo), no necesariamente una cobertura uniforme de todas las URLs teóricamente alcanzables.
  • Mide la cobertura a nivel de URL, no de contenido (una URL puede persistir pero cambiar drásticamente su contenido).

En conclusión, el artículo presenta un avance significativo en la metrología de la web, transformando la dinámica temporal de los archivos web en una métrica cuantitativa de cobertura absoluta, resolviendo una limitación fundamental en la ciencia de datos web.