基于学习型空间编码和自适应形状编码的轨迹索引方法

本发明涉及轨迹管理，具体涉及基于学习型空间编码和自适应形状编码的轨迹索引方法。

背景技术：

1、随着移动设备、基于位置服务（location-based service，lbs）和物联网（internet of things，iot）系统的快速普及，轨迹已成为轨迹分析、路径预测、兴趣点发现、交通管理等时空应用的重要基础数据。在轨迹规模和重要性持续增长的背景下，如何支持高效的轨迹索引与查询已成为轨迹管理领域的重要研究问题。

2、键值（key-value，kv）存储具有高写入吞吐量、低访问延迟和良好的水平扩展能力，已成为大规模轨迹管理的重要技术架构。在基于kv存储的轨迹管理系统中，轨迹（或轨迹片段）通过键（key）进行索引，具体时空信息作为值（value）进行存储。查询处理通常表现为对键空间执行范围扫描，再对扫描得到的候选轨迹进行精确验证，因此键的设计直接决定查询效率。

3、目前主流的轨迹索引技术主要包括以下几类：

4、（1）基于固定空间填充曲线的轨迹索引技术。该类方法利用空间填充曲线（space-filling curve，sfc）将二维或多维空间映射到一维键空间，典型代表为xz2索引。如图1(a)所示，该方法首先对空间进行层次划分，然后根据预定义的sfc遍历顺序为每个空间单元分配编码。对于轨迹对象，则利用其最小外接矩形（minimum bounding rectangle，mbr）确定对应空间单元，采用该空间单元的编码作为轨迹的空间索引键。该类方法实现简单，能够支持基于键范围扫描的轨迹查询。

5、（2）基于形状增强编码的轨迹索引技术。为进一步提高过滤能力，部分研究在空间填充曲线基础上引入形状编码，如xz2+、xz*和tshape索引。该类方法首先确定轨迹对应的扩大元素（enlarged element，ee），然后将扩大元素划分为多个固定大小的子区域，并采用位图记录轨迹与各子区域之间的覆盖关系，从而生成形状编码。最终将空间填充曲线与形状编码组合形成轨迹键值，提供根据轨迹形状进行过滤的能力，以降低查询开销。

6、（3）基于学习型空间填充曲线的索引技术。部分研究开始利用机器学习技术优化sfc的遍历顺序，如bmtree以及lmsfc方法。该类方法根据历史查询访问模式或数据分布信息，学习空间单元之间的排列顺序，进而提高轨迹键分布的连续性，来减少查询扫描范围。与固定sfc相比，学习型sfc能够在特定数据集或特定查询负载下获得更好的查询性能。

7、如图1所示，虽然现有技术在一定程度上提高了轨迹查询效率，但仍存在如下缺陷：

8、（1）编码空间固定，键空间利用率较低：现有sfc索引方法通常对整个空间范围内的所有单元格进行编码，而不考虑轨迹的实际分布情况。在真实轨迹中，大量单元格（图1(b)中的灰色单元）仅包含极少量轨迹甚至不包含任何轨迹，但这些低密度单元格仍然被分配编码并占据键空间位置。这些低密度单元格穿插于高密度单元格之间，导致原本相邻或相关的轨迹被映射到彼此分离的键区间。当查询区域覆盖多个高密度区域时，系统仍需要扫描大量与查询无关的键区间，从而增加扫描次数和访问开销，降低查询效率。

9、（2）遍历顺序固定，键分布连续性不足：对于xz-order等传统sfc，其空间单元遍历顺序完全由预定义规则决定，无法根据轨迹分布特征和实际查询模式进行调整。即使两个空间区域在查询过程中经常被同时访问，其对应编码仍可能相距较远（图1(b)中的单元格a,b,c）。对于现有学习型sfc方法，虽然能够利用历史工作负载学习编码顺序，但主要针对静态查询负载优化，未充分结合轨迹空间分布特征进行联合建模，不具备泛化性，当轨迹分布发生变化或查询模式变化时，学习得到的遍历顺序容易失效。这导致查询区域被拆分成多个离散键区间，增加范围扫描次数，从而影响查询性能。

10、（3）形状编码粒度固定，难以适配分布差异：现有形状增强编码方法通常采用固定大小的划分方案，例如统一采用2×2、3×3或4×4网格对扩展元素进行划分。该类方法未考虑不同空间区域内轨迹分布特征的差异。如图1(c)所示，对于轨迹分布较为简单、差异明显的区域，过细的划分会产生大量冗余编码信息，增加键长度和存储开销；而对于轨迹分布复杂、形态相近的区域，过粗的划分又难以有效区分不同轨迹，导致过滤能力下降。因此，固定粒度的形状编码难以同时兼顾编码紧凑性与轨迹区分能力，限制了整体查询性能的提升。

技术实现思路

1、针对上述现有技术的不足，本发明所要解决的技术问题是：如何提供基于学习型空间编码和自适应形状编码的轨迹索引方法，通过识别并裁剪低密度空间单元来减少码空间中的冗余区域，提高编码空间利用率；基于强化学习构建空间填充曲线，使空间邻近且经常被共同访问的区域在一维键空间中保持邻近，减少离散扫描区间数量，提高查询扫描局部性；通过自适应形状编码能够根据局部轨迹分布特征动态选择空间划分粒度，增强查询过滤效果，减少无用的空间相交判断开销，提高查询效率。

2、为了解决上述技术问题，本发明采用了如下的技术方案：

3、基于学习型空间编码和自适应形状编码的轨迹索引方法，包括：

4、s1：获取待存储的轨迹数据，并提取各轨迹对应的轨迹标识和分片数量；

5、s2：对原始空间进行划分构建四叉树空间层次结构，并将各轨迹分配到对应的单元格内，生成初始四叉树结构；

6、s3：根据预设密度阈值对初始四叉树结构的低密度单元格进行识别和裁剪，生成紧凑四叉树结构；

7、s4：利用强化学习算法学习单元格的遍历顺序，生成适应轨迹分布和查询工作负载特征的学习型空间填充曲线，并基于学习型空间填充曲线生成各轨迹的空间编码；

8、s5：根据各单元格内部轨迹分布特征，自适应选择扩大元素的划分粒度，并生成各轨迹的形状编码；

9、s6：通过各轨迹的空间编码和形状编码结合对应的轨迹标识和分片数量生成各轨迹的索引键，并存储各轨迹的索引键。

10、具体来说，步骤s2中，生成初始四叉树结构的处理步骤包括：

11、s201：将基于四叉树组织的原始空间作为根节点；

12、s202：从根节点开始，采用递归划分方式将每个空间区域均匀划分为四个子区域，直至达到预设的最大划分次数；

13、s203：将每个划分后的子区域作为单元格，每个单元格对应于四叉树中的一个节点；

14、s204：根据分配规则将各轨迹分配到唯一的单元格中，生成初始四叉树结构；

15、其中分配规则为：轨迹的最小外接矩形的左下角位于单元格对应的空间区域内，且单元格的扩大元素覆盖该轨迹的最小外接矩形。

16、具体来说，步骤s3中，生成紧凑四叉树结构的处理步骤包括：

17、s301：获取预设的轨迹密度阈；

18、s302：采用自底向上的顺序遍历方式访问初始四叉树结构；

19、s303：对于当前访问的单元格，若单元格包含的轨迹数量小于预设的轨迹密度阈值，则判定为低密度空间单元；

20、s304：将低密度单元格及其子树中的所有轨迹重新分配到其最近的、满足保留条件的祖先节点中，并从初始四叉树结构中删除该低密度空间单元；

21、s305：重复步骤s303至s304，直至完成初始四叉树结构的遍历，生成紧凑四叉树结构。

22、具体来说，步骤s4中，生成学习型空间填充曲线的处理步骤包括：

23、s401：基于强化学习框架构建强化学习模型，定义状态空间、动作空间及奖励函数，并初始化策略网络和价值网络；

24、s402：在每轮训练开始时，随机选择紧凑四叉树中的单元格作为遍历序列的起始单元格，并将其标记为已访问；

25、s403：根据当前遍历状态为当前单元格构建状态向量，并将状态向量输入策略网络；状态向量包括轨迹分布特征、四叉树结构特征、空间位置特征以及遍历上下文特征；

26、其中：

27、轨迹分布特征用于描述当前单元格及其扩大元素的轨迹分布情况；

28、四叉树结构特征用于描述当前单元格在紧凑四叉树中的结构位置，包括单元格所在层级以及从根节点到当前节点的层次路径信息；

29、空间位置特征用于描述当前单元格与周围轨迹分布之间的空间邻近关系；

30、遍历上下文特征用于描述当前遍历过程的动态状态，包括当前已访问单元格占全部单元格的比例、当前单元格与上一访问单元格之间的距离以及邻域单元格的密度统计信息；

31、s404：策略网络根据当前状态向量计算候选动作集合中各动作的选择概率，并按照所述概率选择下一待访问单元格；

32、s405：将所选择的下一待访问单元格追加至当前遍历序列末尾，并更新访问状态；根据当前动作产生的遍历结果计算对应的局部奖励；

33、s406：当完成一轮遍历并生成完整遍历序列后，根据所生成学习型空间填充曲线的整体质量计算全局奖励；

34、s407：基于当前遍历过程中获得的局部奖励和全局奖励，采用强化学习算法（ppo）更新策略网络和价值网络的参数；

35、s408：重复执行s402至s407，迭代训练策略网络和价值网络，直至收敛或达到预设的训练轮次；

36、s409：训练完成后，利用训练得到的策略网络，根据各单元格的状态依次选择下一待访问单元格，生成紧凑四叉树对应的学习型空间填充曲线。

37、具体来说，步骤s403中，候选动作集合为当前单元格的局部邻域单元格，包括：

38、（1）同层邻域单元格，与当前单元格位于同一四叉树层级且空间位置相邻的单元格；

39、（2）跨层邻域单元格，当前单元格的祖先节点以及子节点。

40、具体来说，步骤s405中，局部奖励的计算公式为：

41、；

42、；

43、；

44、式中：为局部奖励；为空间邻近度奖励，为当前单元格，为下一个要访问的保留单元格；为轨迹相似度奖励；为单元格和中心点的距离，为归一化所使用的最大距离；为单元格所关联的轨迹集合；为单元格所关联的轨迹集合。

45、具体来说，步骤s406中，全局奖励的计算公式为：

46、；

47、；

48、式中：为全局奖励；、为遍历顺序的凝聚度，为给定查询工作负载，为当前学习到的遍历顺序，为作为基准的遍历顺序；为查询产生的扫描区间数量；为相邻扫描区间之间的间隔占总间隔的比例。

49、具体来说，步骤s5中，生成形状编码的处理步骤包括：

50、s501：对于紧凑四叉树结构中的当前单元格，构建其对应的扩大元素；

51、s502：在扩大元素内枚举若干候选网格划分方案；

52、s503：对于每个候选网格划分方案，计算基于网格利用率和轨迹区分度的综合评价得分；

53、s504：选择综合评价得分最高的候选网格划分方案作为最优划分方案；

54、s505：按照最优划分方案将当前单元格的扩大元素进一步划分为若干个子网格，根据轨迹覆盖子网格的情况生成位串作为轨迹的形状编码，并以整数编码的形式存储。

55、具体来说，步骤s503中，计算候选网格划分方案综合评价得分的处理步骤包括：

56、s5031：计算当前单元格c的候选网格划分方案的网格利用率；

57、计算公式为：

58、；

59、式中：为被至少一条轨迹经过的子网格数量；为候选网格划分方案，和分别表示横向和纵向划分数量；

60、s5032：计算当前单元格c的候选网格划分方案的轨迹区分度；

61、计算公式为：

62、；

63、；

64、式中：为根据轨迹覆盖的子网格生成对应的形状编码；为任意两条轨迹和编码之间的汉明距离；为归一化汉明距离；设当前单元格c中包含轨迹集合，其轨迹对总数为；

65、s5033：基于候选网格划分方案的网格利用率和轨迹区分度计算综合评价得分；

66、计算公式为：

67、。

68、具体来说，步骤s6中，生成轨迹索引键的处理步骤包括：

69、s601：获取轨迹的空间编码和形状编码；

70、s602：获取单元格对应扩大元素中形状编码对应的整数编码；

71、s603：将轨迹的空间编码和整数编码组合成轨迹编码；

72、计算公式为：

73、；

74、式中：为预留的左移位数，用于保证所有扩大元素内的形状编码值不会重叠；

75、s603：将轨迹编码与分片数量和轨迹id拼接，生成轨迹的索引键；

76、计算公式为：

77、；

78、式中：为分片数量；为轨迹id；为拼接操作。

79、本发明中基于学习型空间编码和自适应形状编码的轨迹索引方法与现有技术相比，具有如下有益效果：

80、（1）本发明通过对传统四叉树进行剪枝，保留高密度的空间单元格，减少低密度区域对索引结构的影响，在保证空间表达能力的同时降低索引规模和查询开销。

81、（2）本发明将空间填充曲线构建过程建模为马尔可夫决策过程，通过强化学习自动学习空间单元的遍历顺序，生成能够适应轨迹分布特征和查询访问模式的学习型空间填充曲线，提高键空间局部性并减少查询扫描区间数量。

82、（3）本发明构建结合局部奖励和全局奖励的强化学习奖励机制，其中局部奖励反映相邻单元格之间的空间邻近性和轨迹相似性，全局奖励反映查询扫描区间的连续性与局部性，从而引导模型生成更有利于查询处理的空间填充曲线。

83、（4）本发明根据局部轨迹分布特征自动选择形状划分方案，并综合考虑空间利用率和轨迹区分能力确定最优划分结构，从而在控制编码长度的同时提高轨迹形状过滤能力。

84、（5）本发明将学习型空间填充曲线生成的空间编码与自适应形状编码共同构成轨迹键，实现轨迹数据在键值存储系统中的高效组织与快速查询。