Loading...
Please wait, while we are loading the content...
Similar Documents
A Fast Multi-Resolution Method for Detection of Significant Spatial Overdensities (2003)
| Content Provider | CiteSeerX |
|---|---|
| Author | Neill, Daniel B. Moore, Andrew W. |
| Description | Given an N N grid of squares, where each square s ij has a count c ij and an underlying population p ij , our goal is to nd the square region S with the highest density, and to calculate the signi cance 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 ij represents the number of disease cases occurring in that square, we can use Kulldor's spatial scan statistic DK to nd the most signi cant spatial disease cluster. A naive approach to nding the region of maximum density would be to calculate the density measure for every square region: this requires O(RN ) calculations, where 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 suciently dense regions, this method nds the maximum density region in optimal O(RN ) time, and in practice it results in signi cant (10-200x) speedups as compared to the naive approach. |
| File Format | |
| Language | English |
| Publisher | MIT Press |
| Publisher Date | 2003-01-01 |
| Publisher Institution | Advances in Neural Information Processing Systems 16 |
| Access Restriction | Open |
| Subject Keyword | Monte Carlo Replication Total Population Square Ij Spatial Scan Statistic Dk Signi Cant Novel Multi-resolution Algorithm Significant Spatial Overdensities Square Region Monte Carlo Dense Region Fast Multi-resolution Method Disease Case Naive Approach Total Count Maximum Density Signi Cance Maximum Score Maximum Density Region Underlying Population Ij Prune Region Signi Cant Spatial Disease Cluster Density Measure Count Ij |
| Content Type | Text |
| Resource Type | Article |
