Linear Hotspot Discovery on All Simple Paths: A Summary of Results
2019-09-10
Loading...
View/Download File
Persistent link to this item
Statistics
View StatisticsJournal Title
Journal ISSN
Volume Title
Title
Linear Hotspot Discovery on All Simple Paths: A Summary of Results
Authors
Published Date
2019-09-10
Publisher
Type
Report
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.
Keywords
Description
Related to
Replaces
License
Series/Report Number
Funding information
Isbn identifier
Doi identifier
Previously Published Citation
Suggested citation
Tang, Xun; Gupta, Jayant; Shekhar, Shashi. (2019). Linear Hotspot Discovery on All Simple Paths: A Summary of Results. Retrieved from the University Digital Conservancy, https://hdl.handle.net/11299/216042.
Content distributed via the University Digital Conservancy may be subject to additional license and use restrictions applied by the depositor. By using these files, users agree to the Terms of Use. Materials in the UDC may contain content that is disturbing and/or harmful. For more information, please see our statement on harmful content in digital repositories.