移动对象数据库中海量时空轨迹数据压缩方法研究

Trajectory is everywhere.With the widely spreading of positioning techniques of satellites, wireless sensors and smart devices, trajectory data is increasing by blasting and challenges the serviceability of moving object database. Recent works of trajectory compression focus on single trajectory only, and they consider little on redundancy between multiple trajectories, which is the inherent attribute of trajectories because objects move similarly in nature. Furthermore, the efficiency of inquiries on compressed trajectories is also critical important in moving object databases..To tackle the growing massive volume of trajectory data, the aim of this project is to seek a novel method of trajectory compression applying for moving object database. Firstly, we propose a redundant model between multiple trajectories, employ statistical methods and computational geometry to cluster 'near-duplicates' from segments of trajectories, and abstract an item of 'near trajectory dictionary' from each cluster. Secondly, we introduce a hierarchical sketch model to represent an original trajectory, supporting with necessary data structures and indexing methods. Thirdly, to fulfill different requirements of trajectory compression, we adopt an adaptive framework on choosing and scheduling the compression algorithms. Finally, comprehensive experiments are carried out within practical environments utilizing moving object databases.

随着卫星定位技术、物联网定位技术和智能终端的普及，如保存与管理移动对象产生的海量时空轨迹数据，成为当前移动对象数据库研究中的核心关键问题之一。目前轨迹数据压缩方法研究集中在压缩单条轨迹数据，很少考虑移动对象运动模式的相似性带来的数据冗余，以及压缩后轨迹的索引与查询效率，难以适用于移动对象数据库环境。.本项目针对日益增长的轨迹数据海量性挑战，研究适用于移动对象数据库的轨迹压缩方法，首先提出一个多轨迹冗余度模型，并基于时空统计及计算几何方法快速聚类近似副本集合，为轨迹压缩提供冗余信息的表征与提取方法，然后进一步结合移动对象数据库环境，采用分层概略化方法，建立轨迹压缩存储及索引模型，支持压缩后轨迹的高效访问，接着面向轨迹压缩需求特征提炼度量指标，进行自适应调整，最后在理论方法研究的基础上，与移动对象数据库进行集成验证。

移动对象数据库是一种面向现代信息化和大数据时代进展中感知与管理海量移动对象时空信息的新型数据管理系统。移动对象所产生的数据(又称轨迹数据)随着定位技术、智能终端和手机APP应用的普及在急速增长并且日积月累。这类数据符合大数据的3V模型特征，能够为研究个体运动、群体行为乃至社会发展提供时空维度的情报。本研究针对如何保存与管理移动对象产生的海量时空轨迹数据这一个基础问题，从三个方面展开了理论研究与实践：.1. 研究了时空轨迹数据的相似性分布与压缩算法效率的关系，提出了一种面向时空轨迹相似性的benchmark，提出采样率、覆盖率、最大允许偏差、长周期有效性等指标来度量时空轨迹数据的冗余性与完整性，研究成果不仅对于数据压缩技术有效，而且对于行程推荐、交通监控和通勤模式分析等应用场景都具有指导意义。.2. 研究了多种误差受控的时空轨迹压缩算法，从时空受限空间（如路网空间）、几何运动特征、到数据降维近似技术等不同维度对压缩方法和影响因素进行了定量实验分析，压缩率可以高达30~50倍，远高于LZMA压缩算法的10倍压缩率和DP线性简化压缩算法的20倍压缩率；对于频繁采样数据压缩率可以提高至200+倍。.3. 在真实的移动对象数据库系统上对所提技术进行了实验验证，数据压缩得到了显著提升并且在国际最新大数据系统HANA上得到了初步推广，所开发原型模块也通过了权威测评。