顾及轨迹压缩的车辆路径查询算法  

Vehicle path queries method considering vehicle trajectory compression

作　　者：赵东保 邓悦 ZHAO Dongbao;DENG Yue(College of Surveying and Geo-Informatics,North China University of Water Resources and Electric Power,Zhengzhou 450046,China;Henan Institute of Geophysical Space Information,Zhengzhou 450009,China)

机构地区：[1]华北水利水电大学测绘与地理信息学院,河南郑州450046 [2]河南省地球物理空间信息研究院,河南郑州450009

出　　处：《测绘学报》2023年第3期501-514,共14页Acta Geodaetica et Cartographica Sinica

基　　金：国家自然科学基金(41971346);嵩山实验室预研项目(YYJC062022013)。

摘　　要：基于位置服务技术的迅猛发展,产生了巨量车辆轨迹数据。为了有效压缩并查询大规模车辆轨迹数据,本文提出一种面向压缩车辆轨迹的路径空间查询算法。本文算法基于Stroke道路层次结构压缩轨迹空间数据,提取关键变速点压缩轨迹时间数据,并构建了一种用于建立轨迹空间和时间数据之间联系的哈希编码,从而实现车辆轨迹的时空数据集成压缩。利用后缀数组对车辆轨迹的基于Stroke路段的压缩编码构建空间索引结构,再以此为基础,设计了车辆轨迹所对应路径的点信息查询算法、相同子路径查询算法和相似路径查询算法。试验结果表明,针对原始轨迹点空间数据,本文的压缩编码方法压缩比可以达到97∶1,与常规的基于路段编码方式相比,本文压缩编码在车辆轨迹的点信息路径查询方面,查询效率可以提升约2倍;在车辆轨迹的相同子路径查询方面,查询效率可以提升约8倍;在车辆轨迹的相似路径查询方面,查询耗时增长率减少了50%。本文算法对于大规模车辆轨迹的数据管理具有十分重要的基础性作用。With the rapid development of location-based service technology,a huge amount of vehicle trajectory data has been generated.To effectively compress and query large-scale vehicle trajectory data,this paper proposes a path spatial queries algorithm for compressed vehicle trajectories.The algorithm compresses the spatial data of trajectories based on the Stroke road hierarchical structure,compresses the temporal data of trajectories by extracting the key variable speed points,and constructs a hash coding for establishing the connection between trajectory spatial data and trajectory temporal data,so as to realize the integrated compression of spatio-temporal data of vehicle trajectories.The suffix array is used to construct the spatial index structure of the compression coding based on the Stroke segment of the vehicle trajectories.On this basis,the point information query algorithm,strict path query algorithm and similar path query algorithm of the corresponding path of vehicle trajectories are designed.The experimental results indicate that for the original trajectory point spatial data,the compression ratio of the proposed compression coding method can reach 97∶1.Compared with the conventional road segments-based coding mode,the proposed compression coding method has high path spatial queries performance.In the point information query of the path corresponding to the vehicle trajectory,the query efficiency can be increased by about 2 times.In the strict sub-path query of the vehicle trajectory,the query efficiency can be increased by about 8 times,and the growth rate of the query time is reduced by about 50%in the similar path query of the vehicle trajectory.This method plays a fundamental role in the data management of large-scale vehicle trajectories.

关 键 词：轨迹压缩 Stroke层次结构 相同路径查询 相似路径查询 

分 类 号：P208[天文地球—地图制图学与地理信息工程]