Homepage live: automatic block tracing for web personalization

ABSTRACT

The emergence of personalized homepage services, e.g. personalized Google Homepage and Microsoft Windows Live, has enabled Web users to select Web contents of interest and to aggregate them in a single Web page. The web contents are often predefined content blocks provided by the service providers. However, it involves intensive manual efforts to define the content blocks and maintain the information in it. In this paper, we propose a novel personalized homepage system, called .Homepage Live., to allow end users to use drag-and-drop actions to collect their favorite Web content blocks from existing Web pages and organize them in a single page. Moreover, Homepage Live automatically traces the changes of blocks with the evolvement of the container pages by measuring the tree edit distance of the selected blocks. By exploiting the immutable elements of Web pages, the tracing algorithm performance is significantly improved. The experimental results demonstrate the effectiveness and efficiency of our algorithm.

REFERENCES

• 1: Ackerman, M., Starr, B. and Pazzani, M., The Do-I-Care Agent: Effective Social Discovery and Filtering on the Web. In Proceedings of RIAO'97, 17--31.
• 2: Corin R. Anderson , Eric Horvitz, Web montage: a dynamic personalized start page, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511537]
• 3: 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]
• 4: Deng Cai , Shipeng Yu , Ji-Rong Wen , Wei-Ying Ma, Block-based web search, Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, July 25-29, 2004, Sheffield, United Kingdom [doi>10.1145/1008992.1009070]
• 5: Cai, D., Yu, S.P., Wen, J.R. and Ma, W.Y.. VIPS: a vision-based page segmentation algorithm. Microsoft Technical Report, MSR-TR-2003-79, 2003.
• 6: Chen, Y.F., Douglis, F., Huan, H. and Vo, K.P., TopBlend: An Efficient Implementation of HtmlDiff in Java. In Proceedings of the WebNet 2000 Conference, San Antonio, TX, Nov. 2000.
• 7: Jinlin Chen , Baoyao Zhou , Jin Shi , Hongjiang Zhang , Qiu Fengwu, Function-based object model towards website adaptation, Proceedings of the 10th international conference on World Wide Web, p.587-596, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372161]
• 8: Hasan Davulcu , Guizhen Yang , Michael Kifer , I. V. Ramakrishnan, Computational aspects of resilient data extraction from semistructured sources (extended abstract), Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.136-144, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335216]
• 9: Fred Douglis , Thomas Ball , Yih-farn Chen , Eleftherios Koutsofios, The AT&T Internet Difference Engine: Tracking and viewing changes on the web, World Wide Web, v.1 n.1, p.27-44, 1998 [doi>10.1023/A:1019243126596]
• 10: Susan Dumais , Edward Cutrell , JJ Cadiz , Gavin Jancke , Raman Sarin , Daniel C. Robbins, Stuff I've seen: a system for personal information retrieval and re-use, 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.860451]
• 11: Fishkin, K. and Bier, E., WebTracker -- a Web Service for tracking documents. In Proceedings of 6th International World Wide Web Conference (WWW 1997), 2004.
• 12: Juliana Freire , Bharat Kumar , Daniel Lieuwen, WebViews: accessing personalized web content and services, Proceedings of the 10th international conference on World Wide Web, p.576-586, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372160]
• 13: Milos Kovacevic , Michelangelo Diligenti , Marco Gori , Veljko Milutinovic, Recognition of Common Areas in a Web Page Using Visual Information: a possible application in a page classification, Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM'02), p.250, December 09-12, 2002
• 14: Shian-Hua Lin , Jan-Ming Ho, Discovering informative content blocks from Web documents, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775134]
• 15: 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]
• 16: Lakshmish Ramaswamy , Arun Iyengar , Ling Liu , Fred Douglis, Automatic detection of fragments in dynamically generated web pages, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988732]
• 17: 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]
• 18: Atsushi Sugiura , Yoshiyuki Koseki, Internet scrapbook: automating Web browsing tasks by demonstration, Proceedings of the 11th annual ACM symposium on User interface software and technology, p.9-18, November 01-04, 1998, San Francisco, California, United States [doi>10.1145/288392.288395]
• 19: 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]
• 20: Shipeng Yu , Deng Cai , Ji-Rong Wen , Wei-Ying Ma, Improving pseudo-relevance feedback in web information retrieval using web page segmentation, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775155]
• 21: Yanhong Zhai , Bing Liu, Web data extraction based on partial tree alignment, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060761]
• 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.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.4 Hypertext/Hypermedia
          Subjects: Navigation

Additional Classification:
  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.2 User/Machine Systems
          Subjects: Human factors; Human information processing
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.4 Hypertext/Hypermedia
          Subjects: User issues

General Terms:
Algorithms, Experimentation, Human Factors

Keywords:
adaptive user interfaces, tracing, tree edit distance, tree pruning, web blocks