Theory seminar - Jeffrey Phillips: Scalable Spatial Scan Statistics with Coresets

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.

2018.10.09 | Dorthe Haagen Nielsen

Date Tue 16 Oct
Time 13:15 14:00
Location Nygaard-395 (5335-395). Åbogade 34, 8200 Aarhus N

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

Site Specific, Lecture / talk, CS frontpage, MADALGO , Public/media, Staff, Students, Target groups, IT, computer science and mathematics