Wild Card Queries for Searching Resources on the Web

Davood Rafiei, Haobin LiarXiv 2009 · arXiv

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:

  1. Query Flattening: Semantic wild cards are replaced with similar terms from thesauri to generate base queries.
  2. Query Rewriting: Queries are transformed using linguistic rules, such as active-to-passive voice conversion or hyponym pattern application (e.g., "movies such as %").
  3. Retrieval: Expanded queries are processed via search engine APIs. The system isolates noun phrases from the resulting text snippets at the % positions.
  4. 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.

Figure 1: Average precision for US states increases as the number of query rewritings grows from 2 to 4, demonstrating the consensus filter effect.

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.
Figure 6: Precision-recall curves for US states (top) and Country names (bottom) comparing PT-hits against various baselines and state-of-the-art systems.

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

Abstract

We propose a domain-independent framework for searching and retrieving facts and relationships within natural language text sources. In this framework, an extraction task over a text collection is expressed as a query that combines text fragments with wild cards, and the query result is a set of facts in the form of unary, binary and general $n$-ary tuples. A significance of our querying mechanism is that, despite being both simple and declarative, it can be applied to a wide range of extraction tasks. A problem in querying natural language text though is that a user-specified query may not retrieve enough exact matches. Unlike term queries which can be relaxed by removing some of the terms (as is done in search engines), removing terms from a wild card query without ruining its meaning is more challenging. Also, any query expansion has the potential to introduce false positives. In this paper, we address the problem of query expansion, and also analyze a few ranking alternatives to score the results and to remove false positives. We conduct experiments and report an evaluation of the effectiveness of our querying and scoring functions.
BibTeX
@misc{rafiei2009wild,
  author = {Davood Rafiei and Haobin Li},
  title = {{Wild Card Queries for Searching Resources on the Web}},
  year = {2009},
  eprint = {0908.2588},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/0908.2588},
}
Figure