Abstract: With the development of mobile terminal positioning technology, the scale of trajectory data has increased dramatically. The storage and rapid query of massive trajectory data have become research hotspots. The distributed framework can provide efficient data processing capabilities. This paper first proposes a local trajectory index TRindex, which effectively preserves the proximity of temporal and spatial data and supports spatiotemporal queries. This paper also designs a multi-layer range circle mapping method in TRindex, maps the spatial minimum bounding rectangle (MBR) to a one-dimensional axis, establishes an order of the distance from the trajectory to the center of the range circle, and builds a spatial range tree based on this order. This design ensures spatial proximity, providing spatial proximity for range queries. It also forms an ordered relationship between the distances from trajectories to reference points, enabling efficient pruning of K-nearest neighbor queries and effectively reducing the problem of duplicate calculations in K-nearest neighbor queries. Finally, based on TRindex, this paper constructs a distributed trajectory index (DTRindex), which consists of three main components: data partitioning, local indexing, and global indexing. The global index is a modified R*-tree with a Bloom filter applied to each node, effectively improving query efficiency.The DTRindex effectively supports three spatiotemporal query algorithms: spatiotemporal range queries, K-nearest neighbor queries, and mobile object trajectory queries. Finally, the Hadoop-based distributed trajectory index HadoopTrajectory, the single-machine index PM-tree, and the NoSQL-based distributed trajectory index TMan were selected as experimental counterparts for comparison. Through simulation experiments, DTRindex has been demonstrated to exhibit superior performance across multiple metrics: in spatio-temporal range query efficiency, it achieves average improvements of approximately 57%, 74%, and 25% compared to HadoopTrajectory, PM-tree, and TMan respectively; For k-nearest neighbour queries, performance improved by 40%, 48%, and 20% on average; for mobile object trajectory queries, efficiency increased by 50%, 53%, and 30%. Furthermore, ablation experiments validated the effectiveness of each core module. The spatial range tree layer contributed most significantly, achieving an overall average performance improvement of 2.5times. The temporal index layer contributed secondarily, yielding an average performance improvement of 1.2 times. The moving object double linked list contributed approximately 90% to the average performance improvement, making its contribution most substantial in moving object trajectory queries, where efficiency increased nearly fourfold.

摘要： 随着移动终端定位技术发展，轨迹数据规模剧增，海量轨迹数据存储与快速查询成研究热点。分布式框架能提供高效数据处理能力。本文首先提出了局部轨迹索引TRindex，该索引很好地保持了时间和空间数据的近邻性，支持时空查询。TRindex中设计了多层范围圆映射方法，将空间最小边界矩形（MBR）映射到一维轴上，建立了轨迹到范围圆圆心的距离的序，并根据这个序建立了空间范围树。该设计保证了空间的邻近性，为范围查询提供空间临近性；同时又形成了轨迹到参考点距离的有序关系，能实现K近邻查询的有效剪枝并能有效地减少了K近邻查询重复计算的问题。最后基于TRindex本文构建了分布式轨迹索引DTRindex，主要分为数据分区、局部索引、全局索引三部分。全局索引为改进的R*-tree，并针对每个节点设置布隆过滤器，有效地提高了查询的效率。DTRindex索引能同时有效地支持三种时空查询算法：时空范围查询、K近邻查询和移动对象轨迹查询。最后，选取了同样基于Hadoop框架的分布式轨迹索引HadoopTrajectory、单机式索引PM-tree和基于NoSQL数据库的分布式轨迹索引TMan作为实验对照对象.通过实验对比，证实了DTRindex在多项性能上表现优异：在时空范围查询效率上，相较于HadoopTrajectory、PM-tree和TMan，DTRindex分别平均提升了约57%、74%和25%；在K近邻查询上，性能平均提升了40%、48%和20%；在移动对象轨迹查询上，效率提升了50%、53%和30%。此外，消融实验验证了各核心模块的有效性，空间范围树层贡献最大，使得整体平均性能提升2.5倍，时序索引层贡献次之，平均性能提升1.2倍，移动对象双链表使得平均性能提升约90%，在移动对象轨迹查询中贡献最大，效率提升将近4倍。