Linear Hotspot Discovery on All Simple Paths: A Summary of Results

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. The problem is #p-hard due to the exponential number of simple paths. To address the computational challenges, we propose a novel algorithm named bi-directional fragment-multi-graph traversal (ASP_FMGT) and two path reduction approaches ASP_NR and ASP_HD. Extensive theoretical and experimental analyses show that ASP_FMGT has substantially improved performance over a baseline approach using depth-first-search with backtracking (ASP_Base) while keeping the solution complete and correct. Moreover, case studies on real-world datasets showed that ASP_FMGT outperforms existing approaches, including by discovering new hotspots unknown before and achieving higher accuracy for locating known hotspots.