基于局部聚类的轨迹数据流偏倚采样

摘要

Managing trajectories of moving objects is a research focus in mobile computing. Building data synopses by sampling technologies is one of the widely used method. But traditional uniform sampling usually discard some significant points that reveal relative spatiotemporal changes. A novel biased sampling approach based on sliding window model was proposed utilizing the property of local continuity. Firstly, through local clustering, the sliding window was divided into various sized basic windows and sampling the data elements of a basic window using biased sampling rate, then forming trajectory stream synopses. This algorithm takes advantage of the intrinsic characteristics of trajectory stream and achieves superior approximation quality. The extensive experiments verified the effectiveness of our algorithm.%移动对象轨迹数据管理是移动计算领域的研究热点.通过采样技术构造数据流摘要是普遍采用的方法之一.传统的均匀采样往往容易丢失某些关键变化数据.利用轨迹数据流的局部连续性特征,提出一种基于滑动窗口的偏倚采样算法.算法将滑动窗口通过聚类划分成若干大小不一的基本窗口,并针对每个基本窗口给定一个采样率,对窗口内数据进行偏倚采样,从而形成数据流摘要.算法利用了轨迹数据的内在特征,因此具有较高的采样质量.最后,基于实际数据对算法进行了实验,结果证明了算法的有效性.