Nothing Special   »   [go: up one dir, main page]

Skip to main content

Subset Scanning for Event and Pattern Detection

  • Reference work entry
  • First Online:
Encyclopedia of GIS
  • 100 Accesses

Synonyms

Fast subset scan; GraphScan; Linear-time subset scanning

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.

Historical Background

The spatial and space-time scan statistics (Kulldorff 19972001), building on earlier work on scan statistics by Naus (1965) and others, are powerful and widely used methods for event detection in spatiotemporal data. These methods evaluate a score function F(S),...

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 1,599.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Hardcover Book
USD 1,999.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

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

    Google Scholar 

  • Costa MA, Assuncao RM, Kulldorff M (2012) Constrained spanning tree algorithms for irregularly-shaped spatial clustering. Comput Stat Data Anal 56(6):1771–1783

    Article  MathSciNet  Google Scholar 

  • 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

    Google Scholar 

  • Duczmal L, Assuncao R (2004) A simulated annealing strategy for the detection of arbitrary shaped spatial clusters. Comput Stat Data Anal 45:269–286

    Article  MATH  Google Scholar 

  • 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

    Article  MATH  Google Scholar 

  • Kulldorff M (1997) A spatial scan statistic. Commun Stat Theory Methods 26(6):1481–1496

    Article  MathSciNet  MATH  Google Scholar 

  • Kulldorff M (2001) Prospective time-periodic geographical disease surveillance using a scan statistic. J R Stat Soc A 164:61–72

    Article  MathSciNet  MATH  Google Scholar 

  • Kulldorff M, Huang L, Pickle L, Ducmzal L (2006) An elliptic spatial scan statistic. Stat Med 25:3929–3943

    Article  MathSciNet  Google Scholar 

  • Kulldorff M, Mostashari F, Duczmal L, Yih WK, Kleinman K, Platt R (2007) Multivariate scan statistics for disease surveillance. Stat Med 26:1824–1833

    Article  MathSciNet  Google Scholar 

  • 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

    Google Scholar 

  • McFowland III E, Speakman S, Neill DB (2013) Fast generalized subset scan for anomalous pattern detection. J Mach Learn Res 14:1533–1561

    MathSciNet  MATH  Google Scholar 

  • Naus JI (1965) The distribution of the size of the maximum cluster of points on the line. J Am Stat Assoc 60:532–538

    Article  MathSciNet  Google Scholar 

  • Neill DB (2009a) An empirical comparison of spatial scan statistics for outbreak detection. Int J Health Geogr 8:20

    Article  Google Scholar 

  • Neill DB (2009b) Expectation-based scan statistics for monitoring spatial time series data. Int J Forecast 25:498–517

    Article  Google Scholar 

  • Neill DB (2012) Fast subset scan for spatial pattern detection. J R Stat Soc Ser B Stat Methodol 74(2):337–360

    Article  MathSciNet  Google Scholar 

  • Neill DB, Kumar T (2013) Fast multidimensional subset scan for outbreak detection and characterization. Online J Publ Health Inf 5(1):156

    Google Scholar 

  • 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

    Google Scholar 

  • 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

    Google Scholar 

  • Neill DB, McFowland III E, Zheng H (2013) Fast subset scan for multivariate event detection. Stat Med 32:2185–2208

    Article  MathSciNet  Google Scholar 

  • 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

    Google Scholar 

  • Patil GP, Taillie C (2004) Upper level set scan statistic for detecting arbitrarily shaped hotspots. Environ Ecol Stat 11:183–197

    Article  MathSciNet  Google Scholar 

  • 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

    Google Scholar 

  • 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

    Google Scholar 

  • Speakman S, McFowland III E, Neill DB (2015) Scalable detection of anomalous patterns with connectivity constraints. J Comput Graph Stat 24(4):1014–1033

    Article  MathSciNet  Google Scholar 

  • Speakman S, Somanchi S, McFowland III E, Neill DB (2016, in press) Penalized fast subset scanning. J Comput Graph Stat

    Google Scholar 

  • Tango T, Takahashi K (2005) A flexibly shaped spatial scan statistic for detecting clusters. Int J Health Geogr 4:11

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Editor information

Editors and Affiliations

Rights and permissions

Reprints 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

Publish with us

Policies and ethics