Browsing by Author "Tang, Xun"

Now showing 1 - 6 of 6
  • Thumbnail Image
    Item
    Crime Hotspot Detection: A Computational Perspective
    (2016-09-01) Eftelioglu, Emre; Tang, Xun; Shekhar, Shashi
    Given a set of crime locations, a statistically significant crime hotspot is an area where the concentration of crimes inside is significantly higher than outside. The motivation of crime hotspot detection is twofold: detecting crime hotspots to focus the deployment of police enforcement and predicting the potential residence of a serial criminal. Crime hotspot detection is computationally challenging due to the difficulty of enumerating all potential hotspot areas, selecting an interest measure to compare these with the overall crime intensity, and testing for statistical significance to reduce chance patterns. This chapter focuses on statistical significant crime hotspots. First, the foundations of spatial scan statistics and its applications (i.e. SaTScan) to circular hotspot detection are reviewed. Next, ring-shaped hotspot detection is introduced. Third, linear hotspot detection is described since most crimes occur along a road network. The chapter concludes with future research directions in crime hotspot detection.
  • Thumbnail Image
    Item
    Data Science for Mining Patterns in Spatial Events
    (2019-05) Tang, Xun
    There has been an explosive growth of spatial data over the last decades thanks to the popularity of location-based services (e.g., Google Maps), affordable devices (e.g., mobile phone with GPS receiver), and fast development of data transfer and storage technologies. This significant growth as well as the emergence of new technologies emphasize the need for automated discovery of spatial patterns which can facilitate applications such as mechanical engineering, transportation engineering, and public safety. This thesis investigates novel and societally important patterns from various types of large scale spatial events such as spatial point events, spatio-temporal point events, and spatio-temporal linear events. Multiple novel approaches are proposed to address the statistical, computational, and mathematical challenges posed by different patterns. Specifically, a neighbor node filter and a shortest tree pruning algorithms are developed to discover linear hotspots on shortest paths, a bi-directional fragment-multi- graph traversal is proposed for discovering linear hotspots on all simple paths, and an apriori-graph traversal algorithm is proposed to detecting spatio-temporal intersection patterns. Extensive theoretical and experimental analyses show that the proposed approaches not only achieve substantial computational efficiency but also guarantee mathematical properties such as solution correctness and completeness. Case studies using real-world datasets demonstrate that the proposed approaches identify valuable patterns that are not detected by current state-of-the-art methods.
  • Thumbnail Image
    Item
    Linear Hotspot Discovery on All Simple Paths: A Summary of Results
    (2019-09-10) Tang, Xun; Gupta, Jayant; Shekhar, Shashi
    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.
  • Thumbnail Image
    Item
    Significant Linear Hotspot Discovery
    (2016-11-18) Tang, Xun; Eftelioglu, Emre; Oliver, Dev; Shekhar, Shashi
    Given a spatial network and a collection of activities (e.g., pedestrian fatality reports, crime reports), Significant Linear Hotspot Discovery (SLHD) finds all shortest paths in the spatial network where the concentration of activities is statistically significantly high. SLHD is important for societal applications in transportation safety or public safety such as finding paths with significant concentrations of accidents or crimes. SLHD is challenging because 1) there are a potentially large number of candidate paths (? 1016) in a given dataset with millions of activities and road network nodes and 2) test statistic (e.g., density ratio) is not monotonic. Hotspot detection approaches on Euclidean space (e.g., SaTScan) may miss significant paths since a large fraction of an area bounded by shapes in Euclidean space for activities on a path will be empty. Previous network-based approaches consider only paths between road intersections but not activities. This paper proposes novel models and algorithms for discovering statistically significant linear hotspots using the algorithms of neighbor node filter, shortest path tree pruning, and Monte Carlo speedup. We present case studies comparing the proposed approaches with existing techniques on real data. Experimental results show that the proposed algorithms yield substantial computational savings without reducing result quality.
  • Thumbnail Image
    Item
    Transdisciplinary Foundations of Geospatial Data Science
    (2017-12-05) Xie, Yiqun; Eftelioglu, Emre; Ali, Reem Y.; Tang, Xun; Li, Yan; Doshi, Ruhi; Shekhar, Shashi
    Recent developments in data mining and machine learning approaches have brought lots of excitement in providing solutions for challenging tasks (e.g., computer vision). However, many approaches have limited interpretability, so their success and failure modes are difficult to understand and their scientific robustness is difficult to evaluate. Thus, there is an urgent need for better understanding of the scientific reasoning behind data mining and machine learning approaches. This requires taking a transdisciplinary view of data science and recognizing its foundations in mathematics, statistics, and computer science. Focusing on the geospatial domain, we apply this crucial transdisciplinary perspective to five common geospatial techniques (hotspot detection, colocation detection, prediction, outlier detection and teleconnection detection). We also describe challenges and opportunities for future advancement.
  • Thumbnail Image
    Item
    You Can’t Smoke Here: Towards Support for Space Usage Rules in Location-aware Technologies
    (2014-09-22) Samsonov, Pavel; Tang, Xun; Schoening, Johannes; Kuhn, Werner
    Recent work has identified the lack of space usage rule (SUR) data – e.g. “no smoking”, “no campfires” – as an important limitation of online/mobile maps that presents risks to user safety and the environment. In order to address this limitation, a large-scale means of mapping SURs must be developed. In this paper, we introduce and motivate the problem of mapping space usage rules and take the first steps towards identifying solutions. We show how computer vision can be employed to identify SUR indicators in the environment (e.g. “No Smoking” signs) with reasonable accuracy and describe techniques that can assign each rule to the appropriate geographic feature. We also discuss how our methods can be applied to large repositories of spatially-referenced images (e.g. Google Street View) to generate global-scale datasets of SURs.