面向时空轨迹流的共同运动模式分布式挖掘算法

Distributed Mining Algorithm for Co-movement Patterns in Spatio-Temporal Trajectory Streams

从轨迹流中挖掘共同运动模式指在同一时间内发现具有相同运动行为的移动对象群体,在交通物流、疫情防控等方面具有重要意义。然而,现有研究面对大规模轨迹流数据难以做到快速响应。因此,本文首先提出了基于滑动窗口的分布式时空轨迹流共同运动模式挖掘算法,使用滑动窗口计算模型代替快照计算模型,利用增量式更新代替重新计算,使算法更适用于无界且快速到达的轨迹流数据,在效率和有效性方面呈现更好的性能。其次,针对分布式流处理系统中由于负载不均导致性能下降问题,提出了自适应多级动态数据分发策略,该策略能够适应轨迹流数据的动态变化,实时监测系统负载情况并根据负载不均的程度做出适当调整。最后,基于分布式流处理平台Flink实现了上述功能,并通过真实数据集的实验证明本文提出的算法比基准方法具有更快的响应速度和更低的延迟。

Mining co-movement patterns from trajectory streams refers to discovering groups of moving objects with same behaviors at the same time,which is essential for transportation logistics,epidemic prevention and control and so on.However,the existing research faces difficulties in responding quickly to large-scale trajectory data streams.Therefore,this paper proposes a novel distributed sliding window algorithm for mining co-movement patterns from spatio-temporal trajectory streams.The algorithm employs a sliding window computing model instead of a snapshot computing model,and utilizes incremental updates instead of re-computing,making it more suitable for handling unbounded and rapidly arriving trajectory data streams.The proposed algorithm demonstrates superior performance in terms of efficiency and effectiveness.Secondly,to address the issue of load imbalance in distributed stream processing systems,this paper proposes an adaptive multi-level dynamic data partitioning strategy.This strategy can adapt to the dynamic changes in trajectory stream data,continuously monitor the system load in real-time,and make appropriate adjustments based on the degree of load imbalance.Finally,this paper implements the above functions on the Flink distributed big data processing platform and uses real data sets for experiments.Comprehensive empirical study demonstrates that the proposed algorithm has faster response speed and lower delay than the baseline method.