document: Rapid detection of significant spatial clusters Given an N x N grid of squares , where each square has a count cij and an underlying population pij , our goal is to find the rectangular region with the highest density , and to calculate its significance by randomization . An arbitrary density function D , dependent on a region 's total count C and total population P , can be used . For example , if each count represents the number of disease cases occurring in that square , we can use Kulldorff 's spatial scan statistic DK to find the most significant spatial disease cluster . A naive approach to finding the maximum density region requires O ( N4 ) time , and is generally computationally infeasible . We present a multiresolution algorithm which partitions the grid into overlapping regions using a novel overlap-kd tree data structure , bounds the maximum score of subregions contained in each region , and prunes regions which can not contain the maximum density region . For sufficiently dense regions , this method finds the maximum density region in O ( ( N log N ) 2 ) time , in practice resulting in significant ( 20-2000x ) speedups on both real and simulated datasets .
doc_bio_tags: O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O