Thread detection in dynamic text message streams

ABSTRACT

Text message stream is a newly emerging type of Web data which is produced in enormous quantities with the popularity of Instant Messaging and Internet Relay Chat. It is beneficial for detecting the threads contained in the text stream for various applications, including information retrieval, expert recognition and even crime prevention. Despite its importance, not much research has been conducted so far on this problem due to the characteristics of the data in which the messages are usually very short and incomplete. In this paper, we present a stringent definition of the thread detection task and our preliminary solution to it. We propose three variations of a single-pass clustering algorithm for exploiting the temporal information in the streams. An algorithm based on linguistic features is also put forward to exploit the discourse structure information. We conducted several experiments to compare our approaches with some existing algorithms on a real dataset. The results show that all three variations of the single-pass algorithm outperform the basic single-pass algorithm. Our proposed algorithm based on linguistic features improves the performance relatively by 69.5% and 9.7% when compared with the basic single-pass algorithm and the best variation algorithm in terms of F1 respectively.

REFERENCES

• 1: J. Allan, J. Carbonell, G. Doddington, J. Yamron, and Y. Yang. Topic detection and tracking pilot study. In Proceedings of DARPA Broadcast News Transcription and Understanding Workshop, pages 194--218, 1998.
• 2: J. Bengel, S. Gauch, E. Mittur, and R. Vijayaraghavan. Chattrack: Chat room topic detection using classification. In 2nd Symposium on Intelligence and Security Informatics (ISI-2004)., page 266-277, Tucson, Arizona., June 2004.
• 3: Ella Bingham , Ata Kabán , Mark Girolami, Topic Identification in Dynamical Text by Complexity Pursuit, Neural Processing Letters, v.17 n.1, p.69-83, 2003 [doi>10.1023/A:1022990829563]
• 4: E. Elnahrawy. Log-based chat room monitoring using text categorization: A comparative study. In St.Thomas, editor, Proceedings of the IASTED International Conference on Information and Knowledge Sharing (IKS 2002), US Virgin Islands, USA, November 2002.
• 5: Vasileios Hatzivassiloglou , Luis Gravano , Ankineedu Maganti, An investigation of linguistic features and clustering algorithms for topical document clustering, Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.224-231, July 24-28, 2000, Athens, Greece [doi>10.1145/345508.345582]
• 6: http://www3.gartner.com/3_consulting_services/marketplace/instMessaging.jsp
• 7: Xiang Ji , Hongyuan Zha, Domain-independent text segmentation using anisotropic diffusion and dynamic programming, 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.860494]
• 8: Ata Kabán , Mark A. Girolami, A Dynamic Probabilistic Model to Visualise Topic Evolution in Text Streams, Journal of Intelligent Information Systems, v.18 n.2-3, p.107-125, March-May 2002 [doi>10.1023/A:1013673310093]
• 9: F. M. Khan, T. A. Fisher, L. Shuler, T. Wu, and W. M. Pottenger. Mining chatroom conversations for social and semantic interactions. Technical Report LU-CSE-02-011, Lehigh University, 2002.
• 10: Jong Wook Kim , K. Selçuk Candan , Mehmet E. Dönderler, Topic segmentation of message hierarchies for indexing and navigation support, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060795]
• 11: Giridhar Kumaran , James Allan, Text classification and named entities for new event detection, 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.1009044]
• 12: Gerard Salton, Automatic text processing: the transformation, analysis, and retrieval of information by computer, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 13: G. Salton , M. Smith, On the application of syntactic methodologies in automatic text analysis, Proceedings of the 12th annual international ACM SIGIR conference on Research and development in information retrieval, p.137-150, June 25-28, 1989, Cambridge, Massachusetts, United States
• 14: Alan F. Smeaton, Progress in the application of natural language processing to information retrieval tasks, The Computer Journal, v.35 n.3, p.268-278, June 1992 [doi>10.1093/comjnl/35.3.268]
• 15: K. G. Steinbach, M. and V. Kumar. A comparison of document clustering techniques. Technical report 00-034, Department of Computer Science and Engineering, University of Minnesota, 2000.
• 16: Ville H. Tuulos , Henry Tirri, Combining Topic Models and Social Networks for Chat Data Mining, Proceedings of the Web Intelligence, IEEE/WIC/ACM International Conference on (WI'04), p.206-213, September 20-24, 2004 [doi>10.1109/WI.2004.44]
• 17: R. C. van. Information Retrieval. Butterworths, London, second edition edition, 1979.
• 18: A. Waibel, M. Bett, M. Finke, and R. Stiefelhagen. Meeting brower: Tracking and summarizing meetings. In Proceedings of the DARPA Broadcast News Transcription and Understanding Workshop, 1998.
• 19: 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]
• 20: Yiming Yang , Tom Pierce , Jaime Carbonell, A study of retrospective and on-line event detection, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.28-36, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290953]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.m Miscellaneous

Additional Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.4 Applications
          Subjects: Text processing

General Terms:
Algorithms, Experimentation

Keywords:
linguistic features, single-pass clustering, text stream, thread detection