Discovering Spatial Mixture Patterns of Interest

Yiqun Xie, Han Bao, Yan Li, Shashi Shekhar

Research output: Chapter in Book/Report/Conference proceedingConference contribution

8 Scopus citations


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 languageEnglish (US)
Title of host publicationProceedings of the 28th International Conference on Advances in Geographic Information Systems, SIGSPATIAL GIS 2020
EditorsChang-Tien Lu, Fusheng Wang, Goce Trajcevski, Yan Huang, Shawn Newsam, Li Xiong
PublisherAssociation for Computing Machinery
Number of pages10
ISBN (Electronic)9781450380195
StatePublished - Nov 3 2020
Event28th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, SIGSPATIAL GIS 2020 - Virtual, Online, United States
Duration: Nov 3 2020Nov 6 2020

Publication series

NameGIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems


Conference28th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, SIGSPATIAL GIS 2020
Country/TerritoryUnited States
CityVirtual, Online

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.


  • Spatial mixture pattern
  • spatial mixture index
  • statistical robustness


Dive into the research topics of 'Discovering Spatial Mixture Patterns of Interest'. Together they form a unique fingerprint.

Cite this