Mining templates from search result records of search engines

ABSTRACT

Metasearch engine, Comparison-shopping and Deep Web crawling applications need to extract search result records enwrapped in result pages returned from search engines in response to user queries. The search result records from a given search engine are usually formatted based on a template. Precisely identifying this template can greatly help extract and annotate the data units within each record correctly. In this paper, we propose a graph model to represent record template and develop a domain independent statistical method to automatically mine the record template for any search engine using sample search result records. Our approach can identify both template tags (HTML tags) and template texts (non-tag texts), and it also explicitly addresses the mismatches between the tag structures and the data structures of search result records. Our experimental results indicate that this approach is very effective.

REFERENCES

• 1: Brad Adelberg, NoDoSE—a tool for semi-automatically extracting structured and semistructured data from text documents, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.283-294, June 01-04, 1998, Seattle, Washington, United States
• 2: Arvind Arasu , Hector Garcia-Molina , Stanford University, Extracting structured data from Web pages, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872799]
• 3: Robert Baumgartner , Sergio Flesca , Georg Gottlob, Visual Web Information Extraction with Lixto, Proceedings of the 27th International Conference on Very Large Data Bases, p.119-128, September 11-14, 2001
• 4: A Fully Automated Object Extraction System for the World Wide Web, Proceedings of the The 21st International Conference on Distributed Computing Systems, p.361, April 16-19, 2001
• 5: Chia-Hui Chang , Shao-Chen Lui, IEPAD: information extraction based on pattern discovery, Proceedings of the 10th international conference on World Wide Web, p.681-688, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372182]
• 6: Chia-Hui Chang , Mohammed Kayed , Moheb Ramzy Girgis , Khaled F. Shaalan, A Survey of Web Information Extraction Systems, IEEE Transactions on Knowledge and Data Engineering, v.18 n.10, p.1411-1428, October 2006 [doi>10.1109/TKDE.2006.152]
• 7: Valter Crescenzi , Giansalvatore Mecca , Paolo Merialdo, RoadRunner: Towards Automatic Data Extraction from Large Web Sites, Proceedings of the 27th International Conference on Very Large Data Bases, p.109-118, September 11-14, 2001
• 8: D. W. Embley , Y. Jiang , Y.-K. Ng, Record-boundary discovery in Web documents, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.467-478, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 9: Andrew Hogue , David Karger, Thresher: automating the unwrapping of semantic content from the World Wide Web, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060762]
• 10: Chun-Nan Hsu , Ming-Tzung Dung, Generating finite-state transducers for semi-structured data extraction from the Web, Information Systems, v.23 n.9, p.521-538, Dec. 1998
• 11: Utku Irmak , Torsten Suel, Interactive wrapper generation with minimal user effort, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135859]
• 12: N. Kushmerick, D. Weld, R. Doorenbos. Wrapper Induction for Information Extraction. Int'l Joint Conf. on AI, 1997.
• 13: Alberto H. F. Laender , Berthier A. Ribeiro-Neto , Altigran S. da Silva , Juliana S. Teixeira, A brief survey of web data extraction tools, ACM SIGMOD Record, v.31 n.2, June 2002 [doi>10.1145/565117.565137]
• 14: Bing Liu , Robert Grossman , Yanhong Zhai, Mining data records in Web pages, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956826]
• 15: B. Liu and Y. Zhai. NET - A System for Extracting Web Data from Flat and Nested Data Records. WISE Conference, 2005.
• 16: L. Liu, C. Pu and W. Han. XWRAP: An XML-Enabled Wrapper Construction System for Web Information Sources. IEEE ICDE, 2000.
• 17: Y. Lu, H. He, H. Zhao, W. Meng, C. Yu. Annotating Structured Data of the Deep Web. IEEE ICDE, 2007.
• 18: Weiyi Meng , Clement Yu , King-Lup Liu, Building efficient and effective metasearch engines, ACM Computing Surveys (CSUR), v.34 n.1, p.48-89, March 2002 [doi>10.1145/505282.505284]
• 19: Ion Muslea , Steve Minton , Craig Knoblock, A hierarchical approach to wrapper induction, Proceedings of the third annual conference on Autonomous Agents, p.190-197, April 1999, Seattle, Washington, United States [doi>10.1145/301136.301191]
• 20: 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
• 21: Kai Simon , Georg Lausen, ViPER: augmenting automatic information extraction with visual perceptions, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany [doi>10.1145/1099554.1099672]
• 22: Jiying Wang , Fred H. Lochovsky, Data extraction and label assignment for web databases, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775179]
• 23: Zonghuan Wu , Vijay Raghavan , Hua Qian , Vuyyuru Rama , Weiyi Meng , Hai He , Clement Yu, Towards Automatic Incorporation of Search Engines into a Large-Scale Metasearch Engine, Proceedings of the 2003 IEEE/WIC International Conference on Web Intelligence, p.658, October 13-17, 2003
• 24: Guizhen Yang , I. V. Ramakrishnan , Michael Kifer, On the complexity of schema inference from web pages in the presence of nullable data attributes, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA [doi>10.1145/956863.956907]
• 25: Yanhong Zhai , Bing Liu, Web data extraction based on partial tree alignment, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060761]
• 26: Y. Zhai, B. Liu. Extracting Web Data Using Instance-Based Learning. WISE Conference, 2005.
• 27: Hongkun Zhao , Weiyi Meng , Zonghuan Wu , Vijay Raghavan , Clement Yu, Fully automatic wrapper generation for search engines, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060760]
• 28: Jun Zhu , Zaiqing Nie , Ji-Rong Wen , Bo Zhang , Wei-Ying Ma, Simultaneous record detection and attribute labeling in web data extraction, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150457]
• 29: http://www.jooneworld.com/.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.5 On-line Information Services
          Subjects: Web-based services

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.5 On-line Information Services
          Subjects: Commercial services

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
information extraction, search engine, wrapper generation