Random walks to identify anomalous free-form spatial scan windows

Vandana P. Janeja, Vijayalakshmi Atluri

Research output: Contribution to journalArticlepeer-review

21 Scopus citations


Often, it is required to Identify anomalous windows over a spatial region that reflect unusual rate of occurrence of a specific event of interest. A spatial scan statistic-based approach essentially considers a scan window and computes the statistic of a parameter(s) of interest, and identifies anomalous windows by moving the scan window in the region. While this approach has been successfully employed in identifying anomalous windows, earlier proposals adopting spatial scan statistic suffer from two limitations: 1) In general, the scan window should be of a regular shape (e.g., circle, rectangle, cylinder). Thus, most approaches are capable of identifying anomalous windows of fixed shapes only. However, the region of anomaly, in general, is not necessarily of a regular shape. Recent proposals to identify windows of irregular shapes identify windows much larger than the true anomalies or penalize large-sized windows. 2) These techniques take into account autocorrelation among spatial data but not spatial heterogeneity. As a result, they often result in inaccurate anomalous windows. To address these limitations, in this paper, we propose a random-walk-based Free-Form Spatial Scan Statistic (FS3). We construct a weighted Delaunay nearest neighbor (WDNN) graph to capture both spatial autocorrelation and heterogeneity. We then use random walks to identify natural free-form scan windows that are not restricted to a predefined shape. We use spatial scan statistics to identify anomalous windows and prove that they are not random but indeed are formed as a result of an anomaly. Application of FS3 on real data sets has shown that it can identify more refined anomalous windows with better likelihood ratio of it being an anomaly than those identified by earlier spatial scan statistic approaches.

Original languageEnglish (US)
Article number4522549
Pages (from-to)1378-1392
Number of pages15
JournalIEEE Transactions on Knowledge and Data Engineering
Issue number10
StatePublished - Oct 2008

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics


  • Random walk
  • Spatial scan statistics
  • Spatial scan window


Dive into the research topics of 'Random walks to identify anomalous free-form spatial scan windows'. Together they form a unique fingerprint.

Cite this