Browsing on small screens: recasting web-page segmentation into an efficient machine learning framework

ABSTRACT

Fitting enough information from webpages to make browsing on small screens compelling is a challenging task. One approach is to present the user with a thumbnail image of the full web page and allow the user to simply press a single key to zoom into a region (which may then be transcoded into wml/xhtml, summarized, etc). However, if regions for zooming are presented naively, this yields a frustrating experience because of the number of coherent regions, sentences, images, and words that may be inadvertently separated. Here, we cast the web page segmentation problem into a machine learning framework, where we re-examine this task through the lens of entropy reduction and decision tree learning. This yields an efficient and effective page segmentation algorithm. We demonstrate how simple techniques from computer vision can be used to fine-tune the results. The resulting segmentation keeps coherent regions together when tested on a broad set of complex webpages.

REFERENCES

• 1: Milic-Frayling, N. and Sommerer, R. (2002) "SmartView: Enhanced Document Viewer for Mobile Devices.ö MSR-TR-2002-114 (2002).
• 2: Milic-Frayling, N. and Sommerer, R., Rodden, K., Blackwell, A. (2003) "SearchMobil: Web Viewing and Search for Mobile Devicesö Proc. WWW 2003.
• 3: Jacob O. Wobbrock , Jodi Forlizzi , Scott E. Hudson , Brad A. Myers, WebThumb: interaction techniques for small-screen browsers, Proceedings of the 15th annual ACM symposium on User interface software and technology, October 27-30, 2002, Paris, France [doi>10.1145/571985.572014]
• 4: G. W. Furnas, Generalized fisheye views, Proceedings of the SIGCHI conference on Human factors in computing systems, p.16-23, April 13-17, 1986, Boston, Massachusetts, United States
• 5: Hedman, A., Carr, D., & Nassla, H. (2004) "Browsing Thumbnails: A Comparison of Three Techniquesöö. Proc. 26th International Conference on Information Technology Interfaces.
• 6: Cai, D., Yu, S., Wen, J.R., Ma, W.Y. (2003), "VIPS: A vision-based segmentation algorithmö. MSR-TR-2003-70. Nov. 2003.
• 7: Xing Xie , Gengxin Miao , Ruihua Song , Ji-Rong Wen , Wei-Ying Ma, Efficient Browsing of Web Search Results on Mobile Devices Based on Block Importance Model, Proceedings of the Third IEEE International Conference on Pervasive Computing and Communications, p.17-26, March 08-12, 2005 [doi>10.1109/PERCOM.2005.16]
• 8: Berwick, B. (2003): Lecture Notes, MIT Class 6.034 AI, Recitation #9 "Nearest Neighbors + ID Treesö, Fall 2003 http://www.ai.mit.edu/courses/6.034b/recitation9.pdf
• 9: Moore, A. (2003): "Information Gainö, Lecture Notes. http://www.autonlab.org/tutorials/
• 10: Loper, E. (2003): "Decision Treesö, Lecture Notes, http://www.cis.upenn.edu/ edloper/slides/
• 11: Allison Woodruff , Andrew Faulring , Ruth Rosenholtz , Julie Morrsion , Peter Pirolli, Using thumbnails to search the Web, Proceedings of the SIGCHI conference on Human factors in computing systems, p.198-205, March 2001, Seattle, Washington, United States [doi>10.1145/365024.365098]
• 12: Heidi Lam , Patrick Baudisch, Summary thumbnails: readable overviews for small screen web browsers, Proceedings of the SIGCHI conference on Human factors in computing systems, April 02-07, 2005, Portland, Oregon, USA [doi>10.1145/1054972.1055066]
• 13: Staffan Björk , Lars Erik Holmquist , Johan Redström , Ivan Bretan , Rolf Danielsson , Jussi Karlgren , Kristofer Franzén, WEST: a Web browser for small terminals, Proceedings of the 12th annual ACM symposium on User interface software and technology, p.187-196, November 07-10, 1999, Asheville, North Carolina, United States [doi>10.1145/320719.322601]
• 14: Orkut Buyukkokten , Hector Garcia-Molina , Andreas Paepcke , Terry Winograd, Power browser: efficient Web browsing for PDAs, Proceedings of the SIGCHI conference on Human factors in computing systems, p.430-437, April 01-06, 2000, The Hague, The Netherlands [doi>10.1145/332040.332470]
• 15: Patrick Baudisch , Bongshin Lee , Libby Hanna, Fishnet, a fisheye web browser with search term popouts: a comparative evaluation with overview and linear view, Proceedings of the working conference on Advanced visual interfaces, May 25-28, 2004, Gallipoli, Italy [doi>10.1145/989863.989883]
• 16: Yu Chen , Wei-Ying Ma , Hong-Jiang Zhang, Detecting web page structure for adaptive viewing on small form factor devices, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775184]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)

General Terms:
Algorithms, Design, Human Factors

Keywords:
browser, machine learning, mobile browsing, mobile devices, small screen, thumbnail browsing, web page segmentation