Aarhus University Seal

Theory seminar - Jeffrey Phillips: Scalable Spatial Scan Statistics with Coresets (copy 1)

Spatial Scan Statistics measure and detect anomalous spatial behavior, specifically they identify geometric regions where significantly more of a measured characteristic is found than would be expected from the background distribution.

Info about event

Time

Tuesday 16 October 2018,  at 13:15 - 14:00

Location

Nygaard-395 (5335-395). Åbogade 34, 8200 Aarhus N

Organizer

Peyman Afshani

Abstract

Spatial Scan Statistics measure and detect anomalous spatial behavior, specifically they identify geometric regions where significantly more of a measured characteristic is found than would be expected from the background distribution.  These techniques have been used widely in geographic information science, such as to pinpoint disease outbreaks.  However, until recently, available algorithms and software only scaled to at most a thousand or so spatial records.  In this work I will describe how using coresets, efficient constructions, and scanning algorithms, we have developed new algorithms and software that easily scales to millions or more data points.  Along the way we provide new efficient algorithms and constructions for eps-samples and eps-nets for various geometric range spaces.  This is a case where subtle theoretical improvements of old structures from discrete geometry actually result in substantial empirical improvements.

Host: Peyman Afshani