A new method for mining event influence propagation trees from spatio-temporal data

In reality, there was often a phenomenon where spatio-temporal events happened one by one. To uncover the mechanism behind phenomenon of this kind, the research of influence propagation pattern mining was initiated. One of fundamental tasks was to mine event influence propagation trees. A traditional way was used to generate a set of spatio-temporal event neighbors based on spatio-temporal proximity of events, and apply a prefix tree method to construct an event influence propagation tree. Once the spatio-temporal events were dense, the cost of mining time and space would be significantly increased by an explosive growth in the number of combinations, therefore, it would be difficult to mine large-scale data. To this end, a new method was proposed to construct a KD tree of geographic entities and retrieve the spatio-temporal proximity relationship between events. A three-layer Hashmap data structure was designed to store the spatio-temporal proximity relationship between events, virtualizing the information of event influence propagation trees without creating entities of trees. Thus combinatorial explosion and a large number of tree operations were avoided, the mining efficiency was improved and spatial costs were cut down. The experimental results on the LSTW spatio-temporal dataset verify the effectiveness and efficiency of new method.