Synonyms
Definition
Subset scanning is an accurate and computationally efficient framework for detecting events and other patterns in both spatial and nonspatial datasets, through constrained optimization of a score function (e.g., a likelihood ratio statistic) over subsets of the data. Many score functions of interest satisfy the linear-time subset scanning property (Neill 2012), enabling exact and efficient optimization over subsets. This efficient unconstrained optimization step, the fast subset scan, can be used as a building block for scalable solutions to event and pattern detection problems incorporating a variety of real-world constraints.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
References
Chen F, Neill DB (2014) Non-parametric scan statistics for event detection and forecasting in heterogeneous social media graphs. In: Proceedings of the 20th ACM SIGKDD conference on knowledge discovery and data mining, New York, pp 1166–1175
Costa MA, Assuncao RM, Kulldorff M (2012) Constrained spanning tree algorithms for irregularly-shaped spatial clustering. Comput Stat Data Anal 56(6):1771–1783
Das K, Schneider J, Neill DB (2008) Anomaly pattern detection in categorical datasets. In: Proceedings of the 14th ACM SIGKDD conference on knowledge discovery and data mining, Las Vegas, pp 169–176
Duczmal L, Assuncao R (2004) A simulated annealing strategy for the detection of arbitrary shaped spatial clusters. Comput Stat Data Anal 45:269–286
Duczmal L, Cancado A, Takahashi R, Bessegato L (2007) A genetic algorithmic for irregularly shaped scan statistics. Comput Stat Data Anal 52(1):43–52
Kulldorff M (1997) A spatial scan statistic. Commun Stat Theory Methods 26(6):1481–1496
Kulldorff M (2001) Prospective time-periodic geographical disease surveillance using a scan statistic. J R Stat Soc A 164:61–72
Kulldorff M, Huang L, Pickle L, Ducmzal L (2006) An elliptic spatial scan statistic. Stat Med 25:3929–3943
Kulldorff M, Mostashari F, Duczmal L, Yih WK, Kleinman K, Platt R (2007) Multivariate scan statistics for disease surveillance. Stat Med 26:1824–1833
Leskovec J, Krause A, Guestrin C, Faloutsos C, VanBriesen J, Glance N (2007) Cost-effective outbreak detection in networks. In: Proceedings of the 13th ACM SIGKDD conference on knowledge discovery and data mining, San Jose, pp 420–429
McFowland III E, Speakman S, Neill DB (2013) Fast generalized subset scan for anomalous pattern detection. J Mach Learn Res 14:1533–1561
Naus JI (1965) The distribution of the size of the maximum cluster of points on the line. J Am Stat Assoc 60:532–538
Neill DB (2009a) An empirical comparison of spatial scan statistics for outbreak detection. Int J Health Geogr 8:20
Neill DB (2009b) Expectation-based scan statistics for monitoring spatial time series data. Int J Forecast 25:498–517
Neill DB (2012) Fast subset scan for spatial pattern detection. J R Stat Soc Ser B Stat Methodol 74(2):337–360
Neill DB, Kumar T (2013) Fast multidimensional subset scan for outbreak detection and characterization. Online J Publ Health Inf 5(1):156
Neill DB, Moore AW (2004) Rapid detection of significant spatial clusters. In: Proceedings of the 10th ACM SIGKDD conference on knowledge discovery and data mining, Seattle, pp 256–265
Neill DB, Moore AW, Sabhnani M, Daniel K (2005) Detection of emerging space-time clusters. In: Proceedings of the 11th ACM SIGKDD conference on knowledge discovery and data mining, Chicago, pp 218–227
Neill DB, McFowland III E, Zheng H (2013) Fast subset scan for multivariate event detection. Stat Med 32:2185–2208
Nobles M, Deyneka L, Ising A, Neill DB (2015) Identifying emerging novel outbreaks in textual emergency department data. Online J Publ Health Inf 7(1): e45
Patil GP, Taillie C (2004) Upper level set scan statistic for detecting arbitrarily shaped hotspots. Environ Ecol Stat 11:183–197
Somanchi S, Neill DB (2013) Discovering anomalous patterns in large digital pathology images. In: Proceedings of the 8th INFORMS workshop on data mining and health informatics, Minneapolis
Speakman S, Zhang Y, Neill DB (2013) Dynamic pattern detection with temporal consistency and connectivity constraints. In: Proceedings of the 13th IEEE international conference on data mining, Dallas, pp 697–706
Speakman S, McFowland III E, Neill DB (2015) Scalable detection of anomalous patterns with connectivity constraints. J Comput Graph Stat 24(4):1014–1033
Speakman S, Somanchi S, McFowland III E, Neill DB (2016, in press) Penalized fast subset scanning. J Comput Graph Stat
Tango T, Takahashi K (2005) A flexibly shaped spatial scan statistic for detecting clusters. Int J Health Geogr 4:11
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this entry
Cite this entry
Neill, D.B. (2017). Subset Scanning for Event and Pattern Detection. In: Shekhar, S., Xiong, H., Zhou, X. (eds) Encyclopedia of GIS. Springer, Cham. https://doi.org/10.1007/978-3-319-17885-1_1547
Download citation
DOI: https://doi.org/10.1007/978-3-319-17885-1_1547
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-17884-4
Online ISBN: 978-3-319-17885-1
eBook Packages: Computer ScienceReference Module Computer Science and Engineering