Automatic web news extraction using tree edit distance

ABSTRACT

The Web poses itself as the largest data repository ever available in the history of humankind. Major efforts have been made in order to provide efficient access to relevant information within this huge repository of data. Although several techniques have been developed to the problem of Web data extraction, their use is still not spread, mostly because of the need for high human intervention and the low quality of the extraction results.In this paper, we present a domain-oriented approach to Web data extraction and discuss its application to automatically extracting news from Web sites. Our approach is based on a highly efficient tree structure analysis that produces very effective results. We have tested our approach with several important Brazilian on-line news sites and achieved very precise results, correctly extracting 87.71% of the news in a set of 4088 pages distributed among 35 different 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. Arllota, V. Crescenzi, G. Mecca, and P. Merialdo. Automatic annotation of data extraction from large Web sites. In Proceedings of the International Workshop on the Web and Databases, pages 7--12, San Diego, USA, 2003.
• 3: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 4: Vijay Boyapati , Kristie Chevrier , Avi Finkel , Natalie Glance , Tom Pierce , Robert Stockton , Chip Whitmer, ChangeDetector™: a site-level monitoring tool for the WWW, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511521]
• 5: Sudarshan S. Chawathe, Comparing Hierarchical Data in External Memory, Proceedings of the 25th International Conference on Very Large Data Bases, p.90-101, September 07-10, 1999
• 6: Weimin Chen, New algorithm for ordered tree-to-tree correction problem, Journal of Algorithms, v.40 n.2, p.135-158, August 2001 [doi>10.1006/jagm.2001.1170]
• 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: Valter Crescenzi , Giansalvatore Mecca , Paolo Merialdo, Wrapping-oriented classification of web pages, Proceedings of the 2002 ACM symposium on Applied computing, March 11-14, 2002, Madrid, Spain [doi>10.1145/508791.509009]
• 9: Daniela Florescu , Alon Levy , Alberto Mendelzon, Database techniques for the World-Wide Web: a survey, ACM SIGMOD Record, v.27 n.3, p.59-74, Sept. 1, 1998 [doi>10.1145/290593.290605]
• 10: Minos Garofalakis , Aristides Gionis , Rajeev Rastogi , S. Seshadri , Kyuseok Shim, XTRACT: a system for extracting document type descriptors from XML documents, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.165-176, May 15-18, 2000, Dallas, Texas, United States
• 11: Stéphane Grumbach , Giansalvatore Mecca, In Search of the Lost Schema, Proceeding of the 7th International Conference on Database Theory, p.314-331, January 10-12, 1999
• 12: Allan Heydon , Marc Najork, Mercator: A scalable, extensible Web crawler, World Wide Web, v.2 n.4, p.219-229, 1999 [doi>10.1023/A:1019213109274]
• 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: Jun-Ki Min , Jae-Yong Ahn , Chin-Wan Chung, Efficient extraction of schemas for XML documents, Information Processing Letters, v.85 n.1, p.7-12, 16 January 2003 [doi>10.1016/S0020-0190(02)00345-9]
• 16: A. Nierman and H. V. Jagadish. Evaluating structural similarity in XML documents. In Proceedings of the 5th International Workshop on the Web and Databases (WebDB 2002), Madison, Wisconsin, USA, June 2002.
• 17: S. M. Selkow. The tree-to-tree editing problem. Information Processing Letters, 6:184--186, Dec. 1977.
• 18: Kuo-Chung Tai, The Tree-to-Tree Correction Problem, Journal of the ACM (JACM), v.26 n.3, p.422-433, july 1979 [doi>10.1145/322139.322143]
• 19: G. Valiente. An efficient bottom-up distance between trees. In Proceedings of the 8th International Symposium on String Processing and Information Retrieval, pages 212--219, Santiago, Chile, 2001. IEEE Computer Science Press.
• 20: G. Valiente. Tree edit distance and common subtrees. Research Report LSI-02-20-R, Universitat Politecnica de Catalunya, Barcelona, Spain, 2002.
• 21: Jason T. L. Wang , Bruce A. Shapiro , Dennis Shasha , Kaizhong Zhang , Kathleen M. Currey, An Algorithm for Finding the Largest Approximately Common Substructures of Two Trees, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.20 n.8, p.889-895, August 1998 [doi>10.1109/34.709622]
• 22: J. T. L. Wang and K. Zhang. Finding similar consensus between trees: an algorithm and a distance hierarchy. Pattern Recognition, 34:127--137, 2001.
• 23: Peter Willett, Recent trends in hierarchic document clustering: a critical review, Information Processing and Management: an International Journal, v.24 n.5, p.577-597, 1988 [doi>10.1016/0306-4573(88)90027-1]
• 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: Wuu Yang, Identifying syntactic differences between two programs, Software—Practice & Experience, v.21 n.7, p.739-755, July 1991 [doi>10.1002/spe.4380210706]
• 26: Kaizhong Zhang , Dennis Shasha , Jason T. L. Wang, Approximate tree matching in the presence of variable length don't cares, Journal of Algorithms, v.16 n.1, p.33-66, Jan. 1994 [doi>10.1006/jagm.1994.1003]
• 27: Kaizhong Zhang , Rick Statman , Dennis Shasha, On the editing distance between unordered labeled trees, Information Processing Letters, v.42 n.3, p.133-139, May 25, 1992 [doi>10.1016/0020-0190(92)90136-J]

INDEX TERMS

General Terms:
Algorithms, Languages

Keywords:
data extraction, edit distance, schema inference, web