基于二级时空分桶的伴随轨迹查询  

Accompanying Trajectory Query Based on Secondary Temporal and Spatial Indexing

作　　者：王晨旭 汪谨权[1] 杨鑫 WANG Chen-Xu;WANG Jin-Quan;YANG Xin(School of Software Engineering,Xi'an Jiaotong University,Xi'an 710049;Ministry of Education Key Lab of Intelligent Network and Network Security,Xi'an Jiaotong University,Xi'an 710049)

机构地区：[1]西安交通大学软件学院,西安710049 [2]西安交通大学智能网络与网络安全教育部重点实验室,西安710049

出　　处：《计算机学报》2024年第1期131-147,共17页Chinese Journal of Computers

基　　金：国家自然科学基金(62272379);陕西省自然科学基金(2021JM-018);国家重点研发计划(2021YFB1715600);中央高校基本科研业务费(xzy012023068)资助。

摘　　要：随着移动传感器设备的普及,人们能够采集到的位置数据越来越多,轨迹数据的规模也越来越庞大.从大规模时空数据中查找与指定轨迹最相似的前k条轨迹一直是时空大数据挖掘的重要挑战之一.现有的相似轨迹查询方法大都包括三个阶段:(1)对海量的离线轨迹数据建立索引;(2)基于索引结构从已知轨迹集中查询与指定轨迹相似的候选轨迹;(3)计算指定轨迹与候选轨迹之间的精确相似度并返回相似度最大的前k条轨迹.但大多数现有方法对轨迹进行聚类索引时不能有效利用时间和空间信息,导致时间相似度不高的轨迹也会被划分到相同的索引项上,最终影响查询的准确性和效率.此外,现有的时空轨迹相似度计算方法存在大量的无效运算,使得相似轨迹的查询效率整体较低.针对当前伴随轨迹查询方法对时间与空间信息利用不充分的问题,本文提出一种新的二级时空分桶索引结构,首先将每条轨迹数据按照时间滑动窗口划分为若干带有时间槽信息的子轨迹,在时间上对轨迹进行一级索引聚类;在此基础上对在相同时间槽内的子轨迹进行二级空间索引聚类,利用哈希算法将具有连续相同位置点的子轨迹映射到同一时空分桶中.与已有索引方法相比,该方法对不同轨迹在索引时具有更好的区分度,查询时的筛选条件更为严格,有效降低了候选轨迹集的规模.针对现有轨迹相似度计算方法效率低下的问题,提出一种基于时差约束的轨迹相似度计算方法.利用轨迹之间的时差排除大量不必要的位置比较运算,将轨迹相似度的计算复杂度控制在线性级别,大大提高了计算效率,同时为过滤伴随轨迹查询过程中的无效计算,对基于时差约束的轨迹相似度计算方法进行变体得到一种上下界过滤方法,最大限度地避免了无效计算.最后,在4个真实的大规模轨迹数据集上对所提方法进行实验�With the proliferation of mobile sensor devices,an increasing amount of position data is being collected,and the scale of trajectory data also grows rapidly.It has always been a challenge to find the top-k trajectories most similar to a given query trajectory from massive spatial-temporal data.Existing trajectory-query methods comprises three main stages:(1)offline trajectory indexing on a massive dataset,(2)searching for candidate trajectories similar to the query trajectory based on the indexed structure,and(3)computing the precise similarity between the query trajectory and candidate trajectories,and returning the top-k most similar trajectories.However,most existing methods fail to effectively exploit the temporal and spatial information during trajectory clustering indexing,Trajectories with low temporal similarity are mistakenly partitioned into the same index,degrading query accuracy and efficiency.Furthermore,existing spatial-temporal trajectory similarity-calculation methods involve numerous unnecessary operations,resulting in low query efficiency.To address these issues,this paper proposes a novel secondary trajectory index structure.Firstly,a trajectory is divided into sub-trajectories by a sliding time window.Then,sub-trajectories are clustered for first-level indexing based on their time slots.Then,sub-trajectories within the same time slot are grouped into second-level spatial clusters.Sub-trajectories with continuous identical locations are partitioned into the same spatial-temporal bucket by a hash algorithm.Compared to existing indexing methods,this approach provides better distinction between different trajectories during indexing,resulting in more strict filtering conditions in the query process,reducing the size of the candidate trajectory set.To tackle the computational efficiency problem of existing trajectory similarity calculation methods,we propose a trajectory similarity calculation method based on the constraints of time difference,eliminating many unnec-essary location comparisons and

关 键 词：二级时空索引 轨迹相似度计算 伴随轨迹查询 

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