Answering Table Augmentation Queries from Unstructured Lists on the Web

Rahul Gupta, Sunita SarawagiPVLDB 2009 · OpenReview

TL;DR

This paper introduces WWT, a system that automatically builds tables from unstructured web lists based on a few example rows. It tackles the challenge of extracting and consolidating information from noisy, diverse web data to answer "show me more like these" queries, achieving impressive recall even with limited examples.

What Problem Does This Paper Address?

Imagine you're researching a topic and find a few interesting facts, but you want to see more. You might search for "topic facts" and get a flood of irrelevant documents. Or, if you're building a knowledge base like Freebase or Wikipedia, you might have a few seed records and want to automatically find more to populate a table. The core problem is how to intelligently extract and integrate structured data from the vast, messy landscape of unstructured web lists (like HTML <ul> or <ol> tags) when you only have a handful of examples to guide the process. Existing search engines are document-centric, and while some systems can extract from structured tables, handling unstructured lists with arbitrary schemas and noise is a significant challenge.

Methods

WWT employs a multi-stage, end-to-end pipeline:

  • List Selection & Indexing: The system first crawls the web, filters out irrelevant lists using heuristics (e.g., list size, record length), and indexes the remaining ~16 million lists using Lucene for efficient retrieval.
  • Resolver: For a given query table (the example rows), WWT infers column types and builds "resolvers." A cell resolver scores how well a text string matches a specific cell in a query row, while a row resolver scores how similar two query rows are. This is crucial for understanding the query's schema and content.
  • Extractor: This is the heart of the system. It uses the resolvers to create labeled training data from the selected web lists. WWT proposes two main extraction strategies:
  • Edefault: Independently trains a statistical model (specifically, a semi-Markov Conditional Random Field or CRF) for each list.
  • Estaged: A multi-stage approach that leverages content overlap across lists. It iteratively trains models, using information from previously processed lists to improve extraction from subsequent ones.
  • The extractor also incorporates novel techniques like alignment features (using multiple sequence alignment to capture list structure) and soft labeling (allowing for more flexible matches beyond exact string equality).
  • Consolidator: Merges the tables extracted from individual lists into a single, unified table. It uses a Bayesian network-based row resolver to handle noisy extractions and missing data, aiming to create more complete rows by combining information from multiple sources.
  • Ranker: Orders the rows in the consolidated table based on a combination of correctness scores from the extractor and support from various sources. They propose several ranking schemes, moving beyond simple additive counts to more sophisticated methods like "Cell_Softmax" that consider cell importance and individual cell correctness probabilities.

Datasets

  • Web Crawl: The system uses a large web crawl of approximately 500 million pages to extract HTML lists.
  • Wikipedia Tables: For evaluation, the authors created a benchmark using 65 Wikipedia tables. They constructed query tables by sampling 3 to 10 rows from these Wikipedia tables.
  • Ground Truth: For each Wikipedia target table, they manually created ground truth by identifying relevant lists, mapping list records to target rows, and annotating correct segmentations. This process also identified "new" relevant rows not present in the original Wikipedia tables.

Key Insights and Ideas

  • "Show me more like these" is a powerful query paradigm: The paper demonstrates that even a small number of example rows can be highly effective for guiding information extraction from the web.
  • Unstructured lists are a rich, yet challenging, data source: The abundance of HTML lists on the web offers a vast resource, but their inherent noise, lack of schema, and stylistic variations make extraction difficult.
  • Leveraging cross-list information is key: The "Estaged" extractor and the sophisticated "Consolidator" highlight the importance of integrating information from multiple sources to overcome individual list limitations and improve accuracy.
  • Beyond simple counts for ranking: The paper shows that simple ranking based on the number of sources supporting a row is insufficient. More advanced methods that consider extraction confidence and cell importance are crucial for presenting high-quality results.
  • CRFs are robust for noisy data: The use of Conditional Random Fields (CRFs) for statistical text segmentation proves effective in handling the irregularities of human-generated web lists.

Key Results

  • High Recall: WWT achieves a recall of 55% with just three query rows, increasing to almost 70% with seven query rows, even with a stringent evaluation metric.
  • Speed: Queries are typically answered in around 20-30 seconds, demonstrating practical usability.
  • Extractor Improvements: Modifications to the default extractor (soft labeling, staged extraction, alignment features) significantly boost F1 scores, particularly for small query sizes and difficult queries. For instance, F1 scores increased from 76.8% to 80.8% with modifications for a query size of three.
  • Ranking Effectiveness: Advanced ranking methods like Cell_Softmax significantly outperform simpler methods (Additive, Softmax) in terms of true positive rate, especially for retrieving relevant rows early.

Limitations and Future Work

  • Limitations:
    • The system's performance can be affected by the quality and relevance of the initial web crawl and list selection.
  • The "Estaged" extractor's performance can be sensitive to errors in earlier stages.
  • The definition of "difficult queries" (less than 60% of target rows in relevant lists) highlights a specific challenge area.
  • Future Work:
    • Extend WWT to incorporate other structured web sources like HTML tables and logical lists.
  • Further explore more sophisticated methods for integrating diverse web data sources.
  • Investigate user-driven approaches for setting column importance scores.

Summary updated

BibTeX
@article{gupta2009answering,
  author = {Rahul Gupta and Sunita Sarawagi},
  title = {{Answering Table Augmentation Queries from Unstructured Lists on the Web}},
  journal = {Proc. VLDB Endow.},
  year = {2009},
  url = {https://openreview.net/forum?id=vm8ufo2uqkt},
}
Figure