Tracking unbounded Topic Streams

Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing, pages 1765–1773, Beijing, China, July 26-31, 2015. c⃝2015 Association for Computational Linguistics Tracking unbounded Topic Streams Dominik Wurzer School of Informatics University of Edinburgh d.s.wurzer @sms.ed.ac.uk Victor Lavrenko School of Informatics University of Edinburgh vlavrenk @inf.ed.ac.uk Miles Osborne Bloomberg London mosborne29 @bloomberg.net Abstract Tracking topics on social media streams is non-trivial as the number of topics men- tioned grows without bound. This com- plexity is compounded when we want to track such topics against other fast mov- ing streams. We go beyond traditional small scale topic tracking and consider a stream of topics against another document stream. We introduce two tracking ap- proaches which are fully applicable to true streaming environments. When tracking 4.4 million topics against 52 million doc- uments in constant time and space, we demonstrate that counter to expectations, simple single-pass clustering can outper- form locality sensitive hashing for nearest neighbour search on streams. 1 Introduction The emergence of massive social media streams has sparked a growing need for systems able to process them. While previous research (Hassan et al., 2009; Becker et al., 2009; Petrovic et al., 2010; Cataldi et al., (2010); Weng et al., (2011); Petrovic 2013) has focused on detecting new topics in unbounded textual streams, less attention was paid to following (tracking) the steadily growing set of topics. Standard topic tracking (Allan, 2002) deals with helping human analysts follow and monitor ongoing events on massive data streams. By pairing topics with relevant documents, topic tracking splits a noisy stream of documents into sub-streams grouped by their target topics. This is a crucial task for financial and security analysts who are interested in pulling together relevant information from unstructured and noisy data streams. Other fields like summarization or topic modeling benefit from topic tracking as a mean to generate their data sources. In todays data streams however, new topics emerge on a continual basis and we are interested in following all instead of just a small fraction of newly detected topics. Since its introduction (Allan, 2002), standard topic tracking typically operates on a small scale and against a static set of predefined target topics. We go beyond such approaches and deal for the first time with massive, unbounded topic streams. Examples of unbounded topic streams include all events reported by news agencies each day across the world; popular examples of unbounded document streams include social media services such as Twitter. Tracking streams of topics allows re- search tasks like topic-modeling or summarization to be applied to millions of topics, a scale that is several orders of magnitude larger than those of current publications. We present two massive scale topic tracking systems capable of tracking unbounded topic streams. One is based on locality sensitive hashing (LSH) and the other on clus- tering. Since we operate on two unbounded data sources we are subject to the streaming model of computation (Muthukrishnan, 2005), which re- …

Content truncated to 500 words