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.
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.
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