Prioritization of Domain-Specific Web Information Extraction

Jian Huang, Cong YuAAAI 2010 · DOI

Introduction

Information Extraction (IE) at the scale of the entire web is prohibitively expensive. Standard techniques—tokenizing, tagging, and running machine learning models—are too slow to run on every single page of the tens of billions on the internet. While traditional solutions use binary classifiers to filter irrelevant pages, this paper introduces Extraction Prioritization (EP). EP ranks web pages based on their expected "utility"—factoring in user demand, data novelty, and extractability—to ensure that the most valuable structured data is recovered first, even when computational resources are limited.

The Consensus Graph and Data Value

The core of the EP framework is the Consensus Graph (CG), a logical model representing extracted entities and their relationships. Instead of treating all data as equal, the system calculates a Consensus Graph Value. This metric incorporates real-world search demand (using query logs) and the principle of diminishing returns. For instance, extracting the 100th Chinese restaurant in Manhattan is considered less valuable than extracting the first one.

Example of extraction results organized into a logical graph structure, showing entities like restaurants with their associated attributes.

The Extraction Prioritization Framework

The EP system operates in batches, using a lightweight "scorer" to estimate a page's potential contribution before full processing. The utility of a page is determined by the probability that it is relevant and extractable, multiplied by the expected increase in the Consensus Graph's value.

By using "cheap" features like URLs, titles, and headers, the system can perform a "look-ahead" to find "gold nuggets" without the overhead of full extraction. This iterative process ensures that as the database grows, the system's definition of "novelty" evolves, preventing it from wasting cycles on redundant information. This allows the system to continuously re-evaluate the web's frontier to find the best remaining pages, rather than stopping after a fixed threshold.

Key Results and Performance

The researchers evaluated EP in the restaurant domain using 150,000 real user queries from Yahoo! Local logs. The system demonstrated massive efficiency gains over random sampling and traditional classifiers.

Accumulation of Consensus Graph (CG) Value over time for different strategies (metadata, content, combined) versus random selection.

Key findings include:

  • High ROI: On the focused corpus, EP strategies reached 85% of the total possible value after extracting only 9% of the pages.
  • Efficiency: Prioritization added only about 15% overhead in processing time but yielded 60% more value compared to non-prioritized approaches.
  • Superiority over Classifiers: The prioritization approach achieved significantly higher coverage than standard binary classifiers because it continues to hunt for the next most valuable piece of information rather than stopping at a fixed relevance threshold.

Conclusion

By treating search demand as a "North Star" and accounting for data novelty, Extraction Prioritization offers a scalable way to turn the "wild" web into useful structured data. Future work may explore more formal models for the tradeoff between redundancy (for corroboration) and novelty, as well as strategies for handling the dynamic nature of the web.

This summary is based on the paper "Prioritization of Domain-Specific Web Information Extraction".

Summary updated

BibTeX
@inproceedings{huang2010prioritization,
  author = {Jian Huang and Cong Yu},
  title = {{Prioritization of Domain-Specific Web Information Extraction}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2010},
  doi = {10.1609/aaai.v24i1.7500},
}
Figure