TMan: A High-Performance Trajectory Data Management System Based on Key-value

摘要: 轨迹数据的有效管理在很大程度上依赖于基本时空查询的效率。具有动态时空特性的轨迹数据激增，给管理带来了显著挑战。现有系统在提供细粒度轨迹表示和处理查询的高效架构方面存在不足，导致计算开销巨大。本文介绍了 TMan，以应对这些挑战。首先，TMan 提出了两种创新的索引结构，可精确捕捉轨迹数据的时空特征。与最先进的索引相比，我们用于时间范围和空间范围查询的索引可以分别减少高达 77% 和 83% 的检索次数。接下来，TMan 为这些索引设计了简洁有效的编码方法。利用这些索引，TMan 提供了一种分布式存储结构和索引缓存机制，用于有效管理键值数据存储中的轨迹。此外，TMan 还引入了一种并行查询处理方法，其中包含一种下推策略，以提高基本查询的效率。大量实验结果表明，TMan 的索引结构和架构优于基线。

Abstract: The effective management of trajectory data heavily relies on the utilization of fundamental spatio-temporal queries. The surge in trajectory data, with its dynamic spatio-temporal properties, poses notable management challenges. Existing systems are inadequate in providing fine-grained trajectory representations and efficient architecture for processing queries, leading to significant computational overhead. This paper introduces TMan to address these challenges. First, TMan presents two innovative index structures that precisely capture the spatio-temporal characteristics of trajectory data. Compared to the state-of-the-art indexes, our indexes for temporal range and spatial range queries can reduce the number of retrievals by up to 77% and 83%, respectively. Next, TMan devises concise and effective encoding methods for these indexes. Leveraging these indexes, TMan provides a distributed storage structure and an index caching mechanism for efficiently managing trajectories in key-value data stores. Moreover, TMan introduces a parallel query processing approach incorporating a push-down strategy to enhance the efficiency of fundamental queries. Extensive experimental results demonstrate that TMan’s index structures and architecture outperform the baselines.

Huajun He, Zihang Xu, Ruiyuan Li, Jie Bao, Tianrui Li, Yu Zheng. TMan: A High-Performance Trajectory Data Management System Based on Key-value Stores[C]//2024 IEEE 40th International Conference on Data Engineering (ICDE). IEEE, 2024.