University of Minnesota
University Relations

Minnesota Supercomputing Institute

Log out of MyMSI

Research Abstracts Online
January 2008 - March 2009

University of Minnesota Twin Cities
Institute of Technology
Department of Computer Science and Engineering

PI: Shashi Shekhar, Fellow

Scalable Parallel Algorithms for Spatial Network Hotspot Discovery

Spatial network hotspots represent connected subsets of a spatial network whose attribute values are significantly higher than expected. Discovering and quantifying spatial network hotspots is important to many application domains, including crime analysis (subsets of high-crime-density streets), police force deployment (planning effective patrolling and/or force deployment to mitigate crime), traffic calming and management (planning efficient placement of barricades and/or security installation in order to minimize traffic congestion and/or effective crowd control during public events). In urban areas, many human activities are centered around spatial infrastructure networks, such as transportation, oil/gas pipelines, and utilities. Thus activity reports such as crime reports may often use network-based location references (e.g., street addresses). In addition, spatial interaction among activities at nearby locations may be constrained by network topology and proximity rather than the planar space assumption of traditional spatial analysis.

The spatial network hotspot discovery problem is challenging because of the potentially conflicting analytical requirements of a spatial point process constrained by a network and point density attributed to network links. Current approaches such as the network K-Function and its variants identify graph hotspots purely based on a spatial point process constrained over a network without considering the effects of a network’s links. In contrast, the approach taken by these researchers not only considers a point process constrained by a network to characterize high-activity segments, but also network links to characterize the level of auto-correlation between high-activity segments to discover high-activity subsets of a spatial network. The researchers are computationally exploring efficient algorithms for statistically interpretable results.

Group Members

Mete Celik, Graduate Student
Betsy George, Graduate Student
James M. Kang, Graduate Student
Pradeep Mohan, Graduate Student