A fast and robust method for web page template detection and removal

ABSTRACT

The widespread use of templates on the Web is considered harmful for two main reasons. Not only do they compromise the relevance judgment of many web IR and web mining methods such as clustering and classification, but they also negatively impact the performance and resource usage of tools that process web pages. In this paper we present a new method that efficiently and accurately removes templates found in collections of web pages. Our method works in two steps. First, the costly process of template detection is performed over a small set of sample pages. Then, the derived template is removed from the remaining pages in the collection. This leads to substantial performance gains when compared to previous approaches that combine template detection and removal. We show, through an experimental evaluation, that our approach is effective for identifying terms occurring in templates - obtaining F-measure values around 0.9, and that it also boosts the accuracy of web page clustering and classification methods.

REFERENCES

• 1: Ziv Bar-Yossef , Sridhar Rajagopalan, Template detection via data mining and its applications, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511522]
• 2: Krishna Bharat , Andrei Broder , Jeffrey Dean , Monika R. Henzinger, A comparison of techniques to find mirrored hosts on the WWW, Journal of the American Society for Information Science, v.51 n.12, p.1114-1122, Oct. 2000 [doi>10.1002/1097-4571(2000)9999:9999<::AID-ASI1025>3.0.CO;2-0]
• 3: Soumen Chakrabarti , Byron Dom , Prabhakar Raghavan , Sridhar Rajagopalan , David Gibson , Jon Kleinberg, Automatic resource compilation by analyzing hyperlink structure and associated text, Computer Networks and ISDN Systems, v.30 n.1-7, p.65-74, April 1, 1998
• 4: Soumen Chakrabarti , Mukul Joshi , Vivek Tawde, Enhanced topic distillation using text, markup tags, and hyperlinks, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.208-216, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383990]
• 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: D. C. Reis , P. B. Golgher , A. S. Silva , A. F. Laender, Automatic web news extraction using tree edit distance, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988740]
• 8: Edleno S. de Moura , Célia F. dos Santos , Daniel R. Fernandes , Altigran S. Silva , Pavel Calado , Mario A. Nascimento, Improving Web search efficiency via a locality based static pruning method, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060783]
• 9: Sandip Debnath , Prasenjit Mitra , C. Lee Giles, Automatic extraction of informative blocks from webpages, Proceedings of the 2005 ACM symposium on Applied computing, March 13-17, 2005, Santa Fe, New Mexico [doi>10.1145/1066677.1067065]
• 10: David Gibson , Kunal Punera , Andrew Tomkins, The volume and evolution of web page templates, Special interest tracks and posters of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1062745.1062763]
• 11: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
• 12: Jakob Nielsen, User interface directions for the Web, Communications of the ACM, v.42 n.1, p.65-72, Jan. 1999 [doi>10.1145/291469.291470]
• 13: A. Nierman and H. V. Jagadish. Evaluating structural similarity in XML documents. In Proceedings of the International Workshop on the Web and Databases, June 2002.
• 14: S. M. Selkow. The tree-to-tree editing problem. Information Processing Letters, 6:184--186, 1977.
• 15: David Carmel , Doron Cohen , Ronald Fagin , Eitan Farchi , Michael Herscovici , Yoelle S. Maarek , Aya Soffer, Static index pruning for information retrieval systems, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.43-50, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383958]
• 16: Ruihua Song , Haifeng Liu , Ji-Rong Wen , Wei-Ying Ma, Learning block importance models for web pages, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988700]
• 17: 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]
• 18: G. Valiente. An efficient bottom-up distance between trees. In Proceedings of the International Symposium on String Processing and Information Retrieval, pages 212--219. IEEE Computer Science Press, 2001.
• 19: J. T. L. Wang and K. Zhang. Finding similar consensus between trees: an algorithm and a distance hierarchy. Pattern Recognition, 34:127--137, 2001.
• 20: 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]
• 21: Lan Yi , Bing Liu , Xiaoli Li, Eliminating noisy information in Web pages for data mining, 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.956785]
• 22: 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

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

General Terms:
Algorithms, Experimentation

Keywords:
web page noise removal, web template extraction