基于MBR的GPS轨迹数据压缩算法

第26卷2016钲第1期3月信阳农林学院学报JournalofXinyangCollegeofAgricultureandForestryVo1．26No．1Mar．2016基于MBR的GPS轨迹数据压缩算法朱猛，孙剑(信阳农林学院信息212程学院，河南信阳464000)摘要：移动对象产生的大量GPS轨迹数据，蕴含了丰富的时间和空间信息。为了减少GPS轨迹数据的存储空间，提高数据分析的效率，针对常用GPS轨迹数据压缩方法不适用于移动设备的问题，本文提出了一种基于MBR的GPS轨迹数据压缩算法，通过Geoli~作为样本数据集对该算法进行了测试。实验结果表明该算法对全局GPS轨迹数据和局部GPS轨迹数据均有较高的压缩率和压缩精度，为移动设备的GPS轨迹数据提供了一种有效的压缩方法。关键词：GPS轨迹数据：数据压缩；MBR中图分类号：TP301文献标识码：A文章编号：2095—8978(2016)01_()l17-04伴随着物联网的快速发展和移动设备的大量普及，GPS轨迹数据呈爆炸式增长趋势。通过数据挖掘可以从这些数据中获得大量有用信息，构建大数据，实现云计算。但是GPS轨迹数据的巨大数据量给信息挖掘造成很大的困难。轨迹数据压缩成为当前移动设备GPS轨迹数据挖掘的研究热点⋯。所谓数据压缩．就是在保持原GPS轨迹数据形成的路径信息走势的前提下，尽可能的删除无用的点或者信息量少的点。GPS轨迹数据压缩算法主要分为两大类．全局的GPS轨迹数据压缩算法和局部的GPS轨迹数据压缩算法，常见的压缩算法在压缩速度和压缩精度上均不适用于移动设备。如均匀采样法，它按给定的时间间隔或者距离间隔来决定保留哪些点，算法虽然简单，但对时空相关性不敏感，具有很大的不稳定性；航位推算法是通过直接相邻的坐标点的各种特性来决定是否保留当前的点，时间复杂度是线性的，同时也会积累显著的误差；DouglasPeucker算法是Douglas和PeuckerI]提出的，在规定的误差阈值内压缩通过递归选择的两个点之间的线段，其精确性虽高，但同时它对计算机资源(CPU和内存)的消耗也相当高，这种算法的时间复杂度也很高。针对常用GPS迹数据压缩方法不适用于移动设备的特点。本文提出了一种基于MBR的GPS轨迹数据压缩算法1最小边界矩形(MBR)最小边界矩形(MinimumBoundingRectangle，MBR)是指能将GPS轨迹上的一段路径上包括的点全部包含进去的最小矩形。如图l，其中以四个点为一个单位绘制了三个最小边界矩形。图1最小边界矩形的示例收稿日期：2015—11—24基金项目：河南省教育厅高等学校重点科研项目(15A520095)作者简介：朱猛(1977一)，男，江苏沛县人，讲师，硕士，主要研究方向为智能信息处理·l17·第26卷第1期信阳农林学院学报2016年3月例如在一个声音抽样数据中画出了三个最小边界矩形，如图2。通过分析每个范围内的声音数据的信息可以推断出这样的假设：(1)最小边界矩形的面积越大，越多的抽样数据点将被保存进来(图2中的MBR2)。(2)位于最小边界矩形的边界上的抽样数据点包含更多的有用信息(图2中最小边界矩形上的点)。根据对数据的观察，为了达到最少的数据失真．保留信息内容的总量要尽可能的保持不变。在时空数据中，对于研究的轨迹数据，轨迹数据的信息内容可以被每一组抽样数据所表现，位置坐标(X，Y)可以看做和抽样数据中的信息内容是一样的，并且在最小边界矩形上的点包含更多的信息内容。下面研究以此为基础的GPS轨迹数据压缩算法。2基于MBR的轨迹数据压缩方法2．1MBR分割和合并原则根据MBR方法，首先要对轨迹数据进行分割和合并，分割较大的最小边界矩形，合并较小的最小边界矩形，以保证所有的最小边界矩形都有大体一致的面积。图3所示，开始以4个点(这个数值可以由用户自行设定)为一组画出了4个最小边界矩形，然后合并了MBR2和MBR3，因为它们的面积远远小于标准的MBR(标准MBR的面积是由用户自行设定的)，同时分割了MBR4，因为它的面积远远大于标准的MBR。标准MBR的大小可以根据实验或者特殊的需求而设定，它的值和构成MBR的点的数量直接影响GPS轨迹数据压缩的压缩率和压缩精度。_4图3分割和合并原则示例本文采用一种利用周期性计算标准MBR大小的方法，取所有MBR大小的平均值作为标准MBR大小的方法，保证了整个压缩过程中具有一致的压缩精度。这种方法的优势在包含多种运动方式的GPS轨迹中表现的最为突出，因为不同速度等级的移动方式下的标准MBR大小是有显著差别的，而这种方法确定的标准MBR大小避免了不同移动方式下使用固定标准MBR大小产生的失真。l52．2选点策略通过分割和合并后的最小边界矩形，包含大体相同的信息量内容，然后将通过这样的策略来确定哪些点保留和哪