摘要
【目的】为降低轨迹热点挖掘的时空复杂度,针对不同的轨迹数据特征,分别提出基于N度路径表连接、基于N度路径表遍历和基于图数据库的轨迹热点挖掘算法。【方法】如果轨迹数据不存在明显的图结构,基于N度路径表连接和基于N度路径表遍历的算法根据轨迹数据分布是否密集,选择连接或遍历的方式对路径表进行多次迭代,从而得到轨迹热点。如果轨迹数据明显存在图结构,基于图数据库的算法在图数据库中做遍历搜索和剪枝优化,从而得到轨迹热点。【结果】在ChoroChronos开源真实数据集上展开实验。在时间复杂度上,基于图数据库的轨迹热点挖掘算法与表现最好的对比算法相比,运行时间减少1/4。在空间复杂度上,基于N度路径表连接和基于N度路径表遍历的算法与表现最好的对比算法相比,占用内存空间减少2/3。【局限】未考虑轨迹序列包含的时序特征,未在更广泛的数据集上展开实验。【结论】与其他的轨迹热点挖掘对比算法相比,本文算法能够有效降低时空复杂度。
[Objective]This paper proposes multiple Trajectory Traversal Hotspots Mining algorithms based on different trajectory characteristics like N-Degree Trajectory Table Join,N-Degree Trajectory Table Traversal,and graph databases.These algorithms will help us reduce the time and space complexity of trajectory hotspots mining,[Methods]If the trajectory data does not form a complete graph structure,we will use the N-Degree Trajectory Table Join algorithm or N-Degree Trajectory Table Traversal algorithm to iterate the path table multiple times.Based on the distribution density of the trajectory data,the algorithms help us obtain the hotspots.If the trajectory data forms a graph structure,the Trajectory Traversal Hotspots Search algorithm will perform traversal search and pruning optimization to obtain the trajectory hotspots.[Results]We conducted experiments with the ChoroChronos open-source dataset.Regarding time complexity,the running time of the Trajectory Traversal Hotspots Search algorithm was reduced by 25%compared with the best comparison algorithm.Regarding space complexity,the N-Degree Trajectory Table Join algorithm and N-Degree Trajectory Table Traversal algorithm consume 67%less memory space than the best comparison algorithm.[Limitations]We still need to fully utilize the temporal features in the trajectory sequences and should conduct experiments on a more comprehensive dataset.[Conclusions]Compared with other trajectory hotspots mining algorithms,the proposed one effectively reduces the space and time complexity.
作者
颜瑞彬
尹德春
顾益军
Yan Ruibin;Yin Dechun;Gu Yijun(College of Information and Cyber Security,People’s Public Security University of China,Beijing 102600,China)
出处
《数据分析与知识发现》
CSCD
北大核心
2023年第7期58-73,共16页
Data Analysis and Knowledge Discovery
基金
公安部科技强警基础工作专项项目(项目编号:2020GABJC02)
中国人民公安大学基本科研业务费项目(项目编号2022JKF02039)的研究成果之一。
