Fast Multivariate Subset Scanning for Scalable Cluster Detection

• Activity Number: 281
• Type: Invited
• Date/Time: Tuesday, August 2, 2011 : 8:30 AM to 10:20 AM
• Sponsor: IMS
• Author(s): Daniel Bertrand Neill*+ and Edward McFowland III and Skyler Speakman
• Companies: Carnegie Mellon University and Carnegie Mellon University and Carnegie Mellon University
• Keywords: event detection ; spatial scan statistics ; linear-time subset scanning

Abstract

We present new, fast algorithms for multivariate event detection in massive space-time datasets. We first review the linear-time subset scanning (LTSS) property, which allows efficient optimization of a likelihood ratio scan statistic over all subsets of the data. This work extends the LTSS framework from univariate to multivariate data, enabling computationally efficient detection of irregularly shaped space-time clusters even when the numbers of spatial locations and monitored data streams are large. We demonstrate that two variants of the multivariate space-time scan statistic can each be efficiently optimized over proximity-constrained subsets of locations and over all subsets of the monitored data streams, enabling timely detection and accurate characterization of emerging events. Using our fast algorithms, we compare these two multivariate scan statistics on real-world disease surveillance tasks, demonstrating tradeoffs between detection and characterization performance. Finally, we discuss extensions of LTSS to other data types, including graph and tensor data. This work was partially supported by National Science Foundation grants IIS-0916345, IIS-0911032, and IIS-0953330.