Mining Sustained Emerging Spatio-Temporal Co-occurrence Patterns from Dynamic Spatial Databases
摘要
Sustained emerging spatio-temporal co-occurrence patterns (SECOPs) represent subsets of spatial features, whose instances consistently appear in close proximity across both space and time. Discovering SECOPs is valuable for many applied fields. Existing studies of SECOP mining neglect the emergence of new instances over time in dynamic spatial databases, which may lead to complex changes in neighbor relationships of instances and heterogeneity of the change in the number of feature instances. Therefore, the deviation may be caused in the SECOP measure for dynamic spatial databases with new instances. To solve this problem, we propose the weighted emerging participation index (WEPI) that incorporates the effects of the change of neighbor relationships and the heterogeneity on the sustained emerging measure of SECOPs. Because WEPI does not possess the antimonotone property, we prove an upper bound of the weighted emerging participation ratio of features and introduce a pruning strategy to prune some candidate patterns. Building upon this pruning strategy, an incremental mining algorithm based on depth-first search is proposed, i.e., IM-DFS. In IM-DFS algorithm, a set of optimization techniques is presented to accelerate WEPI calculation. Extensive experiments on real-world dynamic spatial datasets demonstrate the effectiveness of WEPI and the efficiency of IM-DFS.