轨迹数据的分布式存储与关键查询优化

Along with the rapid development of the Mobile Internet, trajectory data collected by various location-based applications increases as never before. In such a Big Data era, it is essential to study and develop technologies that can process trajectory data in the distributed environment, in order to deal with its massive volume with large-scale heterogeneous clusters. The trajectories are mainly composed with a large set of spatio-temporal data sampled from moving objects, like cars. Therefore, they need much larger storage space and parsing cost, also they distribute very unevenly on both spatial and temporal dimensions. Because of these specialties from the common data types, representing and storing the trajectory data with the usual key-value pairs and the row-based distribution can cause high processing cost for accessing and parsing in parallel those result-irrelevant trajectories. In addition, in some important parallel operations like spatio-temporal join and aggregation, such a storage mechanism costs highly on dividing, duplicating and re-distributing data via the network. Regarding these issues, this project intends to build a hybrid architecture by coupling Hadoop with a moving objects databases, in order to take the full advantages from both sides. Based on this platform, we first intend to get rid of the rigid HDFS key-value model and improve the system’s access performance on trajectory data, by studying the independent multi-level column-based storage mechanism and redundant Trojan spatio-temporal index. Second we intend to propose novel approaches to improve the processing efficiency on those typical high-cost operations, by importing an uneven grid to re-distribute the trajectories based on a global sample index. At last, we desire to support the standard declarative query language like SQL and optimize the generated query plans based on a distributed cost model, in order to construct a practical distributed processing platform that can be used in our continuous research. Therefore, this project has both scientific and economic values.

伴随着移动互联网的迅猛发展，大量由位置服务应用采集的轨迹数据正在极剧增长。为了能够利用大规模异构集群实现海量轨迹数据的高效处理，对其在分布式环境下的存储与并行处理方法开展研究具有重要的科学意义。轨迹数据主体由移动对象的历史采样时空数据集构成，较一般数据类型具有存储成本高，时空分布不均且解析涉及大量几何运算等特点。采用一般基于“键值对”的横向划分机制来对轨迹数据进行分布存储，不仅会在并行查询中引入大量与结果无关的数据存取和解析代价，也会给时空连接、聚集等关键查询带来可观的数据划分、复制与传输开销。因此，本项目拟在扩展既有分布式数据存储平台的基础上，构建面向轨迹数据的垂直划分多级存储与索引机制，并对基于样本时空索引的非均质栅格划分方法和基于分布式操作代价模型的操作组织优化方法进行探索，以期构建一个切实可用的分布式轨迹数据处理平台，为后续研究创造良好条件，具有重要的理论意义和实用价值。

轨迹数据的分布式存储与关键查询优化项目，主要针对轨迹数据存储成本高、解析复杂和时空分布不均等特点，从基础的数据存储和具体的处理方法两个层面，开展数据分布式存储与关键查询优化方面的研究工作。项目主要的研究方向包括分布式环境下的轨迹数据存储与索引机制构建、分布式环境下的轨迹数据连接与聚集操作处理方法和复杂查询下的任务组织优化三个方面。项目研究提出了基于Hadoop平台的路网移动对象数据的分布式索引框架HINMO，达到了基于城市路网分布和轨迹数据时空密度的存储负载均衡目标。在此基础上，项目通过采用先分布式过滤，再进行二阶段传输与精化操作的分布式连接查询方法，减少了大规模集群环境下的空间连接查询过程中的非必要数据传输代价，提高了时间连接等关键复杂查询的处理性能。在此基础上，项目又进一步地利用网格划分和四叉树划分相结合的方式，提出了用于提升交通流数据聚类处理方法TDDDenStream，通过协调交通流数据的空间不均匀性和时间不均匀性，提升了交互过程中的轨迹数据概要处理能力。利用上述研究成果，项目构建了面向智慧城市建设的移动对象查询任务管理理论模型框架，并针对混合云环境下不同云服务商能够提供的云计算服务能力、数据访问安全性、可用服务资源数目等均存在差异的实际问题，提出了一种异构环境下基于预测的任务调度方法FEFT，通过提升对任务调度过程中对后续任务执行与通信效率的精度，来提升整体分布式处理任务的执行性能。除了上述研究内容外，项目还提出了一种云服务器性能评估模型CPE，以便为项目实施提供良好的平台支撑。项目还利用前期研究成果，开展了对路网环境下的Skyline查询方法展开研究，提出了基于查询基数的路网范围自适应限定方法和基于稀疏矩阵的去重估算等方法，通过限定支配集规模的方式来提升查询效率。研究工作自2017年1月开展至今，共发表论文10篇，其中EI检索5篇，SCI检索1篇；获发明专利授权3项，受理多项。协助培养博士生2名，硕士生3名，完成了项目设立的预期目标。