CMU-CS-03-154Computer Science Department School of Computer Science, Carnegie Mellon University
CMU-CS-03-154
Daniel B. Neill, Andrew W. Moore June 2003
CMU-CS-03-154.ps
Keywords: Algorithms, biosurveillance, cluster detection,
spatial scan statistic
count c and an underlying _{ij}population
p, our goal is to find the square region _{ij}S with
the highest density, and to calculate the significance of
this region by Monte Carlo testing. Any density measure D,
which depends on the total count and total population of the region, can
be used. For example, if each count c represents the
number of disease cases occurring in that square, we can use Kulldorff's
_{ij}spatial scan statistic D to find the most significant spatial
disease cluster. A naive approach to finding the region of maximum
density would be to calculate the density measure for every square region:
this requires _{K}O(RN calculations, where
^{3})R is the number of Monte Carlo replications, and hence is
generally computationally infeasible. We present a novel multi-resolution
algorithm which partitions the grid into overlapping regions, bounds the
maximum score of subregions contained in each region, and prunes
regions which cannot contain the maximum density region. For
sufficiently dense regions, this method finds the maximum density
region in optimal O(RN time, and in
practice it results in significant (10-200x) speedups as compared
to the naive approach.^{2})17 pages
| |

Return to:
SCS Technical Report Collection This page maintained by reports@cs.cmu.edu |