时空轨迹大数据分布式蜂群模式挖掘算法

J4 ›› 2016, Vol. 38 ›› Issue (2): 255-261.

时空轨迹大数据分布式蜂群模式挖掘算法

于彦伟1,2,齐建鹏1,陆云辉1,2,赵金东1,张永刚2

(1.烟台大学计算机与控制工程学院，山东烟台 264005;
2.吉林大学符号计算与知识工程教育部重点实验室，吉林长春 130012)

收稿日期:2015-09-03 修回日期:2015-11-12 出版日期:2016-02-25 发布日期:2016-02-25
基金资助:
国家自然科学基金(61403328,61572419,61403329);吉林大学符号计算与知识工程教育部重点实验室开放基金(93K172014K13);山东省重点研发项目（2015GSF115009）;山东省自然科学基金(ZR2013FM011);山东省高等学校科技计划(J14LN24,J14LN70)

Distributed swarm pattern mining algorithm
in big spatio-temporal trajectory data

YU Yanwei1,2,QI Jianpeng1,LU Yunhui1,2,ZHAO Jindong1,ZHANG Yonggang2

(1.School of Computer and Control Engineering,Yantai University,Yantai 264005;2.Key Laboratory of Symbolic Computation and Knowledge
Engineering of Ministry of Education,Jilin University,Changchun 130012,China)

Received:2015-09-03 Revised:2015-11-12 Online:2016-02-25 Published:2016-02-25

摘要/Abstract

摘要：

针对时空轨迹大数据的蜂群模式挖掘需求，提出了一种高效的基于MapReduce的分布式蜂群模式挖掘算法。首先，提出了基于最大移动目标集的对象集闭合蜂群模式概念，并利用最小时间支集优化了串行挖掘算法；其次，提出了蜂群模式的并行化挖掘模型，利用蜂群模式时间域无关性，并行化了聚类与子时间域上的蜂群模式挖掘过程；第三，设计了一个基于MapReduce链式架构的分布式并行挖掘算法，通过四个阶段快速地实现了蜂群模式的并行挖掘；最后，在Hadoop平台上，使用真实交通轨迹大数据集对分布式算法的有效性和高效性进行了验证与分析。

关键词: 时空轨迹挖掘, 大数据, 蜂群模式, 分布式, MapReduce

Abstract:

We propose an efficient distributed mining algorithm based on MapReduce for mining swarm pattern from big spatiotemporal trajectory data. We first define the objectclosed swarm pattern based on the maximum moving object set, and optimize the serial mining algorithm using the strategy of minimum time support set to minimize the computation costs. We then propose a parallel swarm mining model based on the time independence, and the clustering and the objectclosed swarm mining on the time domain are parallelized. Finally, we propose a distributed mining algorithm based on MapReduce chained architecture, which quickly discovers swarm patterns in big trajectory data by a 4stage framework. Experimental evaluations on the Hadoop platform, using massivescale real world traffic trajectory datasets, demonstrate the effectiveness and efficiency of the proposed distributed algorithm.

Key words: spatiotemporal trajectory mining;big data;swarm pattern;distributed;MapReduce

于彦伟1,2,齐建鹏1,陆云辉1,2,赵金东1,张永刚2. 时空轨迹大数据分布式蜂群模式挖掘算法[J]. J4, 2016, 38(2): 255-261.

YU Yanwei1,2,QI Jianpeng1,LU Yunhui1,2,ZHAO Jindong1,ZHANG Yonggang2. Distributed swarm pattern mining algorithm
in big spatio-temporal trajectory data [J]. J4, 2016, 38(2): 255-261.

[1]	陈侨安1，李峰1，曹越1，龙明盛1,2. 基于运行数据分析的Spark任务参数优化[J]. J4, 20160101, 38(01): 11-19.
[2]	杨乾明, 邵靖杰, 曾聘, 袁梦, 宋卓秦, 邓秋严, 张剑锋, 王勇. 一种基于Crossbar结构的分布式共享缓存交换机设计与实现[J]. 计算机工程与科学, 2025, 47(6): 951-957.
[3]	邓淏天, 吴桐, 张川, 祝烈煌. 基于中继链的跨链分布式身份认证方案[J]. 计算机工程与科学, 2025, 47(6): 1008-1017.
[4]	李胜国, 廖霞, 于恒彪, 黄春, 姜浩, 逯喜燕, 王华林, 成礼智. 面向结构矩阵的可扩展并行矩阵乘算法框架[J]. 计算机工程与科学, 2024, 46(9): 1529-1538.
[5]	赵鑫博, 陆忠华. 面向深度行情因子挖掘的分布式训练关键技术研究[J]. 计算机工程与科学, 2024, 46(9): 1554-1565.
[6]	薛梅婷, 俞万刚, 张纪林, 曾艳, 袁俊峰, 周丽. 一种基于动态空间划分和压缩布隆过滤器相结合的分布式元数据负载均衡算法#br#[J]. 计算机工程与科学, 2024, 46(8): 1381-1389.
[7]	张家豪, 邓金易, 尹首一, 魏少军, 胡杨. 基于Actor模型的众核数据流硬件架构探索[J]. 计算机工程与科学, 2024, 46(6): 959-967.
[8]	钟权, 陈志广, 高蓝光. EMRI-Tree：面向多分辨率可视化的层次式数据结构[J]. 计算机工程与科学, 2024, 46(5): 776-784.
[9]	顾颖程, 魏柳, 姜宁, 程环宇, 刘凯, 宋玉, 刘梅招, 汤雷, 陈彧, 张胜. 边缘场景下面向分布式交互应用的服务器分配[J]. 计算机工程与科学, 2024, 46(10): 1748-1756.
[10]	黄泽彪, 董德尊, 齐星云. Gloo+：利用在网计算技术加速分布式深度学习训练[J]. 计算机工程与科学, 2024, 46(1): 28-36.
[11]	姚袭欣, 章博, 陈香兰, 乔磊, 李曦. 一种基于Event-B语言的时间触发系统建模方法[J]. 计算机工程与科学, 2023, 45(4): 613-621.
[12]	杨浩艺, 陈微, 姚泽欢, 谭郁松, 李非. 基于转录组学数据的抗真菌药物预测方法研究[J]. 计算机工程与科学, 2023, 45(2): 246-251.
[13]	白耀文, 杜亚江, 李宗刚, . 基于多步长的多机器人分布式巡逻算法研究[J]. 计算机工程与科学, 2023, 45(2): 313-320.
[14]	周小华, 王学志, 周园春, 孟珍, . 面向大区域碳卫星数据的分布式Kriging插值算法优化[J]. 计算机工程与科学, 2023, 45(11): 1911-1921.
[15]	葛旭冉, 刘洋, 陈志广, 肖侬. 基于MPI的并行大数据集生成器[J]. 计算机工程与科学, 2022, 44(7): 1152-1161.