一种从时空数据中挖掘事件影响传播树的新方法  

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

作　　者：房滇武 王丽珍 邹目权 邓飞 FANG Dianwu;WANG Lizhen;ZOU Muquan;DENG Fei(School of Information Engineering,Kunming University,Kunming 650214,China;Dianchi College,Kunming 650228,China;Postdoctoral Research Workstation,FuDian Bank,Kunming 650200,China)

机构地区：[1]昆明学院信息工程学院,云南昆明650214 [2]滇池学院,云南昆明650228 [3]富滇银行股份有限公司博士后科研工作站,云南昆明650200

出　　处：《智能科学与技术学报》2024年第4期509-521,共13页Chinese Journal of Intelligent Science and Technology

基　　金：昆明学院引进人才科研项目(No.XJ20230085);云南省彩云博士后计划—创新项目(No.YNBH24024);云南省地方本科高校基础研究联合专项(No.202101BA070001-152);昆明学院重点科研团队项目(No.XJ20230047);云南省院士专家工作站项目(No.202205AF150031)。

摘　　要：时空事件连锁发生的现象,在现实中很常见。为揭示这类现象背后的机制,开启了影响传播模式挖掘研究。挖掘事件影响传播树是其中一项基础工作,通常根据事件时空邻近关系,生成事件邻居集,用前缀树方法构建事件影响传播树。在时空事件较稠密时,组合式增长使挖掘时间与空间成本剧增,无法对大规模数据进行挖掘。为此,提出一种新方法,通过构建地理空间实体KD树,检索事件之间的时空邻近关系。设计一种三层哈希图数据结构存储事件的时空邻近关系,使事件影响传播树的信息虚拟化,不创建树实体,避免组合爆炸和大量树操作,提高挖掘效率,降低空间成本。在LSTW时空数据集上的实验结果,验证了新方法的效果。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.

关 键 词：时空数据挖掘 事件影响传播树 KD树 哈希图 

分 类 号：TP391.4[自动化与计算机技术—计算机应用技术]