Linear hotspot discovery on all simple paths: A summary of results

Xun Tang, Jayant Gupta, Shashi Shekhar

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

1 Scopus citations

Abstract

Spatial hotspot discovery aims at discovering regions with statistically significant concentration of activities. It has shown great value in many important societal applications such as transportation engineering, public health, and public safety. This paper formulates the problem of Linear Hotspot Detection on All Simple Paths (LHDA) which identifies hotspots from the complete set of simple paths enumerated from a given spatial network. LHDA overcomes the limitations of existing methods which miss hotspots that naturally occur along linear simple paths on a road network. To address the computational challenges, we propose a novel algorithm named bidirectional fragment-multi-graph traversal (ASP_FMGT) and two path reduction approaches ASP_NR and ASP_HD. Experimental analyses show that ASP_FMGT has substantially improved performance over state-of-the-art approach (ASP_Base) while keeping the solution complete and correct. Moreover, a case study on real-world datasets showed that ASP_FMGT outperforms existing approaches.

Original languageEnglish (US)
Title of host publication27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2019
EditorsFarnoush Banaei-Kashani, Goce Trajcevski, Ralf Hartmut Guting, Lars Kulik, Shawn Newsam
PublisherAssociation for Computing Machinery
Pages476-479
Number of pages4
ISBN (Electronic)9781450369091
DOIs
StatePublished - Nov 5 2019
Event27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2019 - Chicago, United States
Duration: Nov 5 2019Nov 8 2019

Publication series

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

Conference

Conference27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2019
CountryUnited States
CityChicago
Period11/5/1911/8/19

Bibliographical note

Funding Information:
ACKNOWLEDGEMENT This material is based upon work supported by the National Science Foundation under Grants No. 1901099, IIS-1320580, the National Geospatial-Intelligence Agency under Grant No. HM0210-13-1-0005. We would also like to thank Kim Koffolt and the spatial computing research group for their helpful comments and refinements. REFERENCES

Keywords

  • Spatial data mining
  • Spatial hotspot detection
  • Spatial networks

Fingerprint Dive into the research topics of 'Linear hotspot discovery on all simple paths: A summary of results'. Together they form a unique fingerprint.

Cite this