首页|基于图数据库的路网时空轨迹建模和索引结构

基于图数据库的路网时空轨迹建模和索引结构

Network-Constrained Trajectory Modeling and Index Structure Based on a Graph Database

扫码查看
原文链接
  • NETL
  • NSTL
  • 万方数据
大数据时代的到来使得时空轨迹数据的规模和复杂度迅速增长,这对如何高效管理和查询时空轨迹数据提出了新的需求和挑战.图数据库在处理时空轨迹数据的建模、存储和管理方面具有独特优势.然而,随着路网时空轨迹数据规模的不断扩大,图数据库的查询性能也会随之下降.为应对这一挑战,本文提出了一种基于图数据库的路网时空轨迹建模与高效索引方法.该方法采用压缩线性参考(Compressed Linear Reference,CLR)模型对路网时空轨迹进行建模,并将其存储于图数据库中,在此基础上,进一步构建了一种高效的路网时空轨迹索引机制.该索引体系采用了三层时空索引结构,包括路网空间索引、时间索引和时空路径段索引.路网空间索引主要负责底层路段的高效检索,而时间索引与时空路径段索引则针对轨迹数据的时空特征进行精确定位和高效查询.该结构能够有效减少图数据库查询中节点的遍历,提高查询效率.此外,基于该索引结构的2种时空查询方法被开发以满足不同应用场景的需求.为验证所提出时空索引的有效性,本文基于人工合成的不同数量级路网时空轨迹数据进行了2种时空查询效率的对比.实验结果显示,本文提出的高效时空索引相比Nebula Graph原生图数据库索引,在时空窗口-时空路径相交查询中效率提升至少16.59倍,在时空路径-时空路径相交查询中效率提升至少2.74倍.这项研究为路网时空轨迹数据的高效管理和实时查询提供了新的解决方案,具有重要的理论和实际意义.
The rapid growth in the scale and complexity of spatiotemporal trajectory data in the era of big data presents significant challenges for efficient data management and querying.Graph databases,with their inherent advantages in modeling,storing,and managing complex relationships,have emerged as a powerful tool for handling spatiotemporal trajectory data.However,as the scale of road network spatiotemporal trajectory data continues to increase,the query performance of graph databases tends to decline due to the extensive node traversal required.To address this challenge,this paper proposes a novel method for road network spatiotemporal trajectory modeling and efficient indexing within a graph database framework.The proposed method employs the Compressed Linear Reference (CLR) model to represent road network spatiotemporal trajectories.This model is specifically designed to compress and streamline the representation of trajectory data,making it more manageable within large-scale datasets.The CLR model is implemented within a graph database,where a three-layer spatiotemporal indexing structure has been designed.This structure consists of three key components:a road network spatial index,a temporal index,and a spatiotemporal path segment index.The road network spatial index is used to index the underlying road network segments,while the temporal index and the spatiotemporal path segment index handle the temporal and combined spatiotemporal aspects of trajectory data.This integrated indexing structure is designed to minimize the need for extensive node traversal during query execution,significantly improving query efficiency.In addition to the indexing structure,two spatiotemporal query methods have been developed that leverage this efficient index.These methods are tailored to meet the requirements of different application scenarios,such as identifying intersections between spatiotemporal paths and performing spatiotemporal window queries to retrieve relevant trajectory segments.To validate the effectiveness of the proposed method,extensive experiments were conducted using artificially synthesized road network spatiotemporal trajectory data based on the road network of Wuhan.The Nebula Graph database was selected as the platform for managing and storing the spatiotemporal trajectory data,and the proposed indexing and query methods were implemented within this environment.The performance of our approach was tested across datasets of varying scales to evaluate scalability and efficiency.The experimental results demonstrated that the efficient spatiotemporal index significantly outperforms the native indexing mechanisms of Nebula Graph.Specifically,the method improved the performance of spatiotemporal window-path intersection queries by a factor of at least 16.59 and enhanced spatiotemporal path-path intersection queries by a factor of at least 2.74 compared to the baseline performance.These results highlight the substantial improvements in query performance achieved by this method.

network-constrained trajectoriesspatiotemporal data modelgraph databasecompressed linear reference modelspatiotemporal indexR-Tree indexspatiotemporal window-space-time path intersectionspace-time path-path intersection

张宇、陈碧宇、骆钰波、钟宇翔、李岩

展开 >

武汉大学测绘遥感信息工程国家重点实验室,武汉 430079

武汉大学社会地理计算联合研究中心,武汉 430079

路网时空轨迹 时空数据模型 图数据库 压缩线性参考模型 时空索引 R树索引 时空查询 时空窗口-时空路径相交 时空路径-时空路径相交

国家重点研发计划项目国家自然科学基金项目

2017YFB050360342271473

2024

10.12082/dqxxkx.2024.240349

地球信息科学学报
中国科学院地理科学与资源研究所

地球信息科学学报

CSTPCD北大核心
影响因子：1.004
ISSN：1560-8999
年,卷(期)：2024.26(10)