PaperlayerView exact revision on arXiv

Source-linked AI summary

Answering Table Queries on the Web using Column Keywords

Rakesh Pimplikar, Sunita Sarawagi

arXiv:1207.0132v1cs.DB

TL;DR

The paper addresses how to answer multi-column keyword queries using diverse and redundant Web tables rather than free-format text. WWT jointly maps table relevance and column assignments with a graphical model that combines table, corpus, and column-overlap evidence. On 59 queries, it improves F1 from 65% for baseline IR to 70%.

  • Problem

    The task is to determine which Web tables are relevant to a multi-column keyword query and map their columns to the requested query columns.

  • Method

    WWT uses graphical-model inference to jointly label tables and columns, combining segmented query matching, diverse table clues, corpus statistics, and content overlap.

  • Results

    F1 accuracy improves from 65% with a baseline IR method to 70% using WWT on 59 queries.

  • Takeaways & Limitations

    The system produces a single structured multi-column table by consolidating relevant columns and rows from multiple Web tables.

  • Takeaways & Limitations

    The method must handle noisy headers and context, missing headers, and irrelevant tables that can distort column-overlap signals.

Abstract

from arXiv · show

We present the design of a structured search engine which returns a multi-column table in response to a query consisting of keywords describing each of its columns. We answer such queries by exploiting the millions of tables on the Web because these are much richer sources of structured knowledge than free-format text. However, a corpus of tables harvested from arbitrary HTML web pages presents huge challenges of diversity and redundancy not seen in centrally edited knowledge bases. We concentrate on one concrete task in this paper. Given a set of Web tables T1, . . ., Tn, and a query Q with q sets of keywords Q1, . . ., Qq, decide for each Ti if it is relevant to Q and if so, identify the mapping between the columns of Ti and query columns. We represent this task as a graphical model that jointly maps all tables by incorporating diverse sources of clues spanning matches in different parts of the table, corpus-wide co-occurrence statistics, and content overlap across table columns. We define a novel query segmentation model for matching keywords to table columns, and a robust mechanism of exploiting content overlap across table columns. We design efficient inference algorithms based on bipartite matching and constrained graph cuts to solve the joint labeling task. Experiments on a workload of 59 queries over a 25 million web table corpus shows significant boost in accuracy over baseline IR methods.

1. INTRODUCTION

WWT turns sets of column keywords into a consolidated multi-column table by jointly mapping relevant Web-table columns. It addresses noisy, diverse tables with query segmentation, cross-table overlap, and graphical-model inference, improving F1 from 65% to 70% on 59 queries.

  • WWT returns one consolidated q-column table by extracting and mapping relevant columns from multiple Web tables.The system is designed for entity queries and multi-ary relationships expressed as keyword sets for desired columns.
  • The task jointly decides whether each Web table is relevant and how its columns map to query columns.Column mapping is harder than whole-table relevance ranking because both queries and Web tables provide limited column-specific information.
  • WWT combines column-header clues with table context and body, query segmentation, corpus statistics, and content overlap across columns.The graphical model jointly labels columns across tables while incorporating diverse within-table and cross-table signals.
  • F1 accuracy rises from 65% with a baseline IR method to 70% with WWT on a workload of 59 queries.

2. ARCHITECTURE

WWT builds a searchable corpus of extracted Web tables, retrieves candidates through keyword and conservative overlap probes, maps their columns, and consolidates supported rows into one ranked answer table.

  • WWT extracts relational tables from a 500-million-page crawl, retaining about 25 million data tables after filtering HTML table tags.The retained tables are indexed as Lucene documents with header, context, and content fields.
  • Header extraction handles tables whose headers are indicated by visual, layout, or content markers rather than HTML header tags.Only 20% of the 25 million tables used the designated th tag for headers.
  • Context extraction gathers scored text nodes near the table in the parent document to represent what the table is about.
  • The architecture retrieves candidates with a keyword probe, then uses high-confidence tables and sampled rows for a conservative content-overlap probe.This strategy limits noise from arbitrarily retrieving all tables overlapping with initially retrieved tables.
  • The column mapper assigns table relevance and column-level mappings with calibrated scores used for later retrieval and ranking.
  • The consolidator merges relevant columns and rows, removes duplicate rows, and the ranker places more relevant and supported rows first.

3. DESIGNING THE COLUMN MAPPER

The column mapper replaces separate relevance and similarity decisions with a graphical model that jointly labels tables and columns using heterogeneous evidence. Its design addresses noisy contexts, ambiguous headers, missing headers, and unreliable overlap heuristics.

  • A basic TF-IDF thresholding approach is unreliable because context can be verbose, headers can be noisy, and some tables lack headers or useful context.
  • The mapper jointly combines diverse clues within and across tables instead of independently deciding relevance and column matches.
  • The model uses node, edge, and higher-order potentials to represent dependencies among table and column labels.Graphical-model inference seeks a highest-scoring joint assignment, but large cliques make exact inference intractable.

3.1 Variables

The variable design represents table relevance explicitly and assigns each column either a query-column label or no-match label.

  • The graphical model has one binary relevance variable for each Web table and one label variable for each table column.
  • Each column variable takes one of the q query-column labels or the special no-match label na.

3.2 Node Potentials

Node potentials score how well each table column matches a query column by combining segmented header matching with evidence from other table regions and corpus-wide signals.

  • 3.2.1 Matching Query Keywords to Table Columns: The segmentation model addresses split query evidence, multi-row headers, body-only matches, and support from other column headers.Examples include “Nobel prize winner,” “Black metal bands,” and “dog breeds.”
  • 3.2.1 Matching Query Keywords to Table Columns: SegSim segments query keywords into a header-matched part and an evidence-gathering part, allowing matches across context, titles, headers, and body content.It maximizes a weighted score over query segmentations and header rows.
  • 3.2.1 Matching Query Keywords to Table Columns: SegSim combines TF-IDF cosine similarity for the header segment with soft-maxed reliability across five external table regions.The regions are title, context, other headers in the column, other columns’ headers, and frequent body content.
  • 3.2.1 Matching Query Keywords to Table Columns: SegSim reduces to concatenated-header or single-best-row matching in their respective clean and noisy multi-row-header extremes.Repeated matches increase the score with exponentially decaying influence, while a nonzero header match keeps table-level evidence column-specific.
  • 3.2 Node Potentials: Additional node features reward query-term coverage, keyword-column co-occurrence across the corpus, and overall table relevance.The node representation combines these signals through weighted features and a negative bias against very small similarities.

3.3 Edge Potentials

Edge potentials transfer labeling information between similar columns across tables, while normalization, confidence filtering, and one-to-one matching limit misleading propagation.

  • 3.3 Edge Potentials: The basic edge potential rewards similar columns receiving the same label, but irrelevant tables can overwhelm relevant columns through numerous similar neighbors.This failure motivates the custom edge potential.
  • 3.3 Edge Potentials: Similarity is normalized so each column’s total similarity to neighboring columns is bounded, with smoothing and a 0.1 neighbor threshold.The smoothing constant is λ = 0.3, and normalized similarities are asymmetric before symmetric edge construction.
  • 3.3 Edge Potentials: Edges are added across tables only when at least one column has confident independent labeling, using a 0.6 probability threshold.Confidence is estimated from node-potential label probabilities.
  • 3.3 Edge Potentials: For each table pair, bipartite max matching connects each column to at most one counterpart, reducing transfer errors when within-table columns resemble one another.The matching uses weighted content and header similarity.

3.4 Table-level Potentials

Table-level potentials enforce consistent relevance and column mappings by constraining the joint labels assigned to every column in a table.

  • 3.4 Table-level Potentials: Four hard constraints enforce table-level consistency: mutual exclusion, all-irrelevant labeling, first-column matching, and minimum query-column coverage.These constraints assign large negative values to inconsistent labelings.
  • 3.4 Table-level Potentials: The mutex constraint permits at most one table column to map to each query column.It prevents duplicate assignments within a table.
  • 3.4 Table-level Potentials: The all-Irr constraint makes a table irrelevant whenever any one of its columns receives the irrelevant label.This converts column-level decisions into a consistent table-level relevance decision.
  • 3.4 Table-level Potentials: Every relevant table must contain the first query column and, for queries with q ≥2, at least two query columns.The latter is the chosen minimum-match threshold.
  • 3.4 Table-level Potentials: The overall objective maximizes node, edge, and table-consistency potentials over all column labels, with six parameters selected using labeled data.The six parameters are tuned by exhaustive enumeration because the parameter count is small.

4. INFERENCE ALGORITHMS

The inference framework combines table-level and cross-table potentials to jointly assign query-column labels, using exact matching where possible and approximations for the full NP-hard objective.

  • The full column-labeling objective is NP-hard, so the paper develops approximation algorithms alongside an exact solution when edge potentials are absent.The approximations are organized into table-centric and edge-centric approaches.
  • Table-independent inference: Without edge potentials, each table is solved independently as a capacitated maximum-weight bipartite matching between table columns and query labels.The special na label absorbs unmatched columns, while capacities enforce matching constraints.
  • Table-centric collective inference: The table-centric collective method first computes per-column max-marginals, converts them into distributions, aggregates neighbor messages, and updates table potentials before re-solving each table.This approach gives table-level constraints more importance than cross-table edge potentials.
  • Max-marginals: Max-marginals are computed efficiently from one optimal matching and residual-graph shortest paths rather than repeated matching calls for every column-label pair.Bellman-Ford is used because residual edge costs can be negative, with q + 1 shortest-path computations.
  • Maximum-weight bipartite matching: The matching problem is reduced to minimum-cost maximum flow by representing capacities, zero-cost source and sink edges, and negated matching weights in a directed graph.Positive-flow left-to-right edges form the final matching.
  • Edge-centric collective inference: The edge-centric alternative formulates inference as a constrained minimum s-t cut, which is NP-hard under per-table group constraints and is approximated within a factor of two.The groups correspond to columns belonging to the same table, with at most one group vertex allowed on the t side.

5. EXPERIMENTS

Experiments evaluate WWT against baseline and augmented methods on 59 queries over 25 million Web tables, measuring column-mapping accuracy, answer quality, runtime, similarity modeling, and collective inference.

  • 5.1 Overall Comparison: 30.3% overall error made WWT more accurate than Basic and PMI2 at 34.7% and NbrText at 34.2%.The comparison covers seven query groups and uses Basic as the reference for error reduction.
  • 5.1 Overall Comparison: PMI2 provided no overall accuracy boost and increased average query time from 6.3 seconds for Basic to 40 seconds.PMI2 reduced error for some queries but increased it for an equal number, while WWT averaged 6.7 seconds.
  • 5.1 Overall Comparison: WWT improved final consolidated-answer accuracy in all evaluated cases.Answer quality compares rows from the true column mapping with rows from alternative mappings.
  • 5.1 Overall Comparison: WWT’s average runtime was 6.7 seconds, ranging from 1.5 to 14 seconds, with column mapping taking a negligible fraction.Runtime depends mainly on index probing, raw-table size, and the number of rows consolidated.
  • 5.2 Evaluating Segmented Similarity: 30.3% error with segmented similarity improved on 33.3% with standard unsegmented similarity.The models were otherwise identical and separately retrained for each similarity measure.
  • 5.3 Comparing Collective Inference Methods: 30.3% error from the Table-centric algorithm was roughly 3% lower than independent table labeling, outperforming constrained α-expansion, BP, and TRWS.The authors attribute weaker BP and TRWS performance to dissociative edge potentials introduced by mutex constraints.

6. RELATED WORK

The paper situates its multi-column Web-table search task among structured Web search, Web-table search, keyword database queries, and schema matching. Its setting differs from prior clean databases because it matches a few query columns against many noisy, unlinked Web tables.

  • Structured Web search has mainly answered point queries from document sources, whereas this work targets a single consolidated table as the answer.
  • Prior Web-table systems retrieved ranked tables for topic queries and relied on user interactions, rather than directly supporting ad hoc relationships or attribute sets.
  • Keyword search research has increasingly addressed structured annotation of queries over clean databases, product catalogs, and ontologies.
  • This task resembles schema matching but aligns a few query columns with many unlinked and noisy Web tables instead of consistent database schemas.

7. CONCLUSION

The paper presents a graphical-model system that maps query columns to relevant Web-table columns and consolidates them into multi-column answers. On 25 million Web tables, it reports a 12% error reduction over a baseline, while identifying newer corpus statistics and alternative sources as future directions.

  • 12% error reduction relative to a baseline was achieved on a realistic query workload and a database of 25 million Web tables.
  • The graphical model jointly decides table relevance and column mappings using table matches, corpus-wide co-occurrence statistics, and content overlap.
  • Future work includes newer corpus-wide co-occurrence statistics, ontologies, faceted search, and user feedback.
Loading 1207.0132v1…