Using the structure of Web sites for automatic segmentation of tables

ABSTRACT

Many Web sites, especially those that dynamically generate HTML pages to display the results of a user's query, present information in the form of list or tables. Current tools that allow applications to programmatically extract this information rely heavily on user input, often in the form of labeled extracted records. The sheer size and rate of growth of the Web make any solution that relies primarily on user input is infeasible in the long term. Fortunately, many Web sites contain much explicit and implicit structure, both in layout and content, that we can exploit for the purpose of information extraction. This paper describes an approach to automatic extraction and segmentation of records from Web tables. Automatic methods do not require any user input, but rely solely on the layout and content of the Web source. Our approach relies on the common structure of many Web sites, which present information as a list or a table, with a link in each entry leading to a detail page containing additional information about that item. We describe two algorithms that use redundancies in the content of table and detail pages to aid in information extraction. The first algorithm encodes additional information provided by detail pages as constraints and finds the segmentation by solving a constraint satisfaction problem. The second algorithm uses probabilistic inference to find the record segmentation. We show how each approach can exploit the web site structure in a general, domain-independent manner, and we demonstrate the effectiveness of each algorithm on a set of twelve Web sites.

REFERENCES

• 1: 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]
• 2: L. Arlotta, V. Crescenzi, G. Mecca, and P. Marialdo. Automatic annotation of data extracted from large web sites. In Proceedings of the Sixth International Workshop on Web and Databases (WebDB03), 2003.
• 3: Vinayak Borkar , Kaustubh Deshmukh , Sunita Sarawagi, Automatic segmentation of text into structured records, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.175-186, May 21-24, 2001, Santa Barbara, California, United States
• 4: 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]
• 5: 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]
• 6: 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]
• 7: Valter Crescenzi , Giansalvatore Mecca , Paolo Merialdo, Automatic Web Information Extraction in the ROADRUNNER System, Revised Papers from the HUMACS, DASWIS, ECOMO, and DAMA on ER 2001 Workshops, p.264-277, November 27-30, 2001
• 8: 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
• 9: C. Gazen. Thesis proposal, Carnegie Mellon University.
• 10: Z. Ghahramani and M. I. Jordan. Factorial hidden Markov models. In D. S. Touretzky, M. C. Mozer, and M. E. Hasselmo, editors, Proc. Conf. Advances in Neural Information Processing Systems, NIPS, volume 8, pages 472--478. MIT Press, 1995.
• 11: M. Hurst. Layout and language: Challenges for table understanding on the web. In In Web Document Analysis, Proceedings of the 1st International Workshop on Web Document Analysis, 2001.
• 12: Matthew Hurst , Shona Douglas, Layout and Language: Preliminary Investigations in Recognizing the Structure of Tables, Proceedings of the 4th International Conference on Document Analysis and Recognition, p.1043-1047, August 18-20, 1997
• 13: Y. Jiang. Record-Boundary Discovery In Web Documents. PhD thesis, BYU, Utah, 1998.
• 14: N. Kushmerick and B. Thoma. Intelligent Information Agents R&D in Europe: An AgentLink perspective, chapter Adaptive information extraction: Core technologies for information agents. Springer, 2002.
• 15: John D. Lafferty , Andrew McCallum , Fernando C. N. Pereira, Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data, Proceedings of the Eighteenth International Conference on Machine Learning, p.282-289, June 28-July 01, 2001
• 16: K. Lerman and S. Minton. Learning the Common Structure of Data. In Proceedings of the 15th National Conference on Artificial Intelligence (AAAI-2000), Menlo Park, 2000. AAAI Press.
• 17: K. Lerman, C. A. Knoblock, and S. Minton. Automatic data extraction from lists and tables in web sources. In Proceedings of the workshop on Advances in Text Extraction and Mining (IJCAI-2001), Menlo Park, 2001. AAAI Press.
• 18: K. Lerman, S. Minton, and C. Knoblock. Wrapper maintenance: A machine learning approach. Journal of Artificial Intelligence Research, 18:149--181, 2003.
• 19: K. Lerman, C. Gazen, S. Minton, and C. A. Knoblock,. Populating the Semantic Web. Submitted to the workshop on Advances in Text Extraction and Mining (ATEM-2004), 2004.
• 20: Kevin Patrick Murphy , Stuart Russell, Dynamic bayesian networks: representation, inference and learning, 2002
• 21: Ion Muslea , Steven Minton , Craig A. Knoblock, Active + Semi-supervised Learning = Robust Multi-View Learning, Proceedings of the Nineteenth International Conference on Machine Learning, p.435-442, July 08-12, 2002
• 22: Hwee Tou Ng , Chung Yong Lim , Jessica Li Teng Koo, Learning to recognize tables in free text, Proceedings of the 37th annual meeting of the Association for Computational Linguistics on Computational Linguistics, p.443-450, June 20-26, 1999, College Park, Maryland [doi>10.3115/1034678.1034746]
• 23: David Pinto , Andrew McCallum , Xing Wei , W. Bruce Croft, Table extraction using conditional random fields, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada [doi>10.1145/860435.860479]
• 24: Pallavi Pyreddy , W. Bruce Croft, TINTIN: a system for retrieval in text tables, Proceedings of the second ACM international conference on Digital libraries, p.193-200, July 23-26, 1997, Philadelphia, Pennsylvania, United States [doi>10.1145/263690.263816]
• 25: Lawrence R. Rabiner, A tutorial on hidden Markov models and selected applications in speech recognition, Readings in speech recognition, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990
• 26: 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
• 27: J. P. Walser. Wsat(oip) package.
• 28: J. P. Walser. Integer Optimization by Local Search: A Domain Independent Approach, volume 1637 of LNCS. Springer, New York, 1999.
• 29: Yalin Wang , Jianying Hu, Detecting Tables in HTML Documents, Proceedings of the 5th International Workshop on Document Analysis Systems V, p.249-260, August 19-21, 2002
• 30: 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]
• 31: Yalin Wang , Ihsin T. Phillips , Robert M. Haralick, Table Detection via Probability Optimization, Proceedings of the 5th International Workshop on Document Analysis Systems V, p.272-282, August 19-21, 2002
• 32: M. Yoshida, K. Torisawa, and J. Tsujii. A method to integrate tables of the world wide web. In in Proceedings of the International Workshop on Web Document Analysis (WDA 2001), Seattle, U.S., September 2001.