Automatic Wrappers for Large Scale Web Extraction

Nilesh N. Dalvi, Ravi Kumar, Mohamed A. Soliman

TL;DR

This paper introduces a noise-tolerant framework for "wrapper induction"—the process of automatically learning rules to extract structured data from websites. By treating automated (and often incorrect) annotations as noisy signals rather than absolute ground truth, the system can learn high-quality extraction rules across thousands of websites without manual human labeling.

What Problem Does This Paper Address?

Websites often use scripts to generate pages from databases (e.g., store locators, product catalogs). To extract this data, researchers use "wrappers"—sets of rules (like XPath) that identify where specific data fields live in the HTML.

The traditional bottleneck is supervision. Standard wrapper induction requires a human to manually label examples on every single website to "teach" the algorithm. While we can use automated tools (like dictionaries of business names) to label data quickly, these tools are "noisy"—they make mistakes, miss items, or label the wrong text. In traditional systems, a single incorrect label can cause the induction algorithm to "over-generalize," resulting in a rule that extracts useless junk. This paper tackles how to build wrappers that are robust enough to ignore that noise and find the underlying structure.

Methods

The authors propose a "generate-and-test" framework that treats wrapper induction as a probabilistic inference problem.

  1. The Probabilistic Model: They define the extraction goal as finding the most likely data mapping ($X$) given a set of noisy labels ($L$). This is expressed as maximizing $P(L|X)P(X)$.
  2. $P(L|X)$ (Annotation Model): This accounts for the noise. It models the probability that an annotator (with a known precision and recall) would produce the observed labels if $X$ were the true data.
  3. $P(X)$ (Web Publication Model): This models the "goodness" of the resulting list. It assumes that "good" wrappers produce lists with high structural regularity (consistent schema size and visual alignment).
  4. Efficient Enumeration: Since there are an exponential number of label subsets to test, the authors developed two algorithms to find all unique wrappers efficiently:
  5. BottomUp: A black-box algorithm that works with any "well-behaved" wrapper inductor.
  6. TopDown: A faster algorithm designed for "feature-based" inductors (like XPath or prefix-suffix rules).
  7. Ranking: Once a set of candidate wrappers is generated, the probabilistic model ranks them. The "winner" is the one that best explains the noisy labels while producing the most structurally consistent output.

Datasets

The authors evaluated their system on three distinct domains:

  • DEALERS: 330 store locator websites (e.g., furniture, electronics). Labels were generated using a database of 600,000 business names.
  • DISC: 15 music discography sites. Labels were generated from a list of 11 popular albums.
  • PRODUCTS: 10 shopping websites focused on cellphones. Labels were generated from a dictionary of 463 cellphone models.

Key Insights and Ideas

  • Structure as a Quality Signal: The "aha moment" is that we don't need perfect training data if we understand what a "good" result looks like. A correct wrapper will produce a list where items are aligned and have similar internal structures; a noisy wrapper will produce a "messy" list.
  • Wrappers are "Well-Behaved": The authors prove that common wrapper languages (like XPath) satisfy properties like monotonicity and closure. This allows them to prune the search space of possible wrappers from billions down to a manageable few.
  • Handling "Infeasible" Tasks: Traditional site-level supervision is impossible at web-scale. By moving to a domain-centric approach (e.g., "find all business names everywhere"), the system can leverage existing dictionaries to bootstrap extraction across the entire web.

Key Results

  • High Precision: On the DEALERS dataset using XPath wrappers, the noise-tolerant framework achieved nearly 1.0 precision and recall, whereas a "naive" induction approach (which trusts all labels) saw precision drop significantly due to over-generalization.
  • Efficiency: The TopDown algorithm was highly performant, finishing in under a second for most websites, making it viable for production environments.
  • Robustness: The system remained effective even when the automated annotators had very low recall (missing many items) or mediocre precision, provided the underlying page structure was regular.

Limitations and Future Work

  • Structural Dependency: The method relies on pages being script-generated and having a repeating structure. It may struggle with highly irregular or "hand-crafted" pages where the $P(X)$ "goodness" signal is weak.
  • Single-Entity Extraction: While the framework works for pages containing a single entity (like a single product page), it loses the powerful "list alignment" signal used in the ranking model, making it more dependent on the quality of the initial noisy labels.
  • Schema Mapping: The paper primarily focuses on extracting a single type or pre-defined types. Future work could involve more complex schema discovery where the system learns the attributes of an entity entirely on its own.

Summary updated

BibTeX
@article{dalvi2011automatic,
  author = {Nilesh N. Dalvi and Ravi Kumar and Mohamed A. Soliman},
  title = {{Automatic Wrappers for Large Scale Web Extraction}},
  journal = {Proc. VLDB Endow.},
  year = {2011},
  url = {https://openreview.net/forum?id=A1cPCEWxLB},
}

Loading related content...

Figure