Topic segmentation of message hierarchies for indexing and navigation support

ABSTRACT

Message hierarchies in web discussion boards grow with new postings. Threads of messages evolve as new postings focus within or diverge from the original themes of the threads. Thus, just by investigating the subject headings or contents of earlier postings in a message thread, one may not be able to guess the contents of the later postings. The resulting navigation problem is further compounded for blind users who need the help of a screen reader program that can provide only a linear representation of the content. We see that, in order to overcome the navigation obstacle for blind as well as sighted users, it is essential to develop techniques that help identify how the content of a discussion board grows through generalizations and specializations of topics. This knowledge can be used in segmenting the content in coherent units and guiding the users through segments relevant to their navigational goals. Our experimental results showed that the segmentation algorithm described in this paper provides up to 80-85% success rate in labeling messages. The algorithm is being deployed in a software system to reduce the navigational load of blind students in accessing web-based electronic course materials; however, we note that the techniques are equally applicable for developing web indexing and summarization tools for users with sight.

REFERENCES

• 1: Blackboard. http://www.blackboard.com.
• 2: Movie message board. http://www.hundland.com/movieboard.mv.
• 3: James Allan , Courtney Wade , Alvaro Bolivar, Retrieval and novelty detection at the sentence level, 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.860493]
• 4: Krishna Bharat , Monika R. Henzinger, Improved algorithms for topic distillation in a hyperlinked environment, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.104-111, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290972]
• 5: Thorsten Brants , Francine Chen, A System for new event detection, 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.860495]
• 6: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Proceedings of the seventh international conference on World Wide Web 7, p.107-117, April 1998, Brisbane, Australia
• 7: Peter Brusilovsky, Adaptive Hypermedia, User Modeling and User-Adapted Interaction, v.11 n.1-2, p.87-110, 2001
• 8: Peter Brusilovsky, Efficient Techniques for Adaptive Hypermedia, Intelligent Hypertext: Advanced Techniques for the World Wide Web, p.12-30, January 1997
• 9: Peter Brusilovsky, Adaptive Hypermedia, User Modeling and User-Adapted Interaction, v.11 n.1-2, p.87-110, 2001
• 10: K. S. Candan, J. W. Kim, H. Liu, and R. Suvarna. Structure-based mining of hierarchical media data, meta-data, and ontologies. In 5th Workshop on Multimedia Data Mining in conjunction with the ACM Conference on Knowledge Discovery and Data Mining, Seattle, WA, August 2004.
• 11: K. Selçuk Candan , Wen-Syan Li, Using Random Walks for Mining Web Document Associations, Proceedings of the 4th Pacific-Asia Conference on Knowledge Discovery and Data Mining, Current Issues and New Applications, p.294-305, April 18-20, 2000
• 12: K. Selçuk Candan , Wen-Syan Li, Discovering Web Document Associations for Web Site Summarization, Proceedings of the Third International Conference on Data Warehousing and Knowledge Discovery, p.152-161, September 05-07, 2001
• 13: K. Selçuk Candan , Wen-Syan Li, Reasoning for web document associations and its applications in site map construction, Data & Knowledge Engineering, v.43 n.2, p.121-150, November 2002 [doi>10.1016/S0169-023X(02)00053-8 ]
• 14: M. Cannataro, A. Cuzzocrea, and A. Pugliese. A probabilistic approach to model adaptive hypermedia systems. In 1st International Conference on Web Dynamics (in conjunction with the 8th Int. Conference on Database Theory), pages 12--30, London, UK, January 2001.
• 15: C. Caracciolo, W. van Hage, and M. de Rijke. Towards topic driven access to full text documents. In European Digital Library Conferences, 2004.
• 16: T. Cavanaugh. The need for assistive technology in educational technology. Educational Technology Review, 10(1), 2002.
• 17: Soumen Chakrabarti , Byron Dom , Prabhakar Raghavan , Sridhar Rajagopalan , David Gibson , Jon Kleinberg, Automatic resource compilation by analyzing hyperlink structure and associated text, Proceedings of the seventh international conference on World Wide Web 7, p.65-74, April 1998, Brisbane, Australia
• 18: Shih-Fu Chang , William Chen , Horace J. Meng , Hari Sundaram , Di Zhong, VideoQ: an automated content based video search system using visual cues, Proceedings of the fifth ACM international conference on Multimedia, p.313-324, November 09-13, 1997, Seattle, Washington, United States [doi>10.1145/266180.266382]
• 19: Freddy Y. Y. Choi, Advances in domain independent linear text segmentation, Proceedings of the first conference on North American chapter of the Association for Computational Linguistics, p.26-33, April 29-May 04, 2000, Seattle, Washington
• 20: F. Choi. Linear text segmentation. In CLUK3, 2000.
• 21: Jeffrey Dean , Monika R. Henzinger, Finding related pages in the World Wide Web, Proceeding of the eighth international conference on World Wide Web, p.1467-1479, May 1999, Toronto, Canada
• 22: M. E. Donderler, K. S. Candan, S. Wu, L. Peng, and J. W. Kim. Adaptive electronic course content delivery for students who are blind. In Demonstration at ACM Conf. on Computers and Accessibility (ASSETS04), 2004.
• 23: M. E. Donderler, L. Peng, and K. S. Candan. Adaptive content delivery to assist blind students in accessing course materials. In 6th Annual Accessing Higher Ground Conference: Assistive Technology and Accessible Media in Higher Education, Boulder, CO, November 2003.
• 24: 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]
• 25: A. Hampapur, R. Jain, and T. E. Weymouth. Indexing in video databases. In SPIE/IS&T Proceedings on Storage and Retrieval in Image and Video Databases, volume 2420, pages 292--306, San Jose, CA, 1995.
• 26: Ivan Herman , Guy Melançon , M. Scott Marshall, Graph Visualization and Navigation in Information Visualization: A Survey, IEEE Transactions on Visualization and Computer Graphics, v.6 n.1, p.24-43, January 2000 [doi>10.1109/2945.841119 ]
• 27: L. A. R. J. S. Boreczky. Comparison of video shot boundary detection techniques. In SPIE/IS&T Intern. Symposium Electronic Imaging, volume 2664, pages 170--179, 1996.
• 28: T. Joachims, D. Freitag, and T. Mitchell. Webwatcher: A tour guide for the world wide web. In International Joint Conference on Artificial Intelligence, August 1999.
• 29: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Journal of the ACM (JACM), v.46 n.5, p.604-632, Sept. 1999 [doi>10.1145/324133.324140]
• 30: Wen-Syan Li , Necip Fazil Ayan , Okan Kolak , Quoc Vu , Hajime Takano , Hisashi Shimamura, Constructing multi-granular and topic-focused web site maps, Proceedings of the 10th international conference on World Wide Web, p.343-354, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372086]
• 31: Wen-Syan Li , K. Selçuk Candan , Quoc Vu , Divyakant Agrawal, Query Relaxation by Structure and Semantics for Retrieval of Logical Web Documents, IEEE Transactions on Knowledge and Data Engineering, v.14 n.4, p.768-791, July 2002 [doi>10.1109/TKDE.2002.1019213 ]
• 32: Wen-Syan Li , K. Selçuk Candan , Quoc Vu , Divyakant Agrawal, Retrieving and organizing web pages by “information unit”, Proceedings of the 10th international conference on World Wide Web, p.230-244, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372057]
• 33: H. Lieberman. Letizia: An agent that assists web browsing. In 14th Int. Joint Conf. on Artificial Intelligence, Montreal, Canada, 1995.
• 34: N. V. Patel and I. K. Sethi. Video shot detection and characterization for video databases. Pattern Recognition, 30:583--592, 1997.
• 35: Jeffrey C. Reynar , Mitchell P. Marcus, Topic segmentation: algorithms and applications, 1998
• 36: HongJiang Zhang , Atreyi Kankanhalli , Stephen W. Smoliar, Automatic partitioning of full-motion video, Multimedia Systems, v.1 n.1, p.10-28, June 1993 [doi>10.1007/BF01210504]
• 37: Yi Zhang , Jamie Callan , Thomas Minka, Novelty and redundancy detection in adaptive filtering, Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval, August 11-15, 2002, Tampere, Finland [doi>10.1145/564376.564393]
• 38: Wensi Xi , Jesper Lind , Eric Brill, Learning effective ranking functions for newsgroup 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.1009060]
• 39: A. Murakami and K. Nagao and K. Takeda. Discussion Mining: Knowledge Discovery from Online Discussion Records. The First NLP and XML Workshop, Tokyo, Japan, November 2001.
• 40: Jon Kleinberg, Bursty and hierarchical structure in streams, 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.775061]

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.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Abstracting methods; Indexing methods
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.1 Multimedia Information Systems
      H.5.4 Hypertext/Hypermedia
          Subjects: User issues

  K. Computing Milieux
  K.4 COMPUTERS AND SOCIETY
      K.4.2 Social Issues
          Subjects: Assistive technologies for persons with disabilities

General Terms:
Algorithms, Experimentation, Human Factors, Performance

Keywords:
assistive technology for blind users, discussion boards, navigational aid, segmentation