Robust web extraction: an approach based on a probabilistic tree-edit model

ABSTRACT

On script-generated web sites, many documents share common HTML tree structure, allowing wrappers to effectively extract information of interest. Of course, the scripts and thus the tree structure evolve over time, causing wrappers to break repeatedly, and resulting in a high cost of maintaining wrappers. In this paper, we explore a novel approach: we use temporal snapshots of web pages to develop a tree-edit model of HTML, and use this model to improve wrapper construction. We view the changes to the tree structure as suppositions of a series of edit operations: deleting nodes, inserting nodes and substituting labels of nodes. The tree structures evolve by choosing these edit operations stochastically.

Our model is attractive in that the probability that a source tree has evolved into a target tree can be estimated efficiently--in quadratic time in the size of the trees--making it a potentially useful tool for a variety of tree-evolution problems. We give an algorithm to learn the probabilistic model from training examples consisting of pairs of trees, and apply this algorithm to collections of web-page snapshots to derive HTML-specific tree edit models. Finally, we describe a novel wrapper-construction framework that takes the tree-edit model into account, and compare the quality of resulting wrappers to that of traditional wrappers on synthetic and real HTML document examples.

REFERENCES

• 1: Mari Abe , Masahiro Hori, Robust Pointing by XPath Language: Authoring Support and Empirical Evaluation, Proceedings of the 2003 Symposium on Applications and the Internet, p.156, January 27-31, 2003
• 2: Tobias Anton. Xpath-wrapper induction by generating tree traversal patterns. In LWA, pages 126--133, 2005.
• 3: Internet archive: http://www.archive.org/.
• 4: 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
• 5: Marc Bernard, Amaury Habrard, and Marc Sebban. Learning stochastic tree edit distance. In ECML, pages 42--53, 2006.
• 6: Philip Bille, A survey on tree edit distance and related problems, Theoretical Computer Science, v.337 n.1-3, p.217-239, 9 June 2005 [doi>10.1016/j.tcs.2004.12.030]
• 7: Laurent Boyer , Amaury Habrard , Marc Sebban, Learning Metrics Between Tree Structured Data: Application to Image Recognition, Proceedings of the 18th European conference on Machine Learning, September 17-21, 2007, Warsaw, Poland [doi>10.1007/978-3-540-74958-5_9]
• 8: Boris Chidlovskii , Bruno Roustant , Marc Brette, Documentum ECI self-repairing wrappers: performance analysis, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142555]
• 9: 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]
• 10: 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
• 11: Jonathan Graehl , Kevin Knight , Jonathan May, Training tree transducers, Computational Linguistics, v.34 n.3, p.391-427, September 2008 [doi>10.1162/coli.2008.07-051-R2-03-57]
• 12: Wei Han , David Buttler , Calton Pu, Wrapping web data into XML, ACM SIGMOD Record, v.30 n.3, September 2001 [doi>10.1145/603867.603873]
• 13: 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
• 14: Internet movie database: http://www.imdb.com/.
• 15: Kevin Knight and JonathaGraehl. An overview of probabilistic tree transducers for natural language processing. In Proceedings of the CICLing, 2005.
• 16: Marek Kowalkiewicz , Tomasz Kaczmarek , Witold Abramowicz, MyPortal: robust extraction and aggregation of web content, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 17: Marek Kowalkiewicz , Maria E. Orlowska , Tomasz Kaczmarek , Witold Abramowicz, Robust web content extraction, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135928]
• 18: Nickolas Kushmerick, Daniel S. Weld, and Robert B. Doorenbos. Wrapper induction for information extraction. In IJCAI, pages 729--737, 1997.
• 19: Kristina Lerman, Steven N. Minton, and Craig A. Knoblock. Wrapper maintenance: A machine learning approach. Journal of Artificial Intelligence Research, 18:2003, 2003.
• 20: A. McCallum, K. Bellare, and P. Pereira. A conditional random field for discriminatively-trained finite-state string edit distance. In UAI, 2005.
• 21: Robert McCann , Bedoor AlShebli , Quoc Le , Hoa Nguyen , Long Vu , AnHai Doan, Mapping maintenance for data integration systems, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 22: I. Muslea, S. Minton, and C. Knoblock. Stalker: Learning extraction rules for semistructured, 1998.
• 23: Jussi Myllymaki and Jared Jackson. Robust web data extraction with xml path expressions. Technical report, IBM Research Report RJ 10245, May 2002.
• 24: Andrew Ng and Michael Jordan. On discriminative vs. generative classifiers: A comparison of logistic regression and naive bayes. In Advances in Neural Information Processing Systems 2001 (NIPS 14), 2002.
• 25: Jorge Nocedal and Stephen J. Wright. Numerical Optimization. Springer, 1999.
• 26: Jose Oncina , Marc Sebban, Learning stochastic edit distance: Application in handwritten character recognition, Pattern Recognition, v.39 n.9, p.1575-1587, September, 2006 [doi>10.1016/j.patcog.2006.03.011]
• 27: J. S. Provan and M. O. Ball. The complexity of counting cuts and of computing the probability that a graph is connected. SIAM J. Comput., 12(4):777--788, 1983.
• 28: Eric Sven Ristad , Peter N. Yianilos, Learning String Edit Distance, Proceedings of the Fourteenth International Conference on Machine Learning, p.287-295, July 08-12, 1997
• 29: Arnaud Sahuguet , Fabien Azavant, Building Light-Weight Wrappers for Legacy Web Data-Sources Using W4F, Proceedings of the 25th International Conference on Very Large Data Bases, p.738-741, September 07-10, 1999
• 30: http://sourceforge.net/projects/jtidy.
• 31: L. Valiant. The complexity of enumeration and reliability problems. SIAM J. Comput., 8:410--421, 1979.
• 32: K. Zhang , D. Shasha, Simple fast algorithms for the editing distance between trees and related problems, SIAM Journal on Computing, v.18 n.6, p.1245-1262, Dec. 1989 [doi>10.1137/0218082]

INDEX TERMS

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

General Terms:
Algorithms

Keywords:
probabilistic tree-edit model, wrappers, xpath