Distribution-free detection of structured anomalies: permutation and rank-based scans

Ery Arias-Castro, Rui M. Castro, Ervin Tánczos, Meng Wang

Research output: Contribution to journalArticleAcademicpeer-review

18 Citations (Scopus)
1 Downloads (Pure)


The scan statistic is by far the most popular method for anomaly detection, being popular in syndromic surveillance, signal and image processing, and target detection based on sensor networks, among other applications. The use of the scan statistics in such settings yields a hypothesis testing procedure, where the null hypothesis corresponds to the absence of anomalous behavior. If the null distribution is known, then calibration of a scan-based test is relatively easy, as it can be done by Monte Carlo simulation. When the null distribution is unknown, it is less straightforward. We investigate two procedures. The first one is a calibration by permutation and the other is a rank-based scan test, which is distribution-free and less sensitive to outliers. Furthermore, the rank scan test requires only a one-time calibration for a given data size making it computationally much more appealing. In both cases, we quantify the performance loss with respect to an oracle scan test that knows the null distribution. We show that using one of these calibration procedures results in only a very small loss of power in the context of a natural exponential family. This includes the classical normal location model, popular in signal processing, and the Poisson model, popular in syndromic surveillance. We perform numerical experiments on simulated data further supporting our theory and also on a real dataset from genomics. Supplementary materials for this article are available online.

Original languageEnglish
Pages (from-to)789-801
Number of pages13
JournalJournal of the American Statistical Association
Issue number522
Publication statusPublished - 3 Apr 2018


  • Permutation tests
  • Rank tests
  • Scan statistic


Dive into the research topics of 'Distribution-free detection of structured anomalies: permutation and rank-based scans'. Together they form a unique fingerprint.

Cite this