大规模时空轨迹数据连接查询效率优化实践

本文提出一种低集群计算资源条件下, 大规模轨迹类数据同时空关系的快速连接查询算法DPCP-CROSS-JOIN. 该算法通过对轨迹数据时间字段进行分段交叉编码和位置网格化等方式对连续的轨迹数据离散化, 并以日期和网格区域编码进行两级分区存储. 通过交叉“等值”连接查询, 实现时空连接查询的三级索引、四级加速, 将$n\cdot n $对象间同时空关系连接查询时间复杂度从O(n²)降为O(nlogn). 在Hadoop集群上使用Hive和TEZ等进行大规模轨迹数据连接查询时能将连接查询效率最高提升到30.66倍. 该算法以时间段编码作为关联条件, 巧妙绕开连接过程中复杂表达式的实时计算, 以“等值”替代复杂表达式计算连接, 提高MapReduce任务并行度, 提升集群存储和计算资源利用率. 在面对仅使用一般优化已几乎无法完成的, 更大规模类似任务, 仍能在数分钟内完成. 实验表明, 该算法具有高效和稳定等特性, 尤其适用低“算力”资源条件下大规模轨迹数据的同时空关系连接查询. 此方法还可作为时空轨迹伴随查找, 对象间关系亲密度判定等的原子算法, 可广泛应用于维护国家安全、社会治安秩序, 预防和打击犯罪, 辅助城乡规划统筹等领域.