基于聚类的时空数据有损压缩算法

菜单

摘要车辆的GPS数据中包含的车辆行驶轨迹信息具有重要的理论和应用价值。为减少行驶轨迹数据存储空间，提高数据分析及传送的速度，提出了一种基于聚类的时空数据有损压缩算法，根据GPS数据点的时空三维特征，计算轨迹特征点判断的距离标准，更准确的提取出轨迹信息。算例分析结果表明，基于聚类的时空数据有损压缩算法大幅度减少轨迹压缩误差，提高压缩效率。66809

毕业论文关键词　GPS轨迹数据；数据压缩；基于聚类

ABSTRACT

Vehicle GPS data contained information in the vehicle trajectory has important theoretical and application value.To reduce the trajectory data storage space,and improve data analysis and transmission speed,this paper proposes a spatio-temporal data lossless compression algorithm based on clustering.According to the space-time three-dimensional characteristics of GPS data points, calculating the distance the trajectory feature point judgment standard.Results show that numerical simulation examples,based on the space-time characteristics of GPS trajectory compression error data compression algorithms are greatly reduced,Improve the efficiency of compression.

Keywords : GPS trajectory data; Data compression; Based on the clustering

摘要 2

1 需求介绍 5

2 地理坐标点定义 5

3运行以及编译环境 6

3.1运行环境 6

3.2编译环境 6

4算法分析 6

4.1概述 6

4.2详细描述 6

4.3决策 7

5算法概要设计 7

5.1核心基础设计 7

5.2核心算法示意图 8

5.3流程图 11

6算法详细设计 13

6.1变量设计 13

6.2流程图设计 14

7算法测试 17

7.1测试数据 17

7.2测试结果 17

7.3运行时间 17

结论 19

参考文献 20

致谢 20

附录 21

附录1：算法代码 21

1 需求介绍

时间、空间、属性是地理位置的三个基本特征，也是GIS数据库的三种基本数据组成部分。这里的“空间”指空间位置数据及其派生的数据。“属性”指与空间位置无派生关系的专题属性数据。“时间”则指时间、空间和属性状态的时变信息。随着近些年来以空间数据库为基础的GIS研究和应用的不断深入，随时间而变化的信息越来越受到人们关注，因此提出了时态GIS（简称TGIS）的概念。时态GIS的组织核心是时空数据库，时空数据模型则是时空数据库的基础。时空数据库的数据主要来自于一类按照时间周期返回位置及属性数据的传感器，这类传感器通常会被安装在一些移动的个体上，比如车辆或者个人。通过传感器周期传回的位置及属性数据，系统可以完整的记录下个体的移动轨迹以及对应时间属性值（如速度、温度等）。当前的应用发展趋势表明，被监测个体的数目正在呈爆炸性的增长，同时随着技术的进步以及应用的需求，数据回传的周期也越来越短。例如，南京市的私家车保有量大约在100万台左右，如果后台系统想要实时的知道每台车的位置及属性信息，至少需要对每台车进行秒级采样，我们假设每次每台车上传的数据为50个字节，那么每天的数据增加将达到：4.02T=50byte/条*100*24*60*60。可想而知系统长时间的运行将占用非常庞大的磁盘空间，反之如果针对这些采集数据进行有效压缩，而且压缩算法具有较高的压缩比，则可以节约大量的磁盘空间，极大程度的降低系统的建设成本。