在这个时代，有一种数据类型因其具有的独特的价值和面临的挑战而备受关注——那就是轨迹数据。想象一下，每天有成千上万的物流车辆在城市中穿梭，每一辆都在生成大量的移动轨迹。这些数据不仅蕴含着巨大的商业潜力，也是智慧城市建设不可或缺的一环。然而，如何有效管理和查询这些海量的轨迹数据，成为了一个亟待解决的问题。本次为大家带来数据库领域顶级会议ICDE 2024的文章《TMan: A High-Performance Trajectory Data Management System Based on Key-value Store》
一. 背景
随着全球定位系统（GPS）及其他定位技术的日益普及，轨迹数据的应用呈现出爆炸性增长。以京东物流为例，其60,000名快递员每天产生的轨迹日志超过1TB。这一现象凸显了对高效管理系统的迫切需求，以便处理和维护如此庞大的轨迹数据集。尽管键值数据存储因其可扩展性和快速数据检索能力而成为处理大规模数据的常用选择，但它们在轨迹数据管理方面仍面临重大挑战。一方面，轨迹数据的复杂结构缺乏精细的表示方法；另一方面，应用程序需求的查询场景多种多样，要求系统能够灵活且有效地支持各类查询。因此，开发一个能够精确表示轨迹数据并可以高效处理复杂查询的系统变得尤为重要。
为了解决上述两个要求，论文提出了四种新颖的索引结构和编码方法，将轨迹的时空特征精确地转换为一维值并设计了存储方案、索引缓存机制和相应的查询处理技术来支持轨迹查询。
二. 方法介绍
2.1 总体框架
图1 TMan的整体架构
• 存储层（Storage Layer）：TMan系统采用主表和辅助表来适应多样化的查询需求，并最小化冗余存储。 键值数据库通过一维键值对存储数据，而轨迹查询的效率很大程度上取决于将轨迹的时空特征精确转换为一维编码。为此，TMan引入了四个索引来准确表示轨迹特征，并在编码过程中保留这些时空特征。轨迹数据存储在主表中，而其他索引到主表的映射则存储在辅助表中。考虑到轨迹由多个点组成，且连续点通常具有相似特征，TMan利用无损压缩技术将轨迹压缩成字节。同时，采用dp特征保留轨迹的代表性特征。此外，TMan集成了索引缓存机制，以提升查询处理效率。
• 查询处理层（Query Processing）：TMan提供高效的查询处理能力，能够支持各种基础查询，如空间范围查询、ID时间范围查询、时空范围查询和相似性查询。接收到查询后，系统会基于规则的优化器（RBO）和基于成本的优化器（CBO）生成最佳查询计划。随后，TMan将过滤器下推到相关表区域，并并行执行查询，以提高处理效率。
2.2 索引和编码
2.2.1 TR索引和编码
时间范围查询（TRQ）是检索与特定时间范围相交的所有轨迹的关键操作，这在多个领域内至关重要，比如分析物体在特定时间段内的运动模式。TR索引的设计宗旨是高效地支持此类查询。对于轨迹T，其起点和终点时间范围用[ts, te]表示。
TR的索引结构：
在继续介绍之前会先给出定义：
定义1.（TP：时间段）。TR索引将时间线按固定长度划分为相邻且不重叠的时间段。论文用TPi表示第i个时间段。
定义2.（TB：时间箱）。TBi,j是从第i个时间段开始到第j个时间段结束的时间箱。注意，i ≤ j。
TR索引的目的在于：1）采用精细的时间箱来表示轨迹的时间范围；2）对这些时间箱进行编码，以便将近邻时间范围的轨迹进行有效分区。
TR索引的索引结构基于将较短的时间周期组合成一个索引空间的设计理念。时间线被划分为具有固定时长（例如，一小时）的连续且不重叠的时间周期。对于给定的时间范围T.tr = [ts, te]，ts和te分别位于第i个和第j个时间周期。因此，TR索引使用从第i个到第j个时间周期的时间箱来表示T.tr。如图2所示，TR索引利用(j - i + 1)个时间周期构成的时间箱来表示T.tr的时间范围。这种设计使得TR索引能够有效地处理时间范围查询，同时保持编码的简洁性和高效性。
图2 TR索引的示例
TR索引的编码：键值数据存储使用键值对的形式来存储数据。因此，为每个时间箱(bin)分配一个唯一的整数值。编码的目标是为相邻时间范围的轨迹分配尽可能接近的索引值。这种编码方式旨在确保时间箱的索引值不仅唯一，同时能够反映出时间箱之间的邻近关系。通过这种方式，TR索引能够有效地支持时间范围查询，同时保持数据存储的紧凑性和查询效率。
由于时间是无限的，TMan将时间线的起始时间设定为UNIX系统的时间起点，即1970年1月1日00:00:00。TMan设定N为时间箱覆盖的最大周期数，以限制编码空间。对于时间箱TBi,j，TMan有i ≤ j ≤ i + N − 1。实际上，经过预处理后，几乎所有轨迹的时间范围都不会超过48小时。因此，如果时间段为1小时，则N不需要超过48。用户也可以根据需要配置N以增加灵活性。
对于时间范围查询q，如果时间段TPi与q相交，则所有从TPi开始的时间箱TB = {TBi,k|i ≤ k ≤ i + N − 1}都与q相交，因此TB是q的候选项。因此，TMan首先对从同一时间段TPi开始的时间箱进行编码，然后对从下一个时间段TPi+1开始的时间箱进行编码，可以得出时间箱TBi,j的索引值如下所示：
TR(TBi, j) = i ∗ N + j – i
2.2.2 TShape索引
轨迹由一系列连续的时空点组成，这些点形成了不规则的空间形状，而不规则的空间形状不利于查询，鉴于此，文章提出了TShape索引技术，它分配最合适的一维索引值来表征轨迹的几何形状。
TShape索引的空间结构：
同样的，在继续介绍之前会先给出定义：
定义3(Cell，𝑐：单元格). 单元格被用于将空间均匀划分为不同的区域，以便有效的对空间数据进行组织和查询。通过四叉树规则，一个单元格可以递归地被划分为四个子单元格，从而实现单元格的分层表示。
定义4(Resolution，𝑟：分辨率). 将初始单元格的分辨率设定为0，在每次递归划分 过程中，子单元格的分辨率将相应地提升1。
定义5(EnlargedElement，𝐸(𝑐)：放大元素). 放大元素由𝛼∗𝛽个在空间上相邻且连续的单元格构成。每个放大元素最左下角的单元格不同。因此，放大元素可以被视 作以左下角单元格为起点，向右上角方向扩展至𝛼∗𝛽个单元格的区域。为便于编码，在后续的使用中，文章使用𝐸(𝑐)来表示以单元格𝑐为左下角的放大元素。
定义6(IndexSpace，𝐼𝑆：索引空间). 放大元素中包含𝛼∗𝛽个单元格。从中选取若 干个单元格组合构成的空间区域称为一个索引空间。
TShape索引的空间结构如下：首先，通过应用四叉树的规则，将单一单元格递归地划分为四个子单元格，每个子单元格的分辨率更高。图3（a）中展示了不同分辨率的单元格。接着，TShape索引采用相同分辨率的𝛼∗𝛽个单元格，构建出一个放大元素，并使用放大元素中单元格的组合作为索引空间来描绘轨迹的几何形状。
在轨迹表征的过程中，TShape 索引根据轨迹的位置和大小匹配最合适的放大元素，并从该放大元素中选取与轨迹形状最契合的一个索引空间以表示轨迹的空间特征。图3 (b) 和 (c) 提供了相关例子。例如，在𝛼∗𝛽为2∗2的设置下，轨迹𝑇1和𝑇2分别由三个分辨率为2的单元格所表示。此外，𝑇4则由两个分辨率为3的单元格表示。当𝛼∗𝛽为3∗3时，𝑇1和𝑇2可通过五个分辨率更高的单元格进行更精细的表示。
图3 TShape索引的结构
轨迹的大小各不相同，单元格的大小也随着分辨率的变化而变化。因此，𝛼∗𝛽个高 分辨率的单元格难以覆盖具有大空间跨度的轨迹。同时，采用低分辨率的单元格来表示空间跨度极小的轨迹，会导致表示精度显著下降。因此，对于给定的轨迹𝑇，TShape 索引首先需要确定能覆盖该轨迹MBR的最小放大元素。为简化过程，文章将整个空间范围的高度和宽度都归一化至[0,1]的范围内。
TShape索引编码：
同样的，在继续介绍之前会先给出定义：
定义7(QuadrantSequence,𝑄：单元格的象限序列码)。给定象限序列𝑄=𝑞1 𝑞2 ... 𝑞𝑟，其整数序列码为：
其中，𝑔是任意单元格的最大分辨率。如图4（a）所示，当𝑔=2时，放大元素‘03’ 和‘33’的序列码分别为4和20。
定义8(ShapeCode,𝑠: 形状码)。一个放大元素涵盖了𝛼∗𝛽个单元格，以0到（𝛼∗𝛽−1）之间的数字，来标记每个单元格在该放大元素中的位置。形状码由𝛼∗𝛽个比特位构成，如果轨迹与某个单元格相交，则其对应位置的比特位设为1，否则该位设为0。
例如图5所示，放大元素‘03’包含9（3∗3）个单元格，并用数字0至8标记这 9个单元格的相对位置。该放大元素涵盖了轨迹𝑇0、𝑇1、𝑇2和𝑇3，这些轨迹的形状分 别由形状码𝑠0、𝑠1、𝑠2以及𝑠3表示。
定义9(𝑇𝑆ℎ𝑎𝑝𝑒(𝑐𝑜𝑑𝑒(𝐸),𝑠)：TShape索引值)。一个索引空间由放大元素𝐸和形状 码𝑠组成，其索引值如下，如图4（b）所示。
一个放大元素由从左下角单元格开始的𝛼∗𝛽个连续的单元格构成。因此，TShape将使用左下角单元格的序列编码来表示对应的放大元素。接着，使用形状码来标记由放大元素中涵盖的单元格自由组合形成的不同形状。
图4 TShape索引的索引编码
图5 TShape形状码
最优形状码：不考虑形状连续性的前提下，一个包含𝛼∗𝛽个单元格的放大元素能够产生2𝛼∗𝛽种不同的形状码。因此，增大𝛼∗𝛽的值可以提升形状码的精度，从而更精确地表示轨迹形状。
在实际应用场景中，放大元素内通常仅有少量的形状码被用于表征轨迹形状，可以显著精简编码空间大小。此外，相似的轨迹倾向于拥有相似的索引空间。因此，新的形状码编码策略应当维护这一相似性特征。假设在一个放大元素中仅有𝑀个实际使用的形状，记作集合𝒮={𝑠0, 𝑠1, ..., 𝑠𝑀−1}。形状码重新编码的优化目标是按照最佳顺序将这M个形状从0到𝑀−1进行重新编号。图6展示了一个例子，TMan的目的是让在空间上相似的形状，其形状代码应越接近。
图6 最优形状码
为了衡量相似性，TMan使用了Jaccard 相似性系数。形状 si 和 sj 的相似度是：
其中|Si∩Sj| 是Si和Sj覆盖的单元格数，其中|Si∪Sj| 是Si或Sj覆盖的单元格数, 形状重编码的目标是找到一个更好的编码 顺序(𝒪=⟨𝑜0,𝑜1,𝑜2, ...,𝑜𝑀−1⟩，其中，任意𝑜𝑖∈𝒮,并且，当𝑖 ≠ 𝑗时，𝑜𝑖 ≠𝑜𝑗)，使得 所有相邻的形状之间的相似值累加和最大，即：
这个问题可以看作是TSP问题（旅行商问题，一种NP难问题）的一个变种，旨在寻找不返回起点的最长路径。针对给定的𝑀个待编码的形状，可通过一个完全图来 表征各形状间的相似度关系，每个形状对应图中的一个节点，形状之间的相似性是相应节点之间的边。编码目标在于确定一条最长的路径，确保每个形状有且仅被访问一次。TMan利用贪心算法（GreedyAlgorithm）和遗传算法（GeneticAlgorithm）来解决形状编码问题。具体来说，贪心算法作为一种启发式方法，在每次迭代中优先选择距离最远的未访问形状以构建路径。贪婪心算法的主要优势在于其简洁性与高效性。图7中呈现了四种形状，它们之间的相似度如图7最右边所示。贪心算法确定的最优编码顺序为 ⟨S0, S1, S3, S2⟩ ，对应的累积相似度为1.92，而原始顺序（⟨S0, S1, S2, S3⟩）的累积相似度仅为1.75。因此，新编码方案更有利于将相似度较高的形状编码得更为接近。
图7 不同顺序的形状相似度累积值.
2.2.3 IDT索引
给定一个轨迹𝑇，其移动对象ID为𝑇.𝑜𝑖𝑑，并且此轨迹的开始时间和结束时间分别位于为时间片𝑇𝑃𝑖和𝑇𝑃𝑗中。因此，IDT索引值由𝑇.𝑜𝑖𝑑和时间段索引值（TR 索引值）整合而成：
ID𝑇(𝑇) = 𝑇.𝑜𝑖𝑑 :: 𝑇𝑅(𝑇𝐵𝑖,𝑗)
其中，𝑇𝑅(𝑇𝐵𝑖,𝑗)是轨迹𝑇 时间范围的索引值，‘::’代表连接操作。
2.2.4 ST索引
ST索引可用于高效支持时空范围查询。ST索引的索引值由两部分组成，即时间段索引值和空间形状索引，具体定义如下：
S𝑇(𝑇) = 𝑇𝑅(𝑇𝐵𝑖,𝑗) :: 𝑇𝑆ℎ𝑎𝑝𝑒(𝑐𝑜𝑑𝑒(𝐸),𝑠)
其中，𝑇𝑅(𝑇𝐵𝑖,𝑗) 是轨迹𝑇时间范围的索引值，𝐸是覆盖轨迹𝑇的最小放大元素，𝑠 是𝐸中最合适表示轨迹𝑇形状的形状码。
2.3 存储架构
设计存储模式的目标是有效地管理键值数据库中的大规模轨迹数据。TMan 提供两种表类型：主表和副表。用户可以为需要高效率的查询场景创建主表。对于对效率要求不高的查询场景，建议使用二级表，这样可以减少存储开销。此外，TMan采用索引缓存机制来最大限度地减少索引的计算。元数据表存储了索引和用户配置的参数。
图8 存储架构（TShape是主索引）
主表结构（Primary Table）：TMan使用主表存储轨迹数据。
辅助索引表结构（Secondary Table）：TMan的辅助索引表只存储其它类型的索引值与主表行键之 间的关系。
元数据表结构（Metadata Table）：TMan利用元数据表来存储表结构以及索引参数等信息，比如构建主索引类型及所需参数等。
索引缓存（Index Cache）:TMan采用了索引缓存机制，以尽量减少索引的计算量。一个放大元素中仅有少数 形状会被用于表示轨迹，这些形状的形状码可通过最优形状码中提出的优化方案进行重新编号。因此，TMan必须维护放大元素使用的形状和其最终形状码之间的映射关系。TMan 用元组⟨放大元素序列码,原始形状码,最优形状码⟩表示形状和最优形状码的映射关系，并利用Redis来缓存这些关系。例如在图5和图7中出现的形状和其对应形状码的映射关系分别是：⟨03,111100001,0⟩, ⟨03,011110001, 1⟩, ⟨03, 000010011,3⟩ 和 ⟨03, 010010011, 2⟩。
当 TMan 接收到查询请求时，首先会在内存缓存中查找相应的映射关系。如果在内存缓存中未找到查询条件的映射元组，则会从Redis中加载对应放大元素的映射元组到内存缓存中。
2.4 数据更新
TR 索引的结构不随数据增加而改变，而TShpae索引的最优形状码可能会发生变化。为此，TMan更新策略旨在维护放大元素和最优形状码的映射关系，关键步骤如下：
• 分组：TMan利用TShpae索引，计算出新增轨迹（可以批量新增）的放大元素 序列码，并且根据放大元素的序列码来分组新增的轨迹；
• 获取形状码：在每个组内，为每条轨迹分配最优的形状码。首先计算轨迹在此 放大元素中的原始形状码，然后通过索引缓存机制得到最优形状码，并用于存储；
• 临时形状码缓冲池：为了加强形状码的空间相似性，TMan实现了对应的优化机制，并利用了索引缓存来存储形状和最优形状码的映射关系。当新增的数据需要使 用放大元素中之前未使用的形状时，TMan采用了临时形状码缓冲池此来记录这些形状，并且按出现顺序依次为新增的形状分配形状码，并以此来存储对应的轨迹；
• 重编码与更新：一旦临时形状码缓冲池中的形状码数量超过最大阈值，TMan 会触发TShape索引的重新编码过程。首先，将当前放大元素中已进行过优化编码的形 状与新增的形状合并在一起。然后，通过最优形状码的编码方式进行重编码，从而得到最优形状码的映射关系。接着，更新索引缓存中的映射关系，并清空形状码缓冲池。同时，提取使用过期编码的数据，将其删除，并使用更新后的编码进行存储。
图9 查询处理流程
三．实验
3.1 实验设置
数据集：文章使用了三个数据集评估来TMan的效率：（1）TDrive。包含北京一周内的318,744条出租车的轨迹；（2）Lorry。该数据集由从2014-03-01到2014-03-31 期间生成的货车数据，进行预处理后，它包含了来着广州的2,643,450条货车轨迹；（3） Synthetic。为评估可扩展性，文章将原始货车轨迹数据的位置进行了随机偏移，生成 了10倍的货车数据。TDrive数据集大小为752MB，货车数据的总大小超过了100GB。 图10（a）和（b）显示了TDrive 和 Lorry 数据集中轨迹的时间范围分布情况。
图10 数据集的时间和空间分布
实验环境：所有实验均在由五台机器构成的集群上进行，每台机器配备了8核CPU、1TB磁盘空间及32GB内存。
评估指标：文章在数据集TDrive与Lorry的时空范围内各随机生成了100个查询窗口，并以查询结果的中位数作为评价指标。
3.2 TR索引性能分析
TR索引用𝑚个连续的时间片来表示一个时间范围。本小节将TR索引的时间片大小设置为10分钟、30分钟、1小时、2小时、4小时、6小时以及8小时，对应的TR索引分别为TR-10M,TR-30M,TR-1H, TR-2H, TR-4H, TR-6H, 和 TR-8H。此外，还将TR 索引与XZT索引进行了比较。图11列出了随查询窗口大小变化时，不同索引所需查询时间和访问的候选轨迹数，观察到的结果如下：1）随着查询窗口大小的增加，需要更多的时间来访问更多的轨迹；2）TR索引优于XZT索引。例如，当查询窗口为24小时时，TR-1H比XZT快3倍；3）时长更短的时间片，表示时间范围的精度越高，使得需要访问的轨迹更少。然而，较短的时间片会增加索引值的编码空间，从而对数据的本地性产生负面影响。因此，与TR-10M相比，虽然TR-1H需要访问更多的数据，但 TR-1H 的数据存储比TR-10M更集中。因此，有时TR-1H的性能会优于TR-10M。
图11 时间范围索引的性能评估(Lorry)
3.3 TShape 索引性能分析
文章通过执行空间范围查询（1.5km*1.5km）来评估TShape索引的效率。TShape 索引的索引空间是由不超过𝛼∗𝛽个位于同一分辨率的单元格组成。存储时，TMan利用最契合轨迹数据的序列码和形状码来索引轨迹。此外，为更好的存储相似的轨迹形 状，文章对形状码的编码顺序进行了优化。
𝛼和𝛽的影响：文章中将𝛼∗𝛽的设置从2∗2开始并不断增加至5∗5，以观察𝛼∗𝛽的变化对TShape索引性能的影响。如图12（a）中展示在保持𝛼不变的情况下， 随着𝛽的增加，被访问的候选轨迹数量会不断减少。造成这种现象的原因是，较大的 𝛼∗𝛽 可以更精细地表示轨迹的形状，从而可以缩小检索范围。然而，较大的𝛼∗𝛽会产生更多的索引空间，导致数据存储更加分散。因此，查询处理需要更多时间来计算与查询范围相交的索引空间，并且I/O次数也会随之增加。所以，如图12(a)和(b)所示，虽然𝛼∗𝛽=3∗3时对轨迹形状的表示能力比3∗4稍差，但3∗3的查询更快。
图12 变化𝛼和𝛽
编码和索引缓存的影响：由𝛼∗𝛽个单元格形成的放大元素有可能产生2𝛼∗𝛽 种形状。然而，在现实世界的数据集中，这些形状中仅有一小部分会被用来表示轨迹。 如图13(a) 所示，对于TDrive数据集，任意用于表示轨迹的放大元素中使用的形状数量都不超过4734个。而且，大多数放大元素中使用的形状少于10个。因此，TMan采用了索引缓存机制来维护每个放大元素中实际使用的形状码。此外，原文还探索了不同的编码方法，以优化形状码的顺序。图13(b)展示不同形状码编码策略的影响。在不使用索引缓存的情况下，需要从2𝛼∗𝛽种形状中搜索可能与查询条件相交的形状上，会产生大量的计算时间。在各种编码方法中，遗传编码的性能略优于其他方法。因为，它更能为相似的形状分配相邻的索引值，从而减少查询过程中的磁盘I/O操 作。此外，文章还将索引缓存策略应用于XZ*索引中，TShape索引的性能仍然优于XZ* 索引。尽管如此，如图13(c)所示，与贪心编码和bitMap（位图）编码相比，遗传编码需要更多时间来确定形状码的最佳顺序，从而导致它的存储时间远高于其它编码。此外，不直接使用形状码来索引轨迹，原文中本实验也实现了利用所有相交单元格的反转列表 （Inverted）来存储轨迹数据。这种方案需要更多的存储成本，并会带来更多的I/O成本。 在查询时，此方案还需要大量数据删除重复数据。因此，它也比TShape索引慢。
图13 TShape索引的性能(TDrive,𝛼∗𝛽=5∗5)
3.4 数据存储和更新性能分析
多索引多表存储方案为TR索引、TShape索引以及ID索引各建立一个数据存储表。多级索引表结构存储方案将TShape设置为主表，用于存储轨迹数据。TR索引和 ID 索引存储在辅助表中。同时利用Redis缓存TShape的最优编码结构。如图14（a）所示， 较多索引多表存储方案，采用多级索引表结构能显著地降低存储开销，减少约60%的存储开销。由于不需要存储轨迹数据，多级索引表结构中用于支持其它类型的查询和 索引缓存的开销明显小于主表。
文章中本实验通过将不同数量级的新增轨迹批量插入到现有表格中，以评估更新的性能。从图14（b）中可以得出，随着数据量的增加，存储所需要的时间越多，但仍在可接受范围内。因此，TMan的更新策略能确保系统的灵活性。
图14 存储开销（TDrive）与数据更新时间
3.5 时间范围查询（TRQ）性能分析
论文中评估了时间范围查询。图 15（a）显示了查询时间，图 15（b）显示了将被查询的数据集数量。对于 TrajMesa 和 TMan，候选项是访问轨迹，而对于 STH，候选项是访问点，因为轨迹被拆分为点并存储在 HDFS 中。图 15（a） 表明 TMan 实现了最佳性能。TrajMesa 使用 XZT 来索引轨迹的时间范围，而 TMan-XZT 在我们的框架中使用相同的 XZT 索引。TMan-XZT 优于 TrajMesa，因为它能够向下推送查询条件。TR index 具有精巧的索引结构和编码方法，与 TrajMesa 相比，TDrive 和 Lorry 的访问量分别减少了 30% 和 77%。此外，图15（b）显示，使用 TR 索引的 TMan 访问的数字轨迹最少，甚至比 STH 高出一两个数量级
图15 时间范围查询的性能
3.6 空间范围查询 (SRQ) 性能分析
文章中将空间窗口设置为从 100m*100m 到 2500m*2500m 不等，以评估空间范围查询。图 15 显示，随着空间窗口大小的增长，由于需要数据集数量的增做，所有系统都需要更长的查询时间。TMan 比 TrajMesa 和 STH 更快，因为它修剪了更多不相关的轨迹。STH 需要在 HDFS 上构建 Map-Reduce 任务，导致多个 I/O 降低其查询性能。TMan-XZ 采用的是 TrajMesa 的空间索引。
结果表明：
1） 使用索引缓存和下推策略，TMan的工作优于 TrajMesa;
2） 带有 TShape 的 TMan 超过了 TMan-XZ，证明 TShape 指数比 XZ 排序更好。平均而言，与 XZ 排序相比，TShape 指数在 TDrive 和 Lorry 上检索的次数分别减少了 83% 和 52%。
图16 空间范围查询的性能
四．总结
本文介绍了TMan，这是一个基于键值数据存储的高性能轨迹数据管理系统。该系统通过TR和TShape索引精准捕捉轨迹的时间和空间特征。TR索引提供了一种简洁的编码方式，专为时间范围设计。而TShape索引则采用非矩形索引空间来详细描述轨迹的复杂形状。为了高效索引轨迹形状，论文设计了一种优化的编码方法。依托这些索引，论文提出了一种新颖的存储模式。此外，为了支持多样化的查询需求，论文构建了索引缓存机制，通过缓存频繁访问的索引和查询结果来提升查询效率。论文还开发了一种高效的查询处理框架，利用这些优化的索引快速准确地返回查询结果。特别值得一提的是，在处理时间范围查询（TRQ）和空间范围查询（SRQ）时，与XZ排序相比，TMan平均能够减少77%和83%的检索次数，显著提高了查询性能。
 |
重庆大学时空实验室（Spatio-Temporal Art Lab，简称Start Lab），旨在发挥企业和高校的优势，深入探索时空数据收集、存储、管理、挖掘、可视化相关技术，并积极推进学术成果在产业界的落地！年度有3~5名研究生名额，欢迎计算机、GIS等相关专业的学生报考！
图文｜洪程璁
校稿｜孙杨洋
编辑｜李佳俊
审核｜李瑞远
审核｜杨广超
