Fast and Flexible Outbreak Detection by Linear-Time Subset Scanning


The spatial scan statistic [1] detects significant spatial clusters of disease by maximizing a likelihood ratio statistic over a large set of spatial regions. Typical spatial scan approaches either constrain the search regions to a given shape, reducing power to detect patterns that do not correspond to this shape, or perform a heuristic search over a larger set of irregular regions, in which case they may not find the most relevant clusters. In either case, computation time is a serious issue when searching over complex region shapeso r when analyzing a large amount of data. Analternative approach might be to search over all possible subsets of the data to find the  most relevant pat-terns, but since there are exponentially many subsets, an exhaustive search is computationally infeasible.


We present a new method of "linear-time subset scanning" and apply this technique to various spatial outbreak detection scenarios, making it computationally feasible (and very fast) to perform spatial scans over huge numbers of search regions.

Primary Topic Areas: 
Original Publication Year: 
Event/Publication Date: 
October, 2007

July 30, 2018

Contact Us

NSSP Community of Practice



This website is supported by Cooperative Agreement # 6NU38OT000297-02-01 Strengthening Public Health Systems and Services through National Partnerships to Improve and Protect the Nation's Health between the Centers for Disease Control and Prevention (CDC) and the Council of State and Territorial Epidemiologists. Its contents are solely the responsibility of the authors and do not necessarily represent the official views of CDC. CDC is not responsible for Section 508 compliance (accessibility) on private websites.

Site created by Fusani Applications