Abstract
Given a collection of N geo-located point samples of k types, we aim to detect spatial mixture patterns of interest, which are sub-regions of the study area that have significantly high or low mixture of points of different types. Spatial mixture patterns have important applications in many societal domains, including resilience of smart cities and communities, biodiversity, equity, business intelligence, etc. The problem is challenging because ranking and selection of candidate patterns can be highly susceptible to the effect of natural randomness, and real-world data often consists of various mixture patterns. In related work, the multi-nomial scan statistic does not support identification of high or low mixture due to its "directionless"nature and high sensitivity to the composition of mixture patterns in data. While species richness indices in biodiversity research allow specification of directions, the measures are very sensitive to spatial randomness effects. To bridge the gap, we first propose a spatial mixture index to provide robust ranking among candidate patterns. Then, we present a dual-level Monte-Carlo estimation method with a baseline algorithm for spatial mixture pattern detection. Finally, we propose both an exact algorithm and a distribution-inspired sequence-reduction heuristic to accelerate the baseline approach. Experiment results with both synthetic and real-world data show that the proposed approaches can detect mixture patterns with high accuracy, and the acceleration methods can greatly reduce computational cost while maintaining high solution quality.
Original language | English (US) |
---|---|
Title of host publication | Proceedings of the 28th International Conference on Advances in Geographic Information Systems, SIGSPATIAL GIS 2020 |
Editors | Chang-Tien Lu, Fusheng Wang, Goce Trajcevski, Yan Huang, Shawn Newsam, Li Xiong |
Publisher | Association for Computing Machinery |
Pages | 608-617 |
Number of pages | 10 |
ISBN (Electronic) | 9781450380195 |
DOIs | |
State | Published - Nov 3 2020 |
Externally published | Yes |
Event | 28th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, SIGSPATIAL GIS 2020 - Virtual, Online, United States Duration: Nov 3 2020 → Nov 6 2020 |
Publication series
Name | GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems |
---|
Conference
Conference | 28th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, SIGSPATIAL GIS 2020 |
---|---|
Country/Territory | United States |
City | Virtual, Online |
Period | 11/3/20 → 11/6/20 |
Bibliographical note
Funding Information:This work is supported by the NSF under Grants No. 1029711 and 1737633, the USDA under Grant No. 2017-51181-27222, the Minnesota Supercomputing Institute, and the University of Maryland.
Publisher Copyright:
© 2020 ACM.
Keywords
- Spatial mixture pattern
- spatial mixture index
- statistical robustness