一种最优化的轨迹数据L_(∞)-PLA压缩算法

An optimal L_(∞)-PLA algorithm for trajectory data compression

随着全球定位系统的发展和应用,巨量的轨迹数据被实时收集,给数据的传输、存储和分析带来挑战.基于分段线性近似(piecewise linear approximation,PLA)的数据压缩技术因具有简单直观、压缩存储低和传输快的特点被广泛应用和研究.针对现有轨迹PLA压缩方法不能最优化地在线压缩多维数据的现状,在最大误差限定(maximum error bound,记为L_(∞))下提出多维轨迹数据的最优化PLA压缩问题(记为m DisPLA_(∞)),并给出一种在线MDisPLA算法予以解决.该算法利用“分治-融合”的策略扩展一维最优化PLA算法,以最优化地压缩多维轨迹数据.MDisPLA算法具有线性时间复杂性,可以生成最少的不连续分割,且可以保证生成直线表示的质量,即原始数据点和对应解压缩点之间的同步误差具有上界.通过与基于同步距离锥交(cone intersection using the synchronous Euclidean distance,CISED)的轨迹压缩算法进行理论和实验比较,验证了MDisPLA算法是稳健的,可生成具有保质性的直线表示.MDisPLA算法以更低的内存消耗,较CISED算法提高了14倍左右的处理速度,降低了约48%的分割个数和10.5%的存储个数.MDisPLA算法在保证压缩质量的同时,显著提高了处理速度和降低了存储空间,整体上优于CISED算法.

With the application and development of global positioning system,huge amounts of real-time trajectory data are collected,which gives a challenge for data transmission,storage and analysis.To attack this issue,data compression technology based on piecewise linear approximation(PLA),which is simple and intuitive,less compression storage and faster data transmission,has been widely researched.Currently,the optimal online PLA algorithm can not effectively compress multi-dimensional trajectory data.This paper presented a novel multi-dimensional compression problem under maximum error bound(mDisPLA_(∞)),and proposed an optimal online PLA algorithm MDisPLA to solve it.MDisPLA used a divide-and-conquer strategy to extend the one-dimensional optimal PLA algorithm for optimizing compression of multi-dimensional trajectory data.It can generate the minimum number of disconnected straight lines in linear time complexity,and these lines are quality-ensured,i.e.,the synchronous error between the original point and corresponding recovered one is controlled.With experimental tests by comparing MDisPLA with the state-of-the-art algorithm implemented based on cone intersection using the synchronous Euclidean distance(CISED)on trajectory data sets,it demonstrates that MDisPLA can be stable to generate the quality-ensured lines.It is faster by 14 times than CISED with lower memory requirements,and can reduce the number of segments by 48%and the storage number by 10.5%.MDisPLA significantly improves processing speed and reduces storage while maintaining compression quality.