Fast Algorithms for Spatial K-Core Discovery and Maintenance
Hao Yang, Keyi Wang, Renjie Sun, Xiaoyang Wang · 2020
With the proliferation of location-based services, there is a rapidly growing amount of spatial data, which tends to be large and complex. To make sense of these data, in this paper, we first propose a novel model, named spatialk-core, by leveraging thek-core concept. Given a set of 2-dimensional data nodes, the spatialk-core is the maximal subset of nodes, where each node has at least k close neighbors. Two nodes are close if their spatial distance is not larger than a given threshold. However, existing spatial graph analysis only focuses on static spatial graphs and ignores the evolution of spatial graphs caused by node movement. To address the concern above, we first develop efficient algorithms to discover the spatialk-core and then propose several pruning rules to accelerate the process of maintaining the spatialk-core in location evolving data. Extensive experiments validate the superiority of our proposed algorithms.