Google's Deep Web crawl

ABSTRACT

The Deep Web, i.e., content hidden behind HTML forms, has long been acknowledged as a significant gap in search engine coverage. Since it represents a large portion of the structured data on the Web, accessing Deep-Web content has been a long-standing challenge for the database community. This paper describes a system for surfacing Deep-Web content, i.e., pre-computing submissions for each HTML form and adding the resulting HTML pages into a search engine index. The results of our surfacing have been incorporated into the Google search engine and today drive more than a thousand queries per second to Deep-Web content.

Surfacing the Deep Web poses several challenges. First, our goal is to index the content behind many millions of HTML forms that span many languages and hundreds of domains. This necessitates an approach that is completely automatic, highly scalable, and very efficient. Second, a large number of forms have text inputs and require valid inputs values to be submitted. We present an algorithm for selecting input values for text search inputs that accept keywords and an algorithm for identifying inputs which accept only values of a specific type. Third, HTML forms often have more than one input and hence a naive strategy of enumerating the entire Cartesian product of all possible inputs can result in a very large number of URLs being generated. We present an algorithm that efficiently navigates the search space of possible input combinations to identify only those that generate URLs suitable for inclusion into our web search index. We present an extensive experimental evaluation validating the effectiveness of our algorithms.

REFERENCES

• 1: L. Barbosa and J. Freire. Siphoning hidden-web data through keyword-based interfaces. In SBBD, 2004.
• 2: M. K. Bergman. The Deep Web: Surfacing Hidden Value. Journal of Electronic Publishing, 2001.
• 3: S. Byers, J. Freire, and C. T. Silva. Efficient acquisition of web data through restricted query interfaces. In WWW Posters, 2001.
• 4: 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]
• 5: Cars.com FAQ. http://siy.cars.com/siy/qsg/faqGeneralInfo.jsp#howmanyads.
• 6: A. Doan, P. Domingos, and A. Y. Halevy. Reconciling Schemas of Disparate Data Sources: A Machine-Learning Approach. In SIGMOD, 2001.
• 7: Luis Gravano , Panagiotis G. Ipeirotis , Mehran Sahami, QProber: A system for automatic classification of hidden-Web databases, ACM Transactions on Information Systems (TOIS), v.21 n.1, p.1-41, January 2003 [doi>10.1145/635484.635485]
• 8: Bin He , Kevin Chen-Chuan Chang, Automatic complex schema matching across Web query interfaces: A correlation mining approach, ACM Transactions on Database Systems (TODS), v.31 n.1, p.346-395, March 2006 [doi>10.1145/1132863.1132872]
• 9: 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]
• 10: 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
• 11: 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]
• 12: 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.
• 13: Alexandros Ntoulas , Petros Zerfos , Junghoo Cho, Downloading textual hidden web content through keyword queries, Proceedings of the 5th ACM/IEEE-CS joint conference on Digital libraries, June 07-11, 2005, Denver, CO, USA [doi>10.1145/1065385.1065407]
• 14: Sriram Raghavan , Hector Garcia-Molina, Crawling the Hidden Web, Proceedings of the 27th International Conference on Very Large Data Bases, p.129-138, September 11-14, 2001
• 15: Anand Rajaraman , Yehoshua Sagiv , Jeffrey D. Ullman, Answering queries using templates with binding patterns (extended abstract), Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.105-112, May 22-25, 1995, San Jose, California, United States [doi>10.1145/212433.220199]
• 16: Gerard Salton , Michael J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, 1986
• 17: Jiying Wang , Ji-Rong Wen , Fred Lochovsky , Wei-Ying Ma, Instance-based schema matching for web databases by domain-specific query probing, Proceedings of the Thirtieth international conference on Very large data bases, p.408-419, August 31-September 03, 2004, Toronto, Canada
• 18: Ping Wu , Ji-Rong Wen , Huan Liu , Wei-Ying Ma, Query Selection Techniques for Efficient Crawling of Structured Web Sources, Proceedings of the 22nd International Conference on Data Engineering, p.47, April 03-07, 2006 [doi>10.1109/ICDE.2006.124]
• 19: 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.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
      H.3.4 Systems and Software
          Subjects: Performance evaluation (efficiency and effectiveness)

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.4 Applications
          Subjects: Text processing

General Terms:
Algorithms, Management, Performance