🔬 physics

Estimating Absolute Web Crawl Coverage From Longitudinal Set Intersections

This paper proposes a simple, ground-truth-free method to estimate the absolute coverage of a web crawl by modeling longitudinal URL overlaps between subsequent crawls as an urn process, which was applied to the German Academic Web to reveal approximately 46% coverage.

Original authors: Michael Paris, Grigori Paris, Fabian Baumann

Published 2026-03-17

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Michael Paris, Grigori Paris, Fabian Baumann

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the head librarian of a massive, ever-changing library called the German Academic Web. Every six months, your team sends out a fleet of robots to copy books from this library. You know exactly how many books your robots copied this time (let's say 100 million), but you have a nagging question: "How many books are actually in the library?"

Since the library is infinite and constantly changing (new books appear, old ones vanish), you can't just count them all. You don't have a master list, and you can't compare your work to another librarian's because you are the only one doing this specific job.

This paper presents a clever, simple trick to answer that question using only your own past records.

The Core Idea: The "Fishing Net" Analogy

Think of the web as a giant pond full of fish (URLs).

The Problem: You cast your net (the crawl) and catch 100 million fish. But you don't know how many fish are in the whole pond.
The Old Way: Usually, to guess the total number of fish, you'd need two different people to cast nets at the same time and see how many fish they caught in common. Or, you'd need a list of "famous fish" to see how many you missed.
The New Way (This Paper): You cast your net today. Then, you cast it again in six months, and again in a year. You look at the fish you caught today and ask: "How many of these are the same fish I caught last time?"

The Magic Formula: The "Urn" Model

The authors use a mathematical concept called an Urn Model. Imagine a giant urn (a jar) filled with colored balls representing every possible website.

The Turnover: Every time you come back to the pond, some fish die or swim away, and new ones are born. The authors found that about 27% of the websites disappear or change every year, while 73% stay the same.
The Overlap: When you cast your net twice, the number of fish you catch in both nets depends on two things:
- How many fish are actually in the pond (the total size).
- How many fish you managed to catch each time (your net size).

By looking at the pattern of overlap between your different catches over the years, you can work backward to figure out the size of the pond.

The "Self-Intersection" Trick

Here is the clever part:

If you catch a fish today, and you catch the exact same fish next time, it means your net is very good or the pond is small.
If you catch almost no fish in common with your previous catch, it means either your net is tiny, or the pond is so huge that you're barely scratching the surface.

The authors plotted their data on a graph. They looked at how the "overlap" dropped as the time between crawls got longer.

The Slope: The steepness of the drop told them how fast the web changes (the 27% turnover rate).
The Intercept: The starting point of the line (if they could magically catch two nets at the exact same moment) told them the Coverage.

The Result: You Caught 46%

When they applied this math to the German Academic Web, they found a surprising answer:

The Coverage: Their robots are actually capturing about 46% of all the academic websites that could be captured.
The Stability: The web is relatively stable; about 3 out of 4 websites stay the same from year to year.

Why This Matters

This is a big deal because:

No External Help Needed: You don't need a "perfect list" of websites to compare against. You just need your own history.
No Rival Librarians: You don't need to team up with another organization to compare notes.
Confidence: Now, if a researcher uses this data to train an AI, they know, "Okay, we have about half the picture. That's pretty good, but we're missing the other half."

The Limitations (The Fine Print)

The authors admit this isn't magic. It assumes:

The "pond" size isn't exploding or shrinking wildly during the study.
Your net catches fish somewhat randomly (not just the biggest, easiest-to-catch ones).
It works best if you have many snapshots over time (like the 15 crawls they used).

In a Nutshell

This paper teaches us how to guess the size of a moving target by looking at how much of it we've already hit, over and over again. It turns the "fog of war" of the internet into a clear, calculable map, showing us exactly how much of the academic world we've successfully archived.

1. Problem Statement

Web archives and focused crawls (e.g., targeting academic or government domains) collect vast amounts of data, but quantifying their completeness remains a fundamental challenge.

The Core Limitation: A single crawl defines a set of collected URLs ( $M$ ) based on a specific configuration, but the total size of the crawlable web space ( $N$ ) is unknown. Consequently, the absolute coverage ( $c = M/N$ ) cannot be determined from a single isolated crawl.
Limitations of Prior Approaches:
- Multi-crawler comparison: Methods like Bharat & Broder (1998) compare different engines to find relative sizes (e.g., Engine A is 2x larger than B) but cannot determine absolute coverage of the total web.
- Entity-based ground truth: Using external datasets (e.g., known university names) measures recall for specific entities but fails to capture the full URL space.
- Quality frameworks: Tools like SHARC assess page fidelity or temporal coherence but do not measure domain-wide coverage.

Goal: The authors propose a method to estimate absolute coverage using only the archive's own longitudinal data (a series of subsequent crawls), eliminating the need for external ground truth or multiple independent crawlers.

2. Methodology: The Urn Model

The authors model the web crawling process as a stochastic urn process to derive an analytical relationship between URL overlaps and coverage.

Theoretical Framework

The Urn: Represents the population of $N$ unique, crawlable URLs.
Time Steps ( $t$ ): Correspond to successive crawls.
Two Processes per Step:
1. Turnover (Decay): A fraction $(1-\alpha)$ of URLs are removed and replaced by new ones. The parameter $\alpha$ represents the temporal persistence of URLs between crawls.
2. Sampling: The crawler draws $M$ URLs uniformly at random (without replacement) from the current population.
Derivation of Overlap:
- The probability that a URL from crawl $t=1$ survives to crawl $t=T$ is $\alpha^{T-1}$ .
- The probability it is re-sampled in crawl $T$ is $M/N$ (the coverage $c$ ).
- The expected size of the intersection between two crawls separated by time $T$ is:
  $E[|u_1 \cap u_T|] = M \cdot \alpha^{T-1} \cdot \frac{M}{N} = \frac{M^2}{N} \alpha^{T-1}$
- Normalizing by the crawl size $M$ yields the expected containment fraction $f(T)$ :
  $f(T) = c \cdot \alpha^{T-1}$

Estimation Strategy

Log-Linear Regression: By taking the logarithm of the observed containment fraction $g(u_i, u_j) = |u_i \cap u_j| / M$ , the relationship becomes linear:
$\log(g) = \log(c) + |i-j| \cdot \log(\alpha)$
Parameter Extraction:
- Intercept ( $\log c$ ): The y-intercept of the regression line (where time difference $\Delta t = 0$ ) provides the estimate for absolute coverage ( $c$ ).
- Slope ( $\log \alpha$ ): The slope provides the decay rate (URL persistence).
Bias Correction: The model accounts for crawler bias (e.g., breadth-first traversal favoring specific subgraphs) by treating deviations from the theoretical uniform expectation as a residual term in the regression.

3. Key Contributions

Theoretical Insight: Formalizes web crawling as a simple urn process, linking set intersection theory to capture-recapture ecology models.
Methodological Innovation: Proposes the first method to estimate absolute coverage using longitudinal self-intersections from a single archive, removing the dependency on external ground truth or multiple crawlers.
Generalizability: The method is applicable to any focused longitudinal crawl configuration, provided multiple crawls exist over time.

4. Results: German Academic Web (GAW)

The method was applied to the German Academic Web (GAW), a focused crawl of ~150 German university domains conducted semi-annually from 2013 to 2021 (15 crawls, ~100M records each).

Data Visualization: A heatmap of pairwise containment showed a clear decay structure as the time difference between crawls increased.
Model Fit: The log-transformed containment data fit the theoretical model exceptionally well ( $R^2 = 0.95$ ).
Key Metrics:
- Absolute Coverage ( $c$ ): Approximately 46%. This means a single GAW crawl captures roughly 46% of the total crawlable academic web space.
- URL Persistence ( $\alpha$ ): Approximately 0.73 per year. This implies a 27% annual URL turnover rate.
- Half-life: The estimated URL half-life is ~2.2 years, consistent with prior web persistence studies (Koehler, 2002).
Temporal Trends: Regression analysis per crawl start date revealed a rising trend in coverage estimates over the 2013–2021 period, suggesting either improved crawl efficiency or a reduction in the total crawlable population size.

5. Significance and Implications

Self-Contained Assessment: Archive operators can now assess the completeness of their archives without needing external datasets, entity matching, or comparisons with other crawlers.
Downstream Applications: Knowing the sampling fraction ( $c$ ) is critical for researchers using web data for tasks like training Large Language Models (LLMs), as it quantifies the representativeness of the dataset.
Strategic Planning: The method distinguishes between a "replacement regime" (stable population size) and a "growth regime" (expanding population), helping operators decide on optimal crawl frequencies.
Limitations & Assumptions:
- Assumes the population size $N$ remains relatively constant during the observation window.
- Assumes sampling is approximately uniform (though the model corrects for bias via residuals).
- Measures URL-level coverage, not content-level coverage (a URL may persist while its content changes).

Conclusion

The paper successfully demonstrates that temporal self-intersections in longitudinal web archives can serve as a proxy for independent samples in capture-recapture models. By fitting a simple urn model to the decay of URL overlaps, the authors provide a robust, interpretable, and external-data-free method to estimate the absolute coverage of focused web crawls.