通过空间网络中的局部K函数实现渐进式且可扩展的热点检测

《ACM Transactions on Spatial Algorithms and Systems》：Progressive and Scalable Hotspot Detection through Local K-Function in Spatial Networks

热点检测方法研究

　　

摘要

地理标记数据的广泛可用性结合现代地图服务，使得数据能够准确地与空间网络关联起来。在空间网络上应用统计分析（如热点检测）对于精确的量化和模式分析至关重要，这有助于在各种重要应用中做出有效的决策。现有的空间网络热点检测算法要么缺乏关于检测到的热点的充分统计证据（例如聚类分析），要么需要高昂的计算成本才能提供这些证据。在本文中，我们提出了基于网络局部K函数的热点检测算法，这些算法可以处理预定义和未知的热点半径。K函数是一种广泛用于网络模式分析的统计方法，能够帮助理解空间网络中活动和事件的密度与分布。然而，由于其效率低下，尤其是对于大型网络而言，它的实际应用受到了限制。通过使用真实和合成数据集进行的广泛实验评估表明，我们的算法在计算具有预定义半径的热点时速度比现有算法快28倍，在识别没有预定义半径的热点时速度快四个数量级以上。此外，为了解决空间网络的动态变化问题，我们提出了一种增量式热点检测方法，该方法在添加新事件时能够高效地更新热点检测结果，从而利用之前的分析结果。