Paper Review: WebTables: Exploring the Power of Tables on the Web

Title and Author of Paper

WebTables: Exploring the Power of Tables on the Web. M.J. Cafarella et al.

Summary

WebTables is a project to extract and process HTML tables from Google’s serach index. It attempts to answer two questions: what are some effective techniques for searching structured data at search engine scale, and what can be derived from analyzing a large corpus of HTML tables?

Web documents often contain structured and relational data embedded in HTML tables. The WebTables project extracted 14.1 billion English language HTML tables and further filtered those down to 154 million tables that contain structured data. From this data, we have the potential to determine semantic information embedded in the web, create visualizations, and integrate web documents into new applications.

By viewing HTML tables as small relational databases, we discover the problem of effectively exposing this data to search engine users. This requires ranking millions of small relational tables that each contain their own schema and set of tables, and matching ranked tables to user input.

Modelling Tables

Extracting Tables

The author’s wrote a system for automatically extracting tables from web documents. This used a combination of hand-written and statistically-trained classifiers to filter “good” results from “bad” ones. The actual extraction algorithm is the subject of a different paper and not described here. For the remainder of the paper, you can assume a corpus R of “relations” that are extracted from HTML documents.

Attribute Correlation Statistics

To rank HTML tables according to search criteria requires scoring the data using an algorithm tailored to table-based data. The authors compute some summary statistics, called the attribute correlation statistics database or ACSDb, for this task. These statistics allow for the calculation of the probability of seeing attributes within a given table’s schema. For example, p(address) is simply the sum of all counts c for pairs whose schema contains address divided by the total sum of all counts. The statistic also allows us to dtect relationships between attribute names. For example, p(address|name) returns the probability of having an attribute address in a relation, given that the attribute name exists.

The WebTables search engine uses the data model embedded in the ACSDb statistics to allow users to rank relations by relevance to a query, using a familiar (to search engines) keyword-based input. The author’s use this data to derive several ranking algorithms and combine them using a linear regression estimator scored by human judges. Some algorithms operate solely on word data and return results similar to a text-based search, other algorithms take advantage of the tables schema. The best performing algorithm is the schemaRank. This ranking scheme uses features of the table such as number of rows, number of columns, hits on header values, and hits on table body values, combined with a schema coherency score derived from the ACSDb.

Intuitively, the schema coherency score ranks tables based on how closely related the tables attributes are to one another.

Applications of the ACSDb

Having the data embedded in the ACSDb allows for a few novel applications. First, the ACSDb allows for schema auto-completion, and can be used to assist data base users that are designing a database system — the auto-complete system can guess appropriate attribute names based on previous data points.

A second application of the ACSDb is in suggestion attribute synonyms. This can help users find column headers that are synonyms of one another. This can also be used to help return valid search results.

Lastly, the database can be used to artificially “join” relations in a join graph. That is, related relations can be returned based on the schema information present in the search results.

The authors present experimental results for each of these applications, proving the usefulness of the ACSDb as a statistical measure for relation “table” data.

Conclusions

By extracting a search engine scale sample of HTML tables from web documents, the authors were able to drive the statistical ASCDb. The ASCDb can be used for some novel applications in search engine technology. This paper shows the value of using statistical analysis on large datasets, and provides some exploratory work in realizing the semantic information embedded in the web.

Like this post? Subscribe via RSS or email to never miss an update.