ODE: Ontology-assisted data extraction

ABSTRACT

Online databases respond to a user query with result records encoded in HTML files. Data extraction, which is important for many applications, extracts the records from the HTML files automatically. We present a novel data extraction method, ODE (Ontology-assisted Data Extraction), which automatically extracts the query result records from the HTML pages. ODE first constructs an ontology for a domain according to information matching between the query interfaces and query result pages from different Web sites within the same domain. Then, the constructed domain ontology is used during data extraction to identify the query result section in a query result page and to align and label the data values in the extracted records. The ontology-assisted data extraction method is fully automatic and overcomes many of the deficiencies of current automatic data extraction methods. Experimental results show that ODE is extremely accurate for identifying the query result section in an HTML page, segmenting the query result section into query result records, and aligning and labeling the data values in the query result records.

REFERENCES

• 1: Arvind Arasu , Hector Garcia-Molina, 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]
• 2: R. A. Baeza-Yates, Algorithms for string searching, ACM SIGIR Forum, v.23 n.3-4, p.34-58, Spring 1989 [doi>10.1145/74697.74700]
• 3: Adam L. Berger , Vincent J. Della Pietra , Stephen A. Della Pietra, A maximum entropy approach to natural language processing, Computational Linguistics, v.22 n.1, p.39-71, March 1996
• 4: Bergman, M. K. 2001. The deep Web: Surfacing hidden value. White paper, BrightPlanet Corporation. http://www.brightplanet.com/resources/details/deepweb.html.
• 5: Alexander Bilke , Felix Naumann, Schema Matching Using Duplicates, Proceedings of the 21st International Conference on Data Engineering, p.69-80, April 05-08, 2005 [doi>10.1109/ICDE.2005.126]
• 6: Andrew Eliot Borthwick , Ralph Grishman, A maximum entropy approach to named entity recognition, New York University, New York, NY, 1999
• 7: 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
• 8: 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]
• 9: Kevin Chen-Chuan Chang , Bin He , Chengkai Li , Mitesh Patel , Zhen Zhang, Structured databases on the web: observations and implications, ACM SIGMOD Record, v.33 n.3, September 2004 [doi>10.1145/1031570.1031584]
• 10: Liangyou Chen , Hasan M. Jamil , Nan Wang, Automatic composite wrapper generation for semi-structured biological data based on table structure identification, ACM SIGMOD Record, v.33 n.2, June 2004 [doi>10.1145/1024694.1024704]
• 11: William W. Cohen , Matthew Hurst , Lee S. Jensen, A flexible learning system for wrapping tables and lists in HTML documents, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511477]
• 12: 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
• 13: D. W. Embley , D. M. Campbell , Y. S. Jiang , S. W. Liddle , D. W. Lonsdale , Y.—K. Ng , R. D. Smith, Conceptual-model-based data extraction from multiple-record Web pages, Data & Knowledge Engineering, v.31 n.3, p.227-251, Nov. 1999 [doi>10.1016/S0169-023X(99)00027-0]
• 14: Ariel Felner , Sarit Kraus , Richard E. Korf, KBFS: K-Best-First Search, Annals of Mathematics and Artificial Intelligence, v.39 n.1-2, p.19-39, September 2003 [doi>10.1023/A:1024452529781]
• 15: 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]
• 16: Dan Gusfield, Algorithms on strings, trees, and sequences: computer science and computational biology, Cambridge University Press, New York, NY, 1997
• 17: 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]
• 18: 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
• 19: Nicholas Kushmerick, Wrapper induction: efficiency and expressiveness, Artificial Intelligence, v.118 n.1-2, p.15-68, April 2000 [doi>10.1016/S0004-3702(99)00100-9]
• 20: Kristina Lerman , Lise Getoor , Steven Minton , Craig Knoblock, Using the structure of Web sites for automatic segmentation of tables, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007584]
• 21: 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]
• 22: Lu, Y., He, H., Zhao, H., Meng, W., and Yu, C. 2007. Annotating structured data of the deep Web. In Proceedings of the 23rd IEEE International Conference on Data Engineering. 376--385.
• 23: Minka, T. 2003. A comparison of numerical optimizers for logistic regression. Tech. rep., Department of Statistics, Carnegie Mellon University.
• 24: 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]
• 25: Ratnaparkhi, A. 1996. A maximum entropy model for part-of-speech tagging. In Proceedings of the 1st Empirical Methods in Natural Language Processing Conference. 133--141.
• 26: Roitman, H. and Gal, A. 2006. Ontobuilder: Fully automatic extraction and consolidation of ontologies from Web sources using sequence semantics. In Proceedings of the EDBT Workshops. 573--576.
• 27: 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]
• 28: Snoussi, H., Magnin, L., and Nie, J.-Y. 2001. Heterogeneous Web data extraction using ontologies. In Proceedings of the Conference on Agent-Oriented Information Systems. 99--110.
• 29: Su, W., Wang, J., and Lochovsky, F. H. 2006. Holistic schema matching for Web query interfaces. In Proceedings of the 10th International Conference on Extending Database Technology. 77--94.
• 30: Su, W., Wang, J., Lochovsky, F. H., and Liu, Y. 2009. PADE: Pair-wise alignment-based data extraction. Tech. rep. HKUST-CS09-01, Department of Computer Science and Engineering, The Hong Kong University of Science and Technology, Hong Kong.
• 31: Cui Tao , David W. Embley, Automatic hidden-web table interpretation, conceptualization, and semantic annotation, Data & Knowledge Engineering, v.68 n.7, p.683-703, July, 2009 [doi>10.1016/j.datak.2009.02.010]
• 32: Tao, C. and Embley, D. W. 2007. Automatic hidden-Web table interpretation by sibling page comparison. In Conceptual Modeling -- ER'07. Lecture Notes in Computer Science, vol. 4801 Springer Berlin, 566--581.
• 33: Yuri A. Tijerino , David W. Embley , Deryle W. Lonsdale , Yihong Ding , George Nagy, Towards Ontology Generation from Tables, World Wide Web, v.8 n.3, p.261-285, September 2005 [doi>10.1007/s11280-005-0360-8]
• 34: Vivan, O. M. and Heuser, C. A. 2002. Semiautomatic generation of data-extraction ontologies from relational databases. In Proceedings of the XVII Simpósio Brasileiro de Banco de Dados. 252--262.
• 35: 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]
• 36: 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
• 37: World Wide Web Consortium. 1999. HTML 4.01 specification. http://www.w3.org/TR/REC-html40/.
• 38: Wu, W., Doan, A., Yu, C., and Meng, W. 2005. Boot-strapping domain ontology for semantic Web services from source Web sites. In Proceedings of the 6th VLDB Workshop on Technologies for E-Services. 11--12.
• 39: Yanhong Zhai , Bing Liu, Structured Data Extraction from the Web Based on Partial Tree Alignment, IEEE Transactions on Knowledge and Data Engineering, v.18 n.12, p.1614-1628, December 2006 [doi>10.1109/TKDE.2006.197]
• 40: Tong Zhang , Frank J. Oles, Text Categorization Based on Regularized Linear Classification Methods, Information Retrieval, v.4 n.1, p.5-31, April 2001 [doi>10.1023/A:1011441423217]
• 41: 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]

INDEX TERMS

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

General Terms:
Algorithms, Experimentation, Performance

Keywords:
Domain ontology, data value alignment, label assignment