一种高效的移动对象伴随模式挖掘算法

从时空维度中寻找轨迹相似、时间相近的对象集合,即挖掘移动对象的伴随模式,在基于地理位置的用户行为分析中被广泛使用.然而现有移动对象相似性挖掘算法难以处理时间连续、空间离散、时空相关并且数据量大的时空数据.针对此类数据,设计基于滑动窗口、Apriori性质和贪心选择策略的宽度优先搜索算法,对移动对象伴随模式挖掘问题进行求解.同时结合基于哈希的迭代剪枝算法和基于摘要信息的剪枝算法,设计两层剪枝算法以去除冗余的中间结果.在真实数据上的实验结果表明,与仅使用哈希迭代或摘要信息的剪枝算法相比,该算法的剪枝效率较高,并且能够稳定去除99%以上的冗余数据.

An Efficient Adjoint Pattern Mining Algorithm for Moving Object

Mining adjoint patterns of moving objects is finding the set of objects with similar trajectories and time from a spatio-temporal perspective,which is widely used in user behavior analysis based on geographical location.However,the existing similarity mining algorithms for moving objects can hardly address large amounts of temporally continuous and spatially discrete data of spatio-temporal correlation.To deal with the problem,this paper proposes a width-first search algorithm based on sliding window,Apriori property and greedy selection strategy to solve the problem of mining adjoint patterns of moving objects.Also,a two-layer pruning algorithm is designed combining the iterative pruning algorithm based on Hash iteration and pruning algorithm based on summary information,so as to remove redundant intermediate results.Experimental results on real data show that the pruning efficiency of the proposed algorithm is higher than that of pruning algorithms using only Hash iteration or summary information,meanwhile it can stably remove over 99%of redundant data.