Scalable Spatial Scan Statistics with Coresets
summary
Presents a practical pipeline that builds small geometric coresets to scan millions of geo-located points: construct an epsilon-sample (often ~2–3k points) and an epsilon-net on the dual (often ~100 points), then scan a restricted range family. Uses ham‑sandwich / KD-style partitions to construct samples in near‑linear time and proves reduced sample bounds (e.g. constructive halfspace samples near 1/epsilon^{4/3}, improvements from 1/epsilon to 1/sqrt(epsilon) in some reductions). Implementation finds planted anomalies with high power and scans 10M points in fractions of a second.
AI-written summary · about
chapters (7)
- 0:00Introduction to spatial data
- 2:34The spatial scan statistic
- 5:47Computational challenges
- 10:46Epsilon samples and nets
- 19:25Optimizing scan algorithms
- 26:30Practical performance results
- 34:09Constructive geometric methods
related talks
52mCoresets and Their Applications to Design Sublinear Algorithms
33mComputation-Statistics Tradeoffs in Unsupervised Learning via Data Summarization
01h 03mSampling for Linear Algebra, Statistics, and Optimization I
35mSampling for Subset Selection and Applications
30mParallelization by Approximation
01h 26mStreaming, Sketching and Sufficient Statistics II
55mParallel Coordinate Descent Methods for Big Data Optimization
25mUsing Set Cover to Optimize a Large-Scale Low Latency Distributed Graph