document: Spatial scan statistics : approximations and performance study Spatial scan statistics are used to determine hotspots in spatial data , and are widely used in epidemiology and biosurveillance . In recent years , there has been much effort invested in designing efficient algorithms for finding such `` high discrepancy '' regions , with methods ranging from fast heuristics for special cases , to general grid-based methods , and to efficient approximation algorithms with provable guarantees on performance and quality . In this paper , we make a number of contributions to the computational study of spatial scan statistics . First , we describe a simple exact algorithm for finding the largest discrepancy region in a domain . Second , we propose a new approximation algorithm for a large class of discrepancy functions ( including the Kulldorff scan statistic ) that improves the approximation versus run time trade-off of prior methods . Third , we extend our simple exact and our approximation algorithms to data sets which lie naturally on a grid or are accumulated onto a grid . Fourth , we conduct a detailed experimental comparison of these methods with a number of known methods , demonstrating that our approximation algorithm has far superior performance in practice to prior methods , and exhibits a good performance-accuracy trade-off . All extant methods ( including those in this paper ) are suitable for data sets that are modestly sized ; if data sets are of the order of millions of data points , none of these methods scale well . For such massive data settings , it is natural to examine whether small-space streaming algorithms might yield accurate answers . Here , we provide some negative results , showing that any streaming algorithms that even provide approximately optimal answers to the discrepancy maximization problem must use space linear in the input .
doc_bio_tags: B I I O O O O O B I I 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 B 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 B I I O O O O O O O O O O O O O B O O O O O O O O O O O O O O O O O O B O O O O B I I 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 B O O O O O O O O O O