面向出行服务中海量时空数据连续查询的分布式计算方法

The processing of spatial-temporal data in trip service has become an important issue of urban big data computing. The critical problem over data calculations faced by many applications can be regarded as the processing of continuous queries on big spatial-temporal data. Thus, in the context of trip service, the core research topics of this project are abstracted to three typical problems with respect to the continuous queries on the spatial-temporal data: continuous k-NN queries on huge amounts of moving objects, continuous queries on itineraries that can be matched and continuous navigation queries based on the dynamic traffic information. Considering the technical and theoretic difficulties such like sizeable account of spatial-temporal data, frequently changed queries and continuous updates of search results, this project dives into the distributed computing methods based on a cluster of physical nodes. Specifically, it focuses on the key techniques including distributed big data index structures, parallel search algorithms and real-time update strategies, and aims to address the problems such as continuous incremental k-NN queries, quick match on huge amount of itineraries and constant optimization of navigation routes. The establishment of these innovative solutions will be of great significance to the promotion of relevant works about spatial-temporal data continuous queries field.

城市出行服务领域的海量时空数据计算已成为城市大数据计算的重要方面，而海量时空数据连续查询问题则是诸多出行服务中数据处理所面临的核心问题。因此，本项目以出行服务实际应用为背景，抽象出时空数据连续查询方面的三个典型问题，即海量移动对象连续k近邻查询问题、可匹配行程连续查询问题和基于动态路网的导航路线持续查询问题，作为核心研究课题。本项目围绕上述问题所面临的时空数据规模巨大、查询空间频繁变化和查询结果持续更新等技术难点，深入探讨应对各个问题的基于多计算节点的分布式计算方法，着重研究分布式环境下处理时空数据连续查询所涉及的海量数据分布式索引结构、可扩展的并行查询算法和查询结果实时更新策略等关键技术，解决连续k近邻增量查询、海量行程快速匹配和导航路线持续优化等科学问题，在时空数据连续查询领域提出创新性的解决思路和研究方法，对于推动该领域相关问题的研究具有重要意义。

城市出行服务领域的海量时空数据计算已成为城市大数据计算的重要方面，而海量时空数据连续查询问题则是诸多出行服务中数据处理所面临的核心问题。因此，本项目以出行服务实际应用为背景，抽象出时空数据连续查询方面的三个典型问题，即海量移动对象连续k近邻查询问题、可匹配行程连续查询问题和基于动态路网的导航路线持续查询问题，作为计划研究的三个核心课题。课题组在具体实施过程中，围绕上述核心问题，就基于道路网络的海量移动对象连续k近邻查询，面向动态路网的导航路线持续并行优化以及基于动态图的k条最短路线分布式查询等问题展开深入研究，充分考虑时空数据规模巨大、查询内容频繁变化和查询结果持续更新等技术难点，深入探讨分布式环境下处理海量时空数据连续查询所涉及的分布式索引结构、可扩展的并行查询算法和查询结果实时更新策略等关键技术，提出了面向动态图的基于分布式双层路线索引的k条最短路线分布式查询算法、基于道路网络的多层动态网格移动对象k近邻增量查询算法以及动态路网上面向大规模导航路线持续并行优化策略等一系列解决方案，很好地完成了本项目预设的研究目标，相关成果发表在数据库和数据挖掘领域国际顶级会议SIGMOD 2020（CCF A类会议），《软件学报》，《Engineering Applications of Artificial Intelligence》（SCI，中科院2区）等国内外知名会议和期刊。这些工作在基于图的海量时空数据查询领域受到了国内外同行的高度认可，对该领域的相关工作具有很好的借鉴和启发意义。