Significant Linear Hotspot Discovery
Significant Linear Hotspot Discovery
复制标题
DOI：
10.1109/tbdata.2016.2631518
复制
发表时间：
2017-06
影响因子：
7.2
通讯作者：
Xun Tang;E. Eftelioglu;Dev Oliver;S. Shekhar
中科院分区：
文献类型：
--
作者：
Xun Tang;E. Eftelioglu;Dev Oliver;S. Shekhar
给定一个空间网络和一系列活动（例如，行人死亡报告、犯罪报告），SLHD （Significant Linear Hotspot Discovery）会发现空间网络中所有活动集中度在统计上显著较高的最短路径。SLHD在交通安全或公共安全方面的社会应用非常重要，例如寻找事故或犯罪严重集中的路径。SLHD具有挑战性，因为1)在给定的具有数百万活动和道路网络节点的数据集中可能存在大量候选路径（$\sim10^{16}$）， 2)测试统计量（例如密度比）不是单调的。欧几里得空间上的热点检测方法（例如SaTScan）可能会错过重要的路径，因为在欧几里得空间中以形状为边界的区域的很大一部分将是空的。以前基于网络的方法只考虑路口之间的路径，而不考虑活动。利用邻节点滤波、最短路径树剪枝和蒙特卡罗加速算法，提出了发现统计显著性线性热点的新模型和算法。我们提出了案例研究，将所提出的方法与现有技术在实际数据上进行比较。实验结果表明，该算法在不降低结果质量的前提下节省了大量的计算量。
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 ( $\sim10^{16}$ ) 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.