摘要： 近年来，相似性搜索已成为许多轨迹数据分析任务的重要组成部分。随着轨迹数量的增加，我们必须在大量轨迹中找到类似的轨迹，需要一个可扩展和有效的框架。通常，大量的轨迹数据可以通过键值数据存储来管理。然而，现有的键值数据存储的工作使用粗糙表示来存储轨迹数据。此外，它们不能提供有效的查询处理来搜索相似的轨迹。为此，本文提出了一种高效的键值数据存储轨道相似度搜索框架——TraSS。我们提出了一种新的空间索引，XZ*，它利用不规则形状和大小的细粒度索引空间来精细地表示轨迹。进一步，我们设计了一个从XZ*的索引空间到连续整数的双目标函数，该函数简单而有效。为了提高相似度搜索的效率，我们采用两步对不同轨迹进行修剪:(1)全局修剪。它利用XZ*索引删除没有类似于查询轨迹轨迹的索引空间。我们的全局剪枝只能挑选出与查询轨迹大小和形状相似的索引空间。与最先进的索引相比，我们的全局剪枝在查询处理期间减少了66.4%的I/O开销;(2)当地的过滤。它以一种低复杂度的方式过滤不同的轨迹。我们利用道格拉斯-佩克算法从轨迹中提取的几个代表性特征来加速局部滤波。我们在一个流行的键值数据存储上实现了一个开源工具包(TraSS)。大量实验表明，TraSS的性能优于最先进的解决方案
面临的问题：
1)它们以粗表示的方式存储轨迹，(2)缺乏搜索相似轨迹的高效查询处理。
表示：轨迹由多维点组成，但键值数据存储使用一维键值对存储对象。因此，我们必须为轨迹分配一个适当的键。
查询：计算两个轨迹的相似度是耗时的，因为相似度的度量往往相当复杂。因此，必须提前修剪尽可能多的不同轨迹，以避免在查询处理期间产生不必要的I/O开销和计算。因此，经常采用两个步骤来提高查询效率:(1)全局删除 可以避免访问不相关的存储区域 (2)局部滤波以低复杂度的方式快速去除每个数据区域内的不同轨迹
方案:
1)我们提出了一种高效的基于键值数据存储的轨迹相似度搜索框架TraSS。(Representation).我们提出XZ*索引来表示同一索引空间内尽可能多的相似轨迹。具体来说，它将xz - order的每个放大元素划分为四个相等的子四边形，并将子四边形的组合作为索引空间。较大的索引空间用于覆盖较大的轨迹，而较小的索引空间用于覆盖较小的轨迹。此外，相似大小的轨迹可以通过它们的空间形状来区分。
2）(Query processing). (Global pruning). 因为我们的索引可以精确地描述轨迹的大小和形状，所以我们只访问与查询轨迹Q相似的几个索引空间，避免访问与Q不同的索引空间覆盖的轨迹。(Local filtering).我们使用DP (Douglas-Peucker)算法从轨迹中提取代表点。它利用很少的点来近似轨迹的空间形状。
疑惑点：1)文中提出的(Representation)轨迹表示方法令人感到奇怪，将空间划分为更小的部分，或者说是四叉树的方式，用空间表示轨迹。我的理解是利用最小外界矩阵（MBR）来表示要查询的轨迹，但是文中没有提到如何有效的切分轨迹。
2)整个框架图，看到后很迷惑。尤其在文中query部分。全局删除部分完成后，剩下相似部分，但是文中是怎么实现全局删除部分和representation关联的，在图中看不到相互之间存在的关联性。
