WebTables: exploring the power of tables on the web

ABSTRACT

The World-Wide Web consists of a huge number of unstructured documents, but it also contains structured data in the form of HTML tables. We extracted 14.1 billion HTML tables from Google's general-purpose web crawl, and used statistical classification techniques to find the estimated 154M that contain high-quality relational data. Because each relational table has its own "schema" of labeled and typed columns, each such table can be considered a small structured database. The resulting corpus of databases is larger than any other corpus we are aware of, by at least five orders of magnitude.

We describe the WEBTABLES system to explore two fundamental questions about this collection of databases. First, what are effective techniques for searching for structured data at search-engine scales? Second, what additional power can be derived by analyzing such a huge corpus?

First, we develop new techniques for keyword search over a corpus of tables, and show that they can achieve substantially higher relevance than solutions based on a traditional search engine. Second, we introduce a new object derived from the database corpus: the attribute correlation statistics database (AcsDB) that records corpus-wide statistics on co-occurrences of schema elements. In addition to improving search relevance, the AcsDB makes possible several novel applications: schema auto-complete, which helps a database designer to choose schema elements; attribute synonym finding, which automatically computes attribute synonym pairs for schema matching; and join-graph traversal, which allows a user to navigate between extracted schemas using automatically-generated join links.

REFERENCES

• 1: Eugene Agichtein , Luis Gravano , Jeff Pavel , Viktoriya Sokolova , Aleksandr Voskoboynik, Snowball: a prototype system for extracting relations from large text collections, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.612, May 21-24, 2001, Santa Barbara, California, United States
• 2: Sanjay Agrawal , Surajit Chaudhuri , Gautam Das, DBXplorer: enabling keyword search over relational databases, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564782]
• 3: S. Bell and P. Brockhausen. Discovery of data dependencies in relational databases. In European Conference on Machine Learning, 1995.
• 4: T. Brants, A. C. Popat, P. Xu, F. J. Och, and J. Dean. Large language models in machine translation. In Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Language Learning, pages 858--867, 2007.
• 5: M. Cafarella, A. Halevy, Z. Wang, E. Wu, and Y. Zhang. Uncovering the relational web. In under review, 2008.
• 6: M. J. Cafarella, D. Suciu, and O. Etzioni. Navigating extracted data with schema discovery. In Web DB, 2007.
• 7: Hsin-Hsi Chen , Shih-Chung Tsai , Jin-He Tsai, Mining tables from large scale HTML texts, Proceedings of the 18th conference on Computational linguistics, p.166-172, July 31-August 04, 2000, Saarbrücken, Germany [doi>10.3115/990820.990845]
• 8: Kenneth Ward Church , Patrick Hanks, Word association norms, mutual information, and lexicography, Proceedings of the 27th annual meeting on Association for Computational Linguistics, p.76-83, June 26-29, 1989, Vancouver, British Columbia, Canada [doi>10.3115/981623.981633]
• 9: Robin Dhamankar , Yoonkyong Lee , AnHai Doan , Alon Halevy , Pedro Domingos, iMAP: discovering complex semantic matches between database schemas, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007612]
• 10: AnHai Doan , Pedro Domingos , Alon Y. Halevy, Reconciling schemas of disparate data sources: a machine-learning approach, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.509-520, May 21-24, 2001, Santa Barbara, California, United States
• 11: Oren Etzioni , Michael Cafarella , Doug Downey , Stanley Kok , Ana-Maria Popescu , Tal Shaked , Stephen Soderland , Daniel S. Weld , Alexander Yates, Web-scale information extraction in knowitall: (preliminary results), Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988687]
• 12: Wolfgang Gatterbauer , Paul Bohunsky , Marcus Herzog , Bernhard Krüpl , Bernhard Pollak, Towards domain-independent information extraction from web tables, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242583]
• 13: Bin He , Zhen Zhang , Kevin Chen-Chuan Chang, Knocking the door to the deep Web: integrating Web query interfaces, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007691]
• 14: Vagelis Hristidis , Yannis Papakonstantinou, Discover: keyword search in relational databases, Proceedings of the 28th international conference on Very Large Data Bases, p.670-681, August 20-23, 2002, Hong Kong, China
• 15: Dekang Lin , Patrick Pantel, DIRT @SBT@discovery of inference rules from text, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.323-328, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502559]
• 16: Jayant Madhavan , Philip A. Bernstein , AnHai Doan , Alon Halevy, Corpus-Based Schema Matching, Proceedings of the 21st International Conference on Data Engineering, p.57-68, April 05-08, 2005 [doi>10.1109/ICDE.2005.39]
• 17: Jayant Madhavan , Philip A. Bernstein , Erhard Rahm, Generic Schema Matching with Cupid, Proceedings of the 27th International Conference on Very Large Data Bases, p.49-58, September 11-14, 2001
• 18: J. Madhavan, A. Y. Halevy, S. Cohen, X. L. Dong, S. R. Jeffery, D. Ko, and C. Yu. Structured data meets the web: A few observations. IEEE Data Eng. Bull., 29(4): 19--26, 2006.
• 19: Christopher D. Manning , Hinrich Schütze, Foundations of statistical natural language processing, MIT Press, Cambridge, MA, 1999
• 20: Imran R. Mansuri , Sunita Sarawagi, Integrating Unstructured Data into Relational Databases, Proceedings of the 22nd International Conference on Data Engineering, p.29, April 03-07, 2006 [doi>10.1109/ICDE.2006.83]
• 21: R. Miller and P. Andritsos. Schema discovery. IEEE Data Eng. Bull., 26(3):40--45, 2003.
• 22: Arnab Nandi , H. V. Jagadish, Assisted querying using instant-response interfaces, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247640]
• 23: Flexible Web Document Analysis for Delivery to Narrow-Bandwidth Devices, Proceedings of the Sixth International Conference on Document Analysis and Recognition, p.1074, September 10-13, 2001
• 24: Erhard Rahm , Philip A. Bernstein, A survey of approaches to automatic schema matching, The VLDB Journal — The International Journal on Very Large Data Bases, v.10 n.4, p.334-350, December 2001 [doi>10.1007/s007780100057]
• 25: Peter D. Turney, Mining the Web for Synonyms: PMI-IR versus LSA on TOEFL, Proceedings of the 12th European Conference on Machine Learning, p.491-502, September 05-07, 2001
• 26: Yalin Wang , Jianying Hu, A machine learning based approach for table detection on the web, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511478]
• 27: Ian H. Witten , Eibe Frank, Data Mining: Practical Machine Learning Tools and Techniques, Second Edition (Morgan Kaufmann Series in Data Management Systems), Morgan Kaufmann Publishers Inc., San Francisco, CA, 2005
• 28: S. K. M. Wong , C. J. Butz , Y. Xiang, Automated database schema design using mined data dependencies, Journal of the American Society for Information Science, v.49 n.5, p.455-470, April 15, 1998 [doi>10.1002/(SICI)1097-4571(19980415)49:5<455::AID-ASI7>3.3.CO;2-D]
• 29: M. Yoshida and K. Torisawa. A method to integrate tables of the world wide web. In Proceedings of the 1st International Workshop on Web Document Analysis, pages 31--34, 2001.
• 30: R. Zanibbi, D. Blostein, and J. Cordy. A survey of table recognition: Models, observations, transformations, and inferences, 2003.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT