路网时窗排序的回归模型树轨迹索引  

Trajectory Index of Regression Model Tree Based on Road-segment and Time-window Ordering

作　　者：韩京宇[1,2] 陆维 武凡 刘阳 葛康 朱曼 陈伟 HAN Jing-yu;LU Wei;WU Fan;LIU Yang;GE Kang;ZHU Man;CHEN Wei(School of Computer Science and Technology,Nanjing University of Posts and Telecommunications,Nanjing 210023,China;Jiangsu Key Laboratory of Big Data Security and Intelligent Processing,Nanjing 210023,China)

机构地区：[1]南京邮电大学计算机学院,南京210023 [2]江苏省大数据安全与智能处理重点实验室,南京210023

出　　处：《小型微型计算机系统》2022年第6期1245-1253,共9页Journal of Chinese Computer Systems

基　　金：国家重点研发计划项目(2019YFB2101704)资助.

摘　　要：最近,通过学习型索引取代传统索引以减少索引大小和提高查询效率受到广泛关注.轨迹点在路网和时间维度的连续性难以刻画,数据分布倾斜普遍存在,现存的学习型索引不能有效地支持其查询.提出一种基于路网时窗排序的回归模型树,以支持点和范围查询,含数据排序和模型训练两个阶段:首先,结合希尔伯特曲线和模拟退火寻找保持道路临近性的路段排序,进而采用两层划分获取轨迹点的一维排序,保证时空近邻点排序后彼此靠近;其次,引入回归模型树映射轨迹点和存储位置,提出批量加载和周期更新两种训练模式.真实和模拟数据集上的实验表明,在保证和传统索引可比的查询性能前提下,大幅度降低索引大小,有效地支持以读为主的历史轨迹数据查询.Recent work on learned index has attracted the community's attention,which replaces the conventional index with a learned model to reduce the storage cost and improve the query performance.Due to the difficulty in describing the continuity of the road-segment and time-window space and the distribution skew of trajectory data,the existing learned indexes cannot effectively cope with this.We propose a Regression Model Tree(RTM)based on the ordering in road-segment and time-window space,so as to support the point query and range query,which consists of two stages,data ordering and model training.Firstly,we find the proximity-preserved ordering of road segments using the Hilbert curve numbers optimized by the simulated annealing,and then determine the one-dimensional order of trajectory points by partitioning them with a two-level hierarchy,thus ensuring the proximity of the points which are near to each other in the original segment-time space.Secondly,we introduce the regression model tree to map trajectory points to the storage positions,and propose the batch loading and period updating modes to train the prediction models.The experimental result on real and synthetic datasets shows that our method greatly reduces the storage cost while keeping the query performance comparable to the conventional index,thus supporting the read-only requirement of history trajectory query.

关 键 词：轨迹点 学习型索引 点查询 回归模型树 希尔伯特 模拟退火 

分 类 号：TP392[自动化与计算机技术—计算机应用技术]