目录

• Abstract
• Introduction
• Background
• EDR
• Efficient Trajectory Retrieval Using EDR
• EXPERIMENTS

Abstract

EDR算法对于这些data imperfections更鲁棒。相比于其他的方法，EDR算法更加的有效率和精确。

一 、Introduction

1. 背景

随着移动计算和computer vision techniques的发展，在实际生活或者视频中追踪移动物体的轨迹变得很简单。由此也衍生出来了很多有趣的系统。例如在运动领域，通过分析可以获取某个顶尖运动员习惯的运动轨迹（例如篮球中的突破轨迹）并实施针对性策略（如防守）

2. 轨迹

一个移动物体的轨迹S的，被定义为一系列的“对”。例如：

S = [(t1, s1), (t2, s2) …… , (tn, sn)]。

n就是S序列的长度；si是在ti时刻处的抽样值，一般是2或者3维的数据。

S就代表着物体在一段时间内的连续运动轨迹。很明显，轨迹S一般被描述为2或者3维的时空数据。

而我们感兴趣去的，是许多轨迹的移动的形状。

对于两条轨迹，抽样得出的数据（也就是si）非常重要，可以用于测量两个轨迹的相似度。而时间数据，经常可以被忽略。

3. 基于相似性的检索及轨迹数据面临的问题

2中S中的si，对于基于相似性检索的时空数据库非常重要。

当si是一维（例如股票、商品价格预测、销售量、天气数据、生物医学数据）的时候，已经有了许多出色的成果。但是，一维数据的许多成果，不能直接被用于轨迹数据。因为多维数据有以下的特点：

• 轨迹数据通常是2、3维的，而且通常有不同的长度。

• 轨迹通常包含离群值、异常点。

  不像股票、商品价格等一维数据，轨迹通常由间歇性获取物体的位置所得，因此必然受限于传感器精度不够、干扰信号过大、探测仪器出现错误等情况。

  对于以上这种噪声点的处理，LCSS方法是一个不错的解决办法。但是它没有考虑两个轨迹之间的各种gap

  间隙(gap)指的是两个轨迹中两个识别的相似分量之间的子轨迹。（没看懂）（为什么会导致不准确？）

• 两条轨迹，可能在不同的区域，出现了相似的模式。这主要是因为local time shifting：

  由于不同的采样率或者物体不同的移动速度，导致虽然两个物体移动的轨迹很相似，但是某一些时间段可能因为实验原因而对应不上。

  对于以上local time shifting问题，DTW、ERP是好的解决办法，但是他们对噪声很敏感。

由于以上的问题，以及这些问题的解决办法并不完善，便有了本文。以下是文章内容总括：

• 本文提出了一种新的方法：EDR：Edit Distance on Real sequence。

  ED(edit distance是次方法的基础)，EDR通过把距离量化成0、1来实现噪声点的抑制，而edit distance这个方法本身又对local time shifting情况有所改善（尤其是当local timeshifting不是很大的时候）。当local time shifting很大的时候，EDR的结果也会出现偏差。

  但是这种情况本身就非常极端，而我们又不可能通过采样过后的数据还原出真实的原始数据（真的不行吗？差值？采样定理？我不知道）

• 本文你提出了三种修剪策略——Q-grams均值、金丝三角不等式、轨迹直方图——来提升EDR的检索效率。（通过减少需要检索的“候选人“）

  这是因为不同于LCSS、DTW，因为EDR将距离转化成了0 1，因此不满足三角不等式，不能使用传统的方式来检索。

  这些修剪方式也提供给了用户很大的灵活性：

  这些修剪方法不需要对两个轨迹之间的匹配区域设置约束，因此为用户提供更大的灵活性。（局部匹配？不太懂）（还是指三种方法可以随意结合？但是看起来不是这个意思）

• 展示了如何把这三种方法结合起来，提升准确率。

  文章展示了很多种三种方法的不同结合方式，并且根据他们的修剪功率（pruning power）和加速率（speedup ratio），展示了组合方法的优越的搜索效率。

二、Background

1. 范围定义——划定到二维

为了简单和不失一般性，把轨迹设定为二维的（文中所有的定义、定理都可以被扩展到三维或者更高维度），因此

S = [(t1, s1) ..., (tn, sn)]

si = (S(i,x) ,S(i, y) )， 括号内的内容是下标

(ti, si)是轨迹S的一个代表性元素

2. 数据归一化

可以对轨迹S进行归一化：

u(x),u(y)是其两个唯独的均值

σ(x),σ(y)是两个唯独的方差

image.png

归一化很推荐的，因为归一化使得两个轨迹之间的距离对于空间缩放和移位是不变的。（不太懂）（空间缩放能明白，这个位移没懂）

在下文中将会使用S来替代Norm(S)，即，下文的S都是归一化之后的。

3. 符号说明

4.距离函数定义

image.png

• Eu、DTW、ERP对噪声敏感

• Eu不能处理local time shifting和长度不一致的轨迹

• LCSS可以处理有噪声的轨迹，但是它是一个非常“粗糙的”的算法。（gaps）（it does not differentiate trajectories with similar common subsequences but different sizes of gaps in between.）

三、EDR

EDR比 已存在的 测量两个轨迹之间相似度的 方法 更加的鲁棒、精确。

1. Edit Distance on Real Sequences

Edit distacne(ED)是本方法的基础：

EDR is based on Edit Distance (ED) [26], which is widely used in bio-informatics and speech recognition to measure the similarity between two strings. Given two strings A and B, ED(A, B) is the number of insert, delete, or replace operations that are needed to convert A into B.

但是由于轨迹不是字符串，也不是一维的，因此，合理的定义两个轨迹的元素对“匹配”这一概念，就显得十分重要了。

(1).两个定义

• Defination 1: match

  假如两个轨迹的两个元素ri和sj相互匹配，当且仅当他们满足：

  |r(i,x) - s(j,x)|<= e && |r(i,y) - s(j,y)|<=e

  e是匹配阈值，此时可以写作match(ri, sj) = true

• Defination 2: EDR数值的计算公式

  R和S是两条轨迹，长度分别是n和m。EDR(R, S)是指在阈值为e的情况下把R变到S所需要的插入、删除或者替换操作的次数。其公式如下：

  image.png

  假如match(r1, s1) == true，那么subcost = 0，否则subcost = 1。这是一个递归调用的方法。

  何为EDR，EDR就是操作数！只不过是在阈值e限制下的edit distance。和后文的k紧密相关的！

  例如：

  假如(t1, 0.9), (t2, 1.2)。e=1的时候，这两个点（轨迹）相匹配，EDR是0。但是实际的edit distance是1。但是随着e的减少（即精度的增加，EDR越来越去趋近于实际的edit distance）

(2)从定义看优势

• 其实真正的计算就是subcost，也就是说实现了把距离转化成0 1（也就是是否匹配）。因此对噪声有很强的抑制作用。（LCSS其实也这么干了）

• “最小的 把 R 变成 S ”的这个过程，自然也就赋予了EDR处理local time shifting的能力。当时，假如shifting太大了，最后的EDR结果也会很大。

• 对于不匹配的，subcost = 1。这其实是一个惩罚手段（而LCSS中选择直接跳过），因此EDR又要比LCSS更加准确。

2. Evaluation of EDR

总之就是好好好。

四、Efficient Trajectory Retrieval Using EDR

在定义1中，e被用来限定是否匹配。（也就是用来去除噪声）但是也造成了它违反三角不等式，属于non-metric，因此不能通过传统方法进行索引。

其实基本上所有的对噪声有抑制作用的算法，通常都不符合三角准则。

另外，心理学研究表明，人类的相似性判断也不符合三角准则。

因此，问题现在就在于如何提升相似性搜索的检索效率。每次EDR操作的时空复杂度是O(m×n)，m和n是两个轨迹的长度。（DTW、ERP、LCSS都是二次的）

提出方法的目标是：在没有错误的“解雇”的条件下，尽可能的减少错误的候选者。（减少需要计算EDR的轨迹的数量）

1. Pruning by Mean Value Q-gram

(1)预备知识：

近似字符串匹配问题：

对于一个长度为n的字符串文本，和一个长度为m的模式（m<n)，检索出所有的子字符串，这些字符串需要满足他们到这个模式的edit distance最大是k。

Q-gram：

Q-gram是字符串S的一个长度为q的所有子字符串的集合。

例如

S = [(t1 , (1, 2)), (t2 , (3, 4)), (t3 , (5, 6)), (t4 , (7, 8)), (t5 , (9, 10))]。

那么其大小为3的Q-gram是：

[(1,2), (3, 4), (5, 6)], [(3,4), (5,6), (7, 8)], [(5,6), (7,8), (9,10)].

定理 1：

假如P和S长度分别是m和n，假如P和S的edit distance在k之内，那么一定满足，他们有至少p = max(m, n) - q + 1 - kq个共同的Q-gram.

换言之，假如这某两个字符串小雨了p个共同的Q-gram，那么这俩字符串的edit distance一定不满足最大为k。

这条定理也已用于去除错误的候选者。（但是也要加入措施来避免去除正确的候选者）

此定理只适用于一维数据。

定义 3：

给定两个序列R和Q的两个Q-gram: r = [(r(1,x) , r(1,y)), . . . , (r(q,x) , r (q,y) )] and s = [(s(1,x) , s(1,y) ), . . . , (s(q,x) , s(q,y))] ，当说r匹配s的时候，当且仅当r的每一个元素对应匹配s的每一个元素。（Q-gram一定是q长度啦）

定理2：

对于给定的阈值e，假如两个Q-gram，r和s（与定义3中相同）匹配，那么他们的均值也匹配。

image.png

Q-gram的均值，就是一个q纬度“元包”，每一个“元包”具体是多少维度，主要是要看轨迹采样点的纬度。例如(1,2,3,4,5,6)的q=3时的Q-gram就是三维元包，元包是一维的（实际上就是(3, 4, 5)

但是对于二维元包：S=((1,2),(3,4),(5,6),(7,8),(9,10))的q=3时的Q-gram的均值就是三维元包，元包是二维的（实际上就是((3, 4), (5, 6), (7, 8))

而每一个Q-gram适合均值一样形式的。

(2) 存在的问题

• 每一个轨迹的Q-gram都需要别存储的话，那么存储消耗非常高。

• 定理一只适用于一维数据

• 直接应用Q-gram还会导致维度灾难。

最终，定理一只能用于范围查询（？？？），而在大多数情况下，用户实现又不知道一个范围。

引出k-NN search.

(3)对以上问题的改善

使用定理二，我们就不需要再存储大量的Q-gram了。

更重要的是，我们可以更快的检索出轨迹的Q-gram。

例如：

image.png

(4)实现算法

k-NN查询响应

其中，这里的k是k-NN算法中邻居的范围定义限制，与EDR中的k没有关系。

此算法不引入错误的“解雇”：即不把正确的匹配结果去除掉。

2. Pruning by Near Triangle Inequality

(1) 近似三角不等式

EDR不满足三角不等式，但是满足以下不等式（近似三角不等式）

对于给定的三条轨迹Q，S，R，有如下不等式：

EDR(Q, S) + EDR(S, R) + |S| >= EDR(Q, R)

其中，|S|是轨迹S的长度。

移项得到：

EDR(Q, S) >= EDR(Q, R) - EDR(S, R) -|S|

R可以当作是一个中间临时轨迹，EDR(Q, R), EDR(S, R)都可以直接算出。

(2)lower bound——下界

根据近似三角不等式，可以获得EDR(Q, S)的一个下界。可以用来被用来去除错误的候选项。

(3)算法

image.png

算法说明：

S某一条轨迹（数据库中的），Q是当前要寻找匹配轨迹的轨迹。procArray存储着EDR(Q, Ri)。pmatrix存储者EDR(Ri, S)。result是最后结果，注意，传入的时候就已经有内容了。

使用时需要用到dynamic strategies：

Let maxTriangle denote the maximum number of trajectories whose true EDR distances are kept for near triangle inequality pruning. Hereafter we call these trajectories the reference trajectories. The value of maxTriangle should be determined at query time by the query engine based on the buffer size. The larger maxTriangle is, the more pruning power can be achieved. Dynamic strategies pick these reference trajectories as NearTrianglePruning runs, therefore, the entire pmatrix is not needed.

预选的轨迹应该在查询时刻有查询引擎准备好，也就是说，近似三角形准则并不是一个完善的方法，不太同于4.1，甚至可以作为4.1的一个子部分。maxTriangle越大，说明下限越高，说明修剪的越好。

因此实际应用时的需要如下：

As the reference trajectories are picked and kept, the appropriate column of the distance matrix is read into the buffer space. The buffer space requirement is maxTriangle columns, each of size N (N is the trajectory database size). Thus, the total buffer space required is N ∗ maxTriangle. Given a database that contains 1,000,000 trajectories and maxTriangle = 400, the buffer space requirement is only around 400M, which is acceptable based on the current hardware configuration of PC. The selection of reference trajectories is query dependent. In our implementation, we simply pick the first maxTriangle trajectories that fill up procArray.

(4)对于算法的理解（个人）

这个算法的应用前提是，数据库已经查询到了k-NN响应（能查询k-NN响应就说明Q在这里就是已知的了），并且放到了result里面，procArray预先放的R就是那些轨迹和EDR(Q, Ri)。

这个方法就是用来去除“错误的解雇”和“错误的候选者”。此时考量的S是一条可能是“候选者”但没有被选中的轨迹，因此，此时的pmatrix也就有了，是EDR(Ri, S)。

而后根据近似三角形准则，先计算maxPruneDist——EDR(Q, S)的下界，计算的中介就是此时的procArray和pmatrix中的候选者们。假如此下界<此时最大的k-NN距离，那么说明这个轨迹可能是真正的候选者。但是近似三角形准则毕竟只是一个弱化版本的三角形准则，其限制范围本身就是被弱化的，非常有限。所以，之后要再去计算EDR(Q, S)——真实的EDR距离。

这是因为，EDR(Q, S)大于这个下界，当这个下界小于k-NN的最大距离，并不代表EDR(Q, S)就比k-NN距离小。

假如此距离确实比当前的realDist，假如此时的realDist确实要比bestSoFar(k-NN的最大距离)更好（小），那么说明这个轨迹S确实是真正的候选者。

因此，后续应当把realDist插入到procArray中（难道不应该也插入到pmatrix中？）（原文实在是没给出R到底是哪里来的，所以只能这么猜测，但是解释的并不圆满）

回到上一行自己括号里面的问题：

确实不需要插入到pmatrix中。

现在的目的是寻找Q的匹配轨迹，S是当前的可能的真正的候选者，而我们还需要去继续追寻下一条可能的候选者轨迹。

procArray是EDR(Q, Ri)，在这个过程中Q是不变的，所以当追寻下一个轨迹的时候，这个procArray还需要继续使用。

pmatricx是EDR(S, Ri)，当追寻下一条轨迹的时候，pmatricx是需要重新计算的！所以不需要插入。

与procArray同理，result是下次查询肯定要被用到的（毕竟是k-NN查询的结果！）！所以也需要重写！z

然后把此时的S和realDist插入到result中。

(5)其他

我们应当清楚，近似三角形准则是三角形准则的一个弱化版本。

假如轨迹们都有相同的长度，“避免错误解雇”的效果将会消失。（估计是因为|S|吧）。

其他的把非三角形准则转化成三角形准则的方式还有CSE

Given a distance function dist that is defined on data space D and does not follow triangle inequality, there exist three data elements x, y, z ∈ D, such that dist(x, y) + dist(y, z) < dist(x, z). dist can be converted to another distance function, dist 0 , by adding a positive value c to each distance value calculated by dist. For example, dist 0 (x, y) = dist(x, y) + c. If c is large enough, we may have dist 0 (x, y) + dist 0 (y, z) ≥ dist 0 (x, z) (which equals dist(x, y) + dist(y, z) + c ≥ dist(x, z)), thus, triangle inequity can be hold on dist 0 .

但是我们不使用这种方法，因为：

• All the pairwise distances in the data set have to be investigated to find c.

• Usually, for similarity search, query data are not inside the database.

3. Pruning by Histograms

(1). 预备知识

关键词：Embedding methods.

为了他提高再edit distance条件下的字符串的k-NN查询效率，嵌入式方法被提了出来。

方法的主要思想是把字符串 嵌入 到 一个向量空间中，然后在嵌入后的向量空间中定义一个距离函数（喵喵喵？）

为了避免错误的“解雇”，embedded space的长度就是字符串的edit distance的下界。（喵喵喵？）

许多的embedding 方法被提了出来，但是只有两个介绍了“false dismials”，他们都是用了一样的方法：

FV & FD & 一个定理

• FV: frequency vector

他们通过映射字符串到字符串的频率向量（frequency vector）（FV）上，来把字符串转换到多维的整形空间中。

有以下已经被证明的定理：

the frequency distance (FD) between the FVs of two strings is the lower bound of the actual edit distance.

即，已经证明，两个串的FV之间的频率距离（FD）是实际编辑距离的下限。

• FD：

定义：

FD of two points u and v in s-dimensional space, FD(u, v), is defined as the minimum number of steps (insertion, deletion, replacement operations) that is required to go from u to v (or equivalently from v to u).(喵喵喵？这不就是edit distance吗)

• 自己的一些理解：

正如定理中描述的那样：

the frequency distance (FD) between the FVs of two strings is the lower bound of the actual edit distance.

咱们这里比较的是两个字符串的FVs的距离，所以两个字符串的FVs之间的ED距离又称作FD？？？（我怎么觉得有点奇怪）

使用FV、FD的一些特点的分析

FV显然是一维的直方图（也就是柱状图），他的每一个bin都是字母表里的字母。

(2)算法

• 算法的主要目的

  按照上文介绍的把字符串转换成直方图的形式，这个算法的目的是把轨迹变成两维的直方图。然后通过直方图计算直方图距离。

  以此作为下界。

• 把轨迹转换成轨迹的直方图：

  首先，给出轨迹的x维度上的最大值和最小值，把[min. max]这段分成τx个相等的子范围，每一个子范围的大小都是e。对y纬度进行同样的操作。这两个子序列集之间的元素的任意组合都是直方图的bin。总得组合总数自然是τx * τy。其实也就是把x和y方向分成τx * τy个小格，每个小格都是直方图的一个bin。然后去数每个bin中存在的元素数量（也就是采样点的数量）。

• 定义4：直方图距离：DH：Histogram Distance

  Let H R and H S be histograms of two trajectories R and S, respectively. The histogram distance, HD(H R , H S ), is defined as the minimum number of steps required to go from H R to H S (or equivalently from H S to H R ) by moving to a neighbor point at each step. H R and H S are neighbors if R can be obtained from S (or vice versa) using a single edit operation of EDR.、

  a neighbor point, 也就是说加一

  假如HR和HS分别是两个轨迹H和S的直方图。那么HD(HR, HS)定义成：

  通过每一步移动一个临近点，把从HR转换到HR所需要的最小的步数。

  假如HR和HS是临近的邻居），那么R只需要一次edit operation就可以从S转换成R。

• 定义5：克服两个直方图靠近的边缘点之间的匹配问题：

  Therefore, to overcome the problem that elements located near the boundary of two different histogram bins may match each other under EDR, we treat the elements from two different histogram bins as if they were from the same bin if these two histogram bins approximately match.

  定义5正文：

  Given two histograms H R and H S , histogram bin h R,i of H R approximately matches histogram bin h S,j of H S , if h R,i and h S,j are the same bin or they are adjacent bins.

• 算法内容：

  The algorithm for computing HD between two histograms H R and H S . In procedure CompHisDist, the first for loop is used to compute the difference between two histograms, the second loop (line 4-7) is used to find the elements in the histogram bins that approximately match each other, and the third loop is used to count the minimum number of steps that is required to transfer H R to H S .

image.png

4.3待续

4.4Combination of three pruning methods

上面讨论的三种修建方式都是比较原始的，实际上，可以做到把三种方法结合起来使用——use one pruning method to save the computation of the true distance EDR(Q, S) after another.

(1)EDRCombineK-NN

histogram pruning is applied first, then, mean value Q-gram filters are applied. Finally, the procedure NearTrianglePruning is invoked to remove more false candidates based on computed real EDR distances.

先使用直方图修剪方式，在使用均值Q-gram过滤器。最后，在已经计算得到的EDR距离的基础上，使用近似三角形去除错误的候选者。

(2)算法

image.png

五、EXPERIMENTS

实验部分展示了两方面的实验结果：

• 每一种修剪技术的效率

• 方法之间的组合

实验测量的尺度有两方面

• 加速率：Speedup Ratio

  使用顺序扫描的平均时间 和 使用修剪策略时的平均时间只比。

  越大越好，越大越快。假如小于1，那么就要比直接顺序搜索，不修剪的效率还要低。

  Speedup ratio is defined as the ratio between the average total time (including both CPU and I/O measured in seconds) required for a sequential scan and the average total time needed with a pruning technique in answer a k-NN query.

  • 修剪能力：Pruning power

  修剪功率（不知道是不是这么翻译）指的是，对于给定的k-NN序列Q，数据集S中的没有被计算EDR的轨迹所占的分数。

  越大越好，越打越快，最大是1.

  （没有被被计算的，就是节省下来的计算力啊）

  Given a k-NN query Q, the pruning power is defined to be the fraction of the trajectories S in the data set for which the true distance EDR(Q, S) is not computed (without introducing false dismissals).

测量参数：

• k取值从1到20。

  （k是k-NN的k）

• 阈值e。

  使用多个e探测k-NN算法，选取最符合人类观察的一个e。

1. Efficiency of Pruning by Q-gram Mean Values

(1)数据来源

• UCI KDD 的 ASL 数据集。

• Kungfu 数据集

• Slip 数据集

(2)数据形式

ASL：710条轨迹，长度从60-140

Kungfu：有495条数据，记录着人在打功夫的时候 身体的关节的移动数据，每个轨迹长度是640。

Slip：一共495条数据，记录着人跌倒并且试图站起来的时候的身体关节的移动数据，每个轨迹的长度是400。

(3)测试项目

• 不同的Q-gram大小 的修剪效率

• indexed Q-grams versus merge join（是4.1的前半段方法和后半段方法的对比）（后半段没看）

• 两维Q-gram vs 一z维Q-gram

(4)最终结论

image.png

四个测试方法：

pruning with a R-tree on two dimensional Q-grams (PR), pruning with B + -tree on one-dimensional Q-grams (PB), and pruning with merge join on sorted two dimensional Qgrams (PS2) and one-dimensional Q-grams (PS1).

最终测试结论：

From two test results, we conclude that PS2 on Q-gram of size 1 is the best method to remove false candidates with mean value Q-grams.

PS2是使用Q-gram均值方式的最好方法。

(5)PS2：pruning with merge join on sorted two dimensional Qgrams (PS2)

以下是文中没有详细说明的第二种k-NN查询方法：

The second algorithm performs linear scan over sorted Q-grams. Procedure Qgramk- NN-seq (Algorithm 5.2) first conducts a merge join algorithm to find the common Q-grams between two trajectories without any indexes before computing the real EDR between them. The computation cost of this pruning step is only O(|Q| + max(|R|)) (not including sorting cost).

• 详细算法如下：

image.png

2. Efficiency of Pruning by Near Triangle Inequality

假如数据库中的轨迹都只有相同的大小，那么近似三角形就不能去除错误的候选者。

(1)数据来源 & 数据形式

同Pruning by Q-gram Mean Values。

因为Kungfu和Slip的轨迹的长度都一样，所以可以这两个不会被测试。

我们用来两个数据集，每个数据集有1000个轨迹数据。

而且保证每一个数据集的数据的长度从30到256不相同。

其中一个数据集的数据的长度 符合 均匀分布。两一个数据集的数据长度符合 正态分布。

(2)测试结果

可以看出：

• 相比于Mean Value Q-gram。修建功率、加速率都非常的低下。

  主要是因为近似三角形中的|S|实在是太大了，导致近似三角形的效果变得更差。找一个相比于|S|更小的数值，可以作为一个将来的工作。

• 近似三角形不等式在满足均匀分布的数据集中，表现的更好。

  这再一次印证了之前的假设：在数据长度越分散和均匀的情况下，效果越好。（ASL满足近似正态分布）

3. Efficiency of Pruning by Histograms

(1)测试变量

• 两种方法：

  • HSR：histogram sorted scan

  • HSE：histogram sequential scan

• 不同的bin size

  • (e, 2e, 3e, 4e)

• bin大小为e的 一维数据序列 直方图

(2)测试数据

section 5.1中的所有数据

(3)测试结果

• e 2e 3e 4e中，e的修剪效果和加速率是最好的

• 一维的序列数据的修建效率，要有更大e的比轨迹直方图表现更好。

  pruning power of one-dimensional data sequence histograms is better than that of trajectory histograms with larger bin sizes.

  (没看懂)

• creating one-dimensional sequence histograms with the same bin size e is better than enlarging the bin size e of trajectory histograms.

• HSR方法更加有效率

• 一维序列的加速比要非常接近甚至超过轨迹直方图的加速比

  the speedup ratio of one-dimensional data sequence histograms is very close to or even more than that of trajectory histograms with the same bin size

image.png

(4)测试结果

对比均值Q-gram的修剪功率和加速比率，我们可以发现，直方图方式在移除错误的候选者这方面（也就是这两个指标上）要普遍的强。

Comparing the pruning power and speedup ratio results of mean value Q-grams and histograms (Figures 7 vs. 9 and Figures 8 vs. 10), we also find that histograms generally perform better than mean value Q-grams on removing false candidates.

4.Efficiency of Combined Methods

(1)测试项目

使用4.4中提出的结合方法：

histogram pruning is applied first, then, mean value Q-gram filters are applied. Finally, the procedure NearTrianglePruning is invoked to remove more false candidates based on computed real EDR distances.

先使用直方图修剪方式，在使用均值Q-gram过滤器。最后，在已经计算得到的EDR距离的基础上，使用近似三角形去除错误的候选者。

直方图选择：HRE方式

均值Q-gram过滤器选择PS2形式

(2)测试数据

• NHL数据集：国家冰球联盟球员的二维轨迹

  • 5000条轨迹

  • 每条轨迹30-256的长度

• 混合数据集

  • 32768条轨迹

  • 每条长度60-2000

• 随机走动轨迹数据集

  • 10000条