Introduction
Extracting structured data from the vast, unorganized Web remains a significant challenge. Traditional methods often rely on brittle, site-specific "wrappers" or computationally expensive Natural Language Processing (NLP) techniques that struggle to scale. Furthermore, the inherent flexibility of natural language means that simple keyword searches often fail to capture the full breadth of relevant information. For instance, a search for "Canadian writers" might overlook pages describing "authors from Canada" or "Canadian novelists."
This paper introduces DeWild, a lightweight, domain-independent framework designed to extract facts using natural language queries enhanced with wild cards. By leveraging semantic query expansion and a novel ranking algorithm, DeWild achieves high recall and precision without the need for complex wrappers or heavy NLP.
Methodology
The DeWild system utilizes a query interface centered around two primary wild cards:
- Extraction Target (
%): Identifies noun phrases to be extracted (e.g.,"% is a summer movie"). - Semantic Expansion (
*): Indicates that a term should be expanded to include synonyms and related concepts (e.g.,*movie*might expand to "film" or "motion picture").
The extraction process follows a four-stage pipeline:
- Query Flattening: Semantic wild cards are replaced with similar terms from thesauri to generate base queries.
- Query Rewriting: Queries are transformed using linguistic rules, such as active-to-passive voice conversion or hyponym pattern application (e.g., "movies such as %").
- Retrieval: Expanded queries are processed via search engine APIs. The system isolates noun phrases from the resulting text snippets at the
%positions. - Relevance Ranking (PT-hits): To filter noise, the system employs the PT-hits algorithm. Based on the HITS algorithm, PT-hits uses a bipartite graph between query patterns and extracted tuples. It operates on a mutual reinforcement principle: a high-quality tuple is one extracted by many reliable patterns, and a reliable pattern is one that consistently extracts valid tuples.
Key Insights: The Power of Consensus
A critical finding of this research is that increasing the number of query rewritings actually improves precision—a counterintuitive result in traditional Information Retrieval. Because the PT-hits algorithm requires consensus across multiple, semantically distinct patterns, more rewritings create a more rigorous filter for "false positive" data.
Furthermore, the system demonstrates that search engine snippets provide sufficient context for accurate extraction, significantly reducing the network and processing overhead associated with downloading full web pages.
Evaluation and Results
The authors evaluated DeWild across several benchmarks, including the AOL query log, TREC 2004 QA tracks, and specific entity lists like US states and country names.
Performance Benchmarks
- Question Answering: On the AOL dataset, DeWild achieved a precision of 0.68, doubling the performance of the open-source QA system OpenEphyra (0.32).
- Entity Extraction: In the US states task, PT-hits maintained perfect precision (1.0) up to a recall of 0.8, significantly outperforming frequency counts, Mutual Information (MI) rankings, and the KnowItAll system.
Real-World Utility
In an ad hoc task to identify "Canadian writers," DeWild discovered 156 valid entities in its top 200 results. Notably, 58 of these writers were absent from major online academic directories, highlighting the system's ability to uncover information missing from curated datasets.
Conclusion
DeWild provides a scalable, effective solution for Web-scale fact extraction. By combining simple wild card queries with the mutually reinforcing PT-hits ranking algorithm, the system effectively filters Web noise to produce high-quality structured data. Future work will explore more complex wild card types and specialized indexing to further enhance semantic search capabilities.
Summary updated