Twitter-scale New Event Detection via K-term Hashing

Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, pages 2584–2589, Lisbon, Portugal, 17-21 September 2015. c⃝2015 Association for Computational Linguistics. Twitter-scale New Event Detection via K-term Hashing 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 First Story Detection is hard because the most accurate systems become pro- gressively slower with each document processed. We present a novel ap- proach to FSD, which operates in constant time/space and scales to very high volume streams. We show that when computing novelty over a large dataset of tweets, our method performs 192 times faster than a state-of-the-art baseline without sacrific- ing accuracy. Our method is capable of performing FSD on the full Twitter stream on a single core of modest hardware. 1 Introduction First Story Detection (FSD), also called New Event Detection, is the task of identifying the very first document in a stream to mention a new event1. FSD was introduced as port of the TDT2 initiative and has direct applications in finance, news and government security. The most accurate approaches to FSD involve a runtime of O(n2) and cannot scale to unbounded high volume streams such as Twitter. We present a novel approach to FSD that operates in O(1) per tweet. Our method is able to process the load of the average Twit- ter Firehose3 stream on a single core of mod- est hardware while retaining effectiveness on par with one of the most accurate FSD systems. Dur- ing the TDT program, FSD was applied to news wire documents and solely focused on effective- ness, neglecting efficiency and scalability. The tra- ditional approach to FSD (Petrovic et al., 2010) computes the distance of each incoming document 1e.g. a natural disaster or a scandal 2TDT by NIST - 1998-2004. http://www.itl.nist.gov/ iad/mig/tests/tdt/resources.html (Last Update: 2008) 3 5,700 tweets per second https://about.twitter .com/company (last updated: March 31, 2015) to all previously seen documents and the mini- mum distance determines the novelty score. Doc- uments, whose minimum distance falls above a certain threshold are considered to talk about a new event and declared as first stories. Conse- quently, the computational effort increases with each document processed. 1.1 Related Work Researchers have proposed a range of approaches to scale FSD to large data streams. Sankara- narayanan et al. (2009) were one of the first to apply FSD to Twitter. They reduced the volume by classifying documents into news/non-news and only compared to tweets within a 3-day window. They did not perform a quantitative evaluation of their approach. Sakaki et al. (2010) and Li et al. (2012) applied keyword filtering in conjunc- tion with classification algorithms, which allowed them to efficiently detect certain events with high precision. These two approaches, although effi- cient and effective, require a user to explicitly de- fine a set of keywords or to provide a set of exam- ples that he wants to track. The approach cannot detect previously …

Content truncated to 500 words