Web-scale extraction of structured data

ABSTRACT

A long-standing goal of Web research has been to construct a unified Web knowledge base. Information extraction techniques have shown good results on Web inputs, but even most domain-independent ones are not appropriate for Web-scale operation. In this paper we describe three recent extraction systems that can be operated on the entire Web (two of which come from Google Research). The TextRunner system focuses on raw natural language text, the WebTables system focuses on HTML-embedded tables, and the deep-web surfacing system focuses on "hidden" databases. The domain, expressiveness, and accuracy of extracted data can depend strongly on its source extractor; we describe differences in the characteristics of data produced by the three extractors. Finally, we discuss a series of unique data applications (some of which have already been prototyped) that are enabled by aggregating extractedWeb information.

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: M. Banko. Personal Communication, 2008.
• 3: M. Banko, M. J. Cafarella, S. Soderland, M. Broadhead, and O. Etzioni. Open Information Extraction from the Web. In IJCAI, 2007.
• 4: M. Banko and O. Etzioni. The Tradeoffs Between Open and Traditional Relational Extraction. In ACL, 2008.
• 5: L. Barbosa and J. Freire. Siphoning hidden-web data through keyword-based interfaces. In SBBD, 2004.
• 6: M. K. Bergman. The Deep Web: Surfacing Hidden Value. Journal of Electronic Publishing, 2001.
• 7: Sergey Brin, Extracting Patterns and Relations from the World Wide Web, Selected papers from the International Workshop on The World Wide Web and Databases, p.172-183, March 27-28, 1998
• 8: M. J. Cafarella, A. Halevy, Y. Zhang, D. Z. Wang, and E. Wu. Uncovering the Relational Web. In WebDB, 2008.
• 9: Michael J. Cafarella , Alon Halevy , Daisy Zhe Wang , Eugene Wu , Yang Zhang, WebTables: exploring the power of tables on the web, Proceedings of the VLDB Endowment, v.1 n.1, August 2008 [doi>10.1145/1453856.1453916]
• 10: Jamie Callan , Margaret Connell, Query-based sampling of text databases, ACM Transactions on Information Systems (TOIS), v.19 n.2, p.97-130, April 2001 [doi>10.1145/382979.383040]
• 11: Cars.com FAQ. http://siy.cars.com/siy/qsg/faqGeneralInfo.jsp#howmanyads.
• 12: Cazoodle Apartment Search. http://apartments.cazoodle.com/.
• 13: K. C.-C. Chang, B. He, and Z. Zhang. MetaQuerier over the Deep Web: Shallow Integration across Holistic Sources. In VLDB-IIWeb, 2004.
• 14: 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]
• 15: Bin He , Kevin Chen-Chuan Chang, Statistical schema matching across web query interfaces, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872784]
• 16: Bin He , Mitesh Patel , Zhen Zhang , Kevin Chen-Chuan Chang, Accessing the deep web, Communications of the ACM, v.50 n.5, p.94-101, May 2007 [doi>10.1145/1230819.1241670]
• 17: Marti A. Hearst, Automatic acquisition of hyponyms from large text corpora, Proceedings of the 14th conference on Computational linguistics, August 23-28, 1992, Nantes, France [doi>10.3115/992133.992154]
• 18: Panagiotis G. Ipeirotis , Luis Gravano, Distributed search over the hidden web: hierarchical database sampling and selection, Proceedings of the 28th international conference on Very Large Data Bases, p.394-405, August 20-23, 2002, Hong Kong, China
• 19: 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]
• 20: J. Madhavan, S. Jeffery, S. Cohen, X. Dong, D. Ko, C. Yu, and A. Halevy. Web-scale Data Integration: You can only afford to Pay As You Go. In CIDR, 2007.
• 21: J. Madhavan, D. Ko, L. Kot, V. Ganapathy, A. Rasmussen, and A. Halevy. Google's Deep-Web Crawl. In VLDB, 2008.
• 22: A. Ntoulas, P. Zerfos, and J. Cho. Downloading Textual Hidden Web Content through Keyword Queries. In JCDL, 2005.
• 23: Anish Das Sarma , Xin Dong , Alon Halevy, Bootstrapping pay-as-you-go data integration systems, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376702]
• 24: Fabian M. Suchanek , Gjergji Kasneci , Gerhard Weikum, Yago: a core of semantic knowledge, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242667]
• 25: P. P. Talukdar, J. Reisinger, M. Pasca, D. Ravichandran, R. Bhagat, and F. Pereira. Weakly Supervised Acquisition of Labeled Class Instances using Graph Random Walks. In EMNLP, 2008.
• 26: Trulia. http://www.trulia.com/.
• 27: Fei Wu , Daniel S. Weld, Autonomously semantifying wikipedia, Proceedings of the sixteenth ACM conference on Conference on information and knowledge management, November 06-10, 2007, Lisbon, Portugal [doi>10.1145/1321440.1321449]
• 28: Wensheng Wu , Clement Yu , AnHai Doan , Weiyi Meng, An interactive clustering-based approach to integrating source query interfaces on the deep Web, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007582]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Statistical computing

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Performance evaluation (efficiency and effectiveness)
          Nouns: World Wide Web (WWW)

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.7 Natural Language Processing
          Subjects: Text analysis

General Terms:
Algorithms, Design, Management, Measurement, Performance