Journal of Geo-information Science >
Adaptive Data Model and Index Structure for Network-constrained Trajectories
Received date: 2022-04-02
Revised date: 2022-04-29
Online published: 2023-03-25
Supported by
National Key Research and Development Program of China(2021YFB3900900)
Natural Science Foundation of Hubei Province of China(2020CFA054)
The State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing Special Research Funding
An adaptive spatiotemporal data model and a spatiotemporal index structure are proposed to support efficient storage and querying of network-constrained trajectories. The proposed adaptive spatiotemporal data model extends the hierarchical Compressed Linear Reference (CLR) data model by establishing the adaptive route-based linear datum in road network with high-frequency network routes mined from the trajectory dataset. Network-constrained trajectories can be transformed from the link-based linear datum to the adaptive route-based linear datum, and the transformed trajectories consist of fewer sub-entities that can be stored with lower storage capacity. The proposed adaptive spatiotemporal index structure is an extension of the LRS-based index structure, which is constructed based on the adaptive route-based Linear Reference System (LRS). Fewer spatiotemporal sub-entities are saved in the adaptive spatiotemporal index structure, which allows for efficient spatiotemporal querying of network-constrained trajectories. In order to verify the effectiveness of the proposed adaptive data model and index structure, adequate experiments are conducted at the end of this paper using the real open-source T-Drive taxi trajectory dataset and the synthetic trajectory dataset. The experiments take two popular spatiotemporal intersection queries as an example, and the proposed adaptive data model and index structure with the conventional hierarchical CLR data model and the LRS-based spatiotemporal index structure are compared in terms of storage efficiency and query efficiency. The analysis results show that the proposed adaptive data model and index structure can improve storage efficiency by 40% and query efficiency by 50%, which confirms that the proposed method can provide a new solution for the management of network-constrained trajectory data.
LUO Yubo , CHEN Biyu . Adaptive Data Model and Index Structure for Network-constrained Trajectories[J]. Journal of Geo-information Science, 2023 , 25(1) : 63 -76 . DOI: 10.12082/dqxxkx.2023.220145
表1 实验数据说明Tab. 1 Description of trajectory data |
数据来源 | 数据名称 | 空间路径数量/N | 时空轨迹数量/个 | 时间段 |
---|---|---|---|---|
T-Drive数据集 | TD | - | 16 192 | 18:00 — 18:30 |
人工合成数据集 | AD1 | 10 | 20 000 | 18:00 — |
AD2 | 5000 | 20 000 | 18:00 — | |
AD3 | 10 000 | 20 000 | 18:00 — | |
AD4 | 15 000 | 20 000 | 18:00 — | |
AD5 | 50 000 | 20 000 | 18:00 — |
表2 AD数据集在不同时空索引结构下时空窗口-时空路径相交查询效率对比Tab. 2 Comparison of query efficiency of spatiotemporal window-path intersection query for AD dataset under different spatiotemporal index structures |
数据集 | 基于路段的 时空索引结构 | 基于街道的 时空索引结构 | 自适应 时空索引结构 | |||||||
---|---|---|---|---|---|---|---|---|---|---|
时空路径 子实体数量/个 | 搜索次数/次 | 时空路径 子实体数量/个 | 搜索次数/次 | 时空路径 子实体数量 | 搜索次数/次 | |||||
AD1 | 1 125 037 | 415 | 670 589 | 232 | 218 220 | 19 | ||||
AD2 | 1 060 371 | 9246 | 672 471 | 5424 | 317 440 | 3158 | ||||
AD3 | 1 057 270 | 10 149 | 669 139 | 5883 | 321 793 | 3893 | ||||
AD4 | 1 058 169 | 10 280 | 671 203 | 5925 | 322 768 | 4089 | ||||
AD5 | 1 055 623 | 10 409 | 670 116 | 5993 | 338 253 | 4301 |
[1] |
|
[2] |
刘经南, 方媛, 郭迟, 等. 位置大数据的分析处理研究进展[J]. 武汉大学学报·信息科学版, 2014, 39(4):379-385.
[
|
[3] |
龚健雅, 黄文哲, 陈泽强, 等. 全球位置信息叠加协议与位置服务网技术研究进展与展望[J]. 地球信息科学学报, 2022, 24(1):2-16.
[
|
[4] |
|
[5] |
|
[6] |
|
[7] |
陆锋, 刘康, 陈洁. 大数据时代的人类移动性研究[J]. 地球信息科学学报, 2014, 16(5):665-672.
[
|
[8] |
吴华意, 黄蕊, 游兰, 等. 出租车轨迹数据挖掘进展[J]. 测绘学报, 2019, 48(11):1341-1356.
[
|
[9] |
|
[10] |
|
[11] |
|
[12] |
|
[13] |
|
[14] |
|
[15] |
陈碧宇, 陈晓玲, 陈慧萍, 等. 网络中移动对象的2维时空数据模型[J]. 测绘学报, 2007, 36(3):329-334.
[
|
[16] |
|
[17] |
|
[18] |
|
[19] |
|
[20] |
|
[21] |
李国徽, 钟细亚. 一种基于固定网络的移动对象运动轨迹索引模型[J]. 计算机研究与发展, 2006, 43(5):828-833.
[
|
[22] |
李红军, 唐常杰, 乔少杰, 等. UTR*-Tree受限网络中移动对象不确定轨迹索引模型[J]. 四川大学学报·工程科学版, 2010, 42(2):118-125.
[
|
[23] |
林许, 李清泉, 杨必胜. 一种基于道路网的移动对象的位置索引与邻近查询方法[J]. 测绘学报, 2010, 39(3):316-327.
[
|
[24] |
丁治明. 一种适合于频繁位置更新的网络受限移动对象轨迹索引[J]. 计算机学报, 2012, 35(7):1448-1461.
[
|
[25] |
|
[26] |
|
[27] |
|
[28] |
|
[29] |
|
[30] |
|
[31] |
|
[32] |
|
[33] |
|
[34] |
|
[35] |
|
/
〈 | 〉 |