目錄

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

Abstract

EDR算法對于這些data imperfections更魯棒。相比于其他的方法，EDR算法更加的有效率和精確环凿。

一 、Introduction

1. 背景

隨著移動計算和computer vision techniques的發(fā)展只怎，在實際生活或者視頻中追蹤移動物體的軌跡變得很簡單锨苏。由此也衍生出來了很多有趣的系統(tǒng)公罕。例如在運動領(lǐng)域，通過分析可以獲取某個頂尖運動員習慣的運動軌跡（例如籃球中的突破軌跡）并實施針對性策略（如防守）

2. 軌跡

一個移動物體的軌跡S的容贝，被定義為一系列的“對”自脯。例如：

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

n就是S序列的長度斤富；si是在ti時刻處的抽樣值膏潮，一般是2或者3維的數(shù)據(jù)。

S就代表著物體在一段時間內(nèi)的連續(xù)運動軌跡满力。很明顯焕参，軌跡S一般被描述為2或者3維的時空數(shù)據(jù)轻纪。

而我們感興趣去的，是許多軌跡的移動的形狀叠纷。

對于兩條軌跡刻帚，抽樣得出的數(shù)據(jù)（也就是si）非常重要，可以用于測量兩個軌跡的相似度涩嚣。而時間數(shù)據(jù)崇众，經(jīng)常可以被忽略航厚。

3. 基于相似性的檢索及軌跡數(shù)據(jù)面臨的問題

2中S中的si校摩，對于基于相似性檢索的時空數(shù)據(jù)庫非常重要。

當si是一維（例如股票阶淘、商品價格預測、銷售量互妓、天氣數(shù)據(jù)溪窒、生物醫(yī)學數(shù)據(jù)）的時候，已經(jīng)有了許多出色的成果冯勉。但是澈蚌，一維數(shù)據(jù)的許多成果，不能直接被用于軌跡數(shù)據(jù)灼狰。因為多維數(shù)據(jù)有以下的特點：

• 軌跡數(shù)據(jù)通常是2宛瞄、3維的，而且通常有不同的長度交胚。

• 軌跡通常包含離群值份汗、異常點。

  不像股票蝴簇、商品價格等一維數(shù)據(jù)杯活，軌跡通常由間歇性獲取物體的位置所得，因此必然受限于傳感器精度不夠熬词、干擾信號過大旁钧、探測儀器出現(xiàn)錯誤等情況。

  對于以上這種噪聲點的處理互拾，LCSS方法是一個不錯的解決辦法歪今。但是它沒有考慮兩個軌跡之間的各種gap

  間隙(gap)指的是兩個軌跡中兩個識別的相似分量之間的子軌跡。（沒看懂）（為什么會導致不準確颜矿？）

• 兩條軌跡寄猩，可能在不同的區(qū)域，出現(xiàn)了相似的模式或衡。這主要是因為local time shifting：

  由于不同的采樣率或者物體不同的移動速度焦影，導致雖然兩個物體移動的軌跡很相似车遂，但是某一些時間段可能因為實驗原因而對應不上。

  對于以上local time shifting問題斯辰，DTW舶担、ERP是好的解決辦法，但是他們對噪聲很敏感彬呻。

由于以上的問題衣陶，以及這些問題的解決辦法并不完善，便有了本文闸氮。以下是文章內(nèi)容總括：

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

  ED(edit distance是次方法的基礎)，EDR通過把距離量化成0蒲跨、1來實現(xiàn)噪聲點的抑制译断，而edit distance這個方法本身又對local time shifting情況有所改善（尤其是當local timeshifting不是很大的時候）。當local time shifting很大的時候或悲，EDR的結(jié)果也會出現(xiàn)偏差孙咪。

  但是這種情況本身就非常極端，而我們又不可能通過采樣過后的數(shù)據(jù)還原出真實的原始數(shù)據(jù)（真的不行嗎巡语？差值翎蹈？采樣定理？我不知道）

• 本文你提出了三種修剪策略——Q-grams均值男公、金絲三角不等式荤堪、軌跡直方圖——來提升EDR的檢索效率。（通過減少需要檢索的“候選人“）

  這是因為不同于LCSS枢赔、DTW澄阳，因為EDR將距離轉(zhuǎn)化成了0 1，因此不滿足三角不等式踏拜，不能使用傳統(tǒng)的方式來檢索寇荧。

  這些修剪方式也提供給了用戶很大的靈活性：

  這些修剪方法不需要對兩個軌跡之間的匹配區(qū)域設置約束，因此為用戶提供更大的靈活性执隧。（局部匹配揩抡？不太懂）（還是指三種方法可以隨意結(jié)合？但是看起來不是這個意思）

• 展示了如何把這三種方法結(jié)合起來镀琉，提升準確率峦嗤。

  文章展示了很多種三種方法的不同結(jié)合方式，并且根據(jù)他們的修剪功率（pruning power）和加速率（speedup ratio）屋摔，展示了組合方法的優(yōu)越的搜索效率烁设。

二、Background

1. 范圍定義——劃定到二維

為了簡單和不失一般性，把軌跡設定為二維的（文中所有的定義装黑、定理都可以被擴展到三維或者更高維度）副瀑，因此

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

si = (S(i,x) ,S(i, y) )， 括號內(nèi)的內(nèi)容是下標

(ti, si)是軌跡S的一個代表性元素

2. 數(shù)據(jù)歸一化

可以對軌跡S進行歸一化：

u(x),u(y)是其兩個唯獨的均值

σ(x),σ(y)是兩個唯獨的方差

image.png

歸一化很推薦的恋谭，因為歸一化使得兩個軌跡之間的距離對于空間縮放和移位是不變的糠睡。（不太懂）（空間縮放能明白，這個位移沒懂）

在下文中將會使用S來替代Norm(S)疚颊，即狈孔，下文的S都是歸一化之后的。

3. 符號說明

4.距離函數(shù)定義

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數(shù)值的計算公式

  R和S是兩條軌跡堤魁，長度分別是n和m喂链。EDR(R, S)是指在閾值為e的情況下把R變到S所需要的插入、刪除或者替換操作的次數(shù)妥泉。其公式如下：

  image.png

  假如match(r1, s1) == true椭微，那么subcost = 0，否則subcost = 1盲链。這是一個遞歸調(diào)用的方法蝇率。

  何為EDR，EDR就是操作數(shù)刽沾！只不過是在閾值e限制下的edit distance本慕。和后文的k緊密相關(guān)的！

  例如：

  假如(t1, 0.9), (t2, 1.2)侧漓。e=1的時候锅尘，這兩個點（軌跡）相匹配，EDR是0布蔗。但是實際的edit distance是1藤违。但是隨著e的減少（即精度的增加浪腐，EDR越來越去趨近于實際的edit distance）

(2)從定義看優(yōu)勢

• 其實真正的計算就是subcost，也就是說實現(xiàn)了把距離轉(zhuǎn)化成0 1（也就是是否匹配）顿乒。因此對噪聲有很強的抑制作用议街。（LCSS其實也這么干了）

• “最小的 把 R 變成 S ”的這個過程，自然也就賦予了EDR處理local time shifting的能力淆游。當時傍睹，假如shifting太大了，最后的EDR結(jié)果也會很大犹菱。

• 對于不匹配的拾稳，subcost = 1。這其實是一個懲罰手段（而LCSS中選擇直接跳過）腊脱，因此EDR又要比LCSS更加準確访得。

2. Evaluation of EDR

總之就是好好好。

四陕凹、Efficient Trajectory Retrieval Using EDR

在定義1中悍抑，e被用來限定是否匹配。（也就是用來去除噪聲）但是也造成了它違反三角不等式杜耙，屬于non-metric搜骡，因此不能通過傳統(tǒng)方法進行索引。

其實基本上所有的對噪聲有抑制作用的算法佑女，通常都不符合三角準則记靡。

另外，心理學研究表明团驱，人類的相似性判斷也不符合三角準則摸吠。

因此，問題現(xiàn)在就在于如何提升相似性搜索的檢索效率嚎花。每次EDR操作的時空復雜度是O(m×n)寸痢，m和n是兩個軌跡的長度。（DTW紊选、ERP啼止、LCSS都是二次的）

提出方法的目標是：在沒有錯誤的“解雇”的條件下，盡可能的減少錯誤的候選者兵罢。（減少需要計算EDR的軌跡的數(shù)量）

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之內(nèi)锦亦，那么一定滿足，他們有至少p = max(m, n) - q + 1 - kq個共同的Q-gram.

換言之令境，假如這某兩個字符串小雨了p個共同的Q-gram杠园，那么這倆字符串的edit distance一定不滿足最大為k。

這條定理也已用于去除錯誤的候選者舔庶。（但是也要加入措施來避免去除正確的候選者）

此定理只適用于一維數(shù)據(jù)抛蚁。

定義 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都需要別存儲的話禀忆，那么存儲消耗非常高。

• 定理一只適用于一維數(shù)據(jù)

• 直接應用Q-gram還會導致維度災難坯屿。

最終，定理一只能用于范圍查詢（巍扛？领跛？？）撤奸，而在大多數(shù)情況下吠昭，用戶實現(xiàn)又不知道一個范圍。

引出k-NN search.

(3)對以上問題的改善

使用定理二胧瓜，我們就不需要再存儲大量的Q-gram了矢棚。

更重要的是，我們可以更快的檢索出軌跡的Q-gram府喳。

例如：

image.png

(4)實現(xiàn)算法

k-NN查詢響應

其中蒲肋，這里的k是k-NN算法中鄰居的范圍定義限制，與EDR中的k沒有關(guān)系。

此算法不引入錯誤的“解雇”：即不把正確的匹配結(jié)果去除掉兜粘。

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——下界

根據(jù)近似三角不等式晋柱，可以獲得EDR(Q, S)的一個下界优构。可以用來被用來去除錯誤的候選項。

(3)算法

image.png

算法說明：

S某一條軌跡（數(shù)據(jù)庫中的）趣斤，Q是當前要尋找匹配軌跡的軌跡俩块。procArray存儲著EDR(Q, Ri)。pmatrix存儲者EDR(Ri, S)浓领。result是最后結(jié)果玉凯，注意，傳入的時候就已經(jīng)有內(nèi)容了联贩。

使用時需要用到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 con?guration of PC. The selection of reference trajectories is query dependent. In our implementation, we simply pick the ?rst maxTriangle trajectories that ?ll up procArray.

(4)對于算法的理解（個人）

這個算法的應用前提是没隘，數(shù)據(jù)庫已經(jīng)查詢到了k-NN響應（能查詢k-NN響應就說明Q在這里就是已知的了）懂扼，并且放到了result里面，procArray預先放的R就是那些軌跡和EDR(Q, Ri)右蒲。

這個方法就是用來去除“錯誤的解雇”和“錯誤的候選者”阀湿。此時考量的S是一條可能是“候選者”但沒有被選中的軌跡，因此瑰妄，此時的pmatrix也就有了陷嘴，是EDR(Ri, S)。

而后根據(jù)近似三角形準則间坐，先計算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確實是真正的候選者彬伦。

因此，后續(xù)應當把realDist插入到procArray中（難道不應該也插入到pmatrix中伊诵？）（原文實在是沒給出R到底是哪里來的单绑，所以只能這么猜測，但是解釋的并不圓滿）

回到上一行自己括號里面的問題：

確實不需要插入到pmatrix中曹宴。

現(xiàn)在的目的是尋找Q的匹配軌跡搂橙，S是當前的可能的真正的候選者，而我們還需要去繼續(xù)追尋下一條可能的候選者軌跡笛坦。

procArray是EDR(Q, Ri)区转，在這個過程中Q是不變的，所以當追尋下一個軌跡的時候版扩，這個procArray還需要繼續(xù)使用废离。

pmatricx是EDR(S, Ri)，當追尋下一條軌跡的時候礁芦，pmatricx是需要重新計算的蜻韭！所以不需要插入。

與procArray同理宴偿，result是下次查詢肯定要被用到的（畢竟是k-NN查詢的結(jié)果Ｏ嫔印）诀豁！所以也需要重寫窄刘！z

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

(5)其他

我們應當清楚舷胜，近似三角形準則是三角形準則的一個弱化版本娩践。

假如軌跡們都有相同的長度活翩，“避免錯誤解雇”的效果將會消失。（估計是因為|S|吧）翻伺。

其他的把非三角形準則轉(zhuǎn)化成三角形準則的方式還有CSE

Given a distance function dist that is de?ned 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 ?nd c.

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

3. Pruning by Histograms

(1). 預備知識

關(guān)鍵詞：Embedding methods.

為了他提高再edit distance條件下的字符串的k-NN查詢效率，嵌入式方法被提了出來吨岭。

方法的主要思想是把字符串 嵌入 到 一個向量空間中拉宗，然后在嵌入后的向量空間中定義一個距離函數(shù)（喵喵喵？）

為了避免錯誤的“解雇”辣辫，embedded space的長度就是字符串的edit distance的下界旦事。（喵喵喵？）

許多的embedding 方法被提了出來急灭，但是只有兩個介紹了“false dismials”姐浮，他們都是用了一樣的方法：

FV & FD & 一個定理

• FV: frequency vector

他們通過映射字符串到字符串的頻率向量（frequency vector）（FV）上，來把字符串轉(zhuǎn)換到多維的整形空間中葬馋。

有以下已經(jīng)被證明的定理：

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

即卖鲤，已經(jīng)證明，兩個串的FV之間的頻率距離（FD）是實際編輯距離的下限畴嘶。

• FD：

定義：

FD of two points u and v in s-dimensional space, FD(u, v), is de?ned 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)算法

• 算法的主要目的

  按照上文介紹的把字符串轉(zhuǎn)換成直方圖的形式悦污，這個算法的目的是把軌跡變成兩維的直方圖铸屉。然后通過直方圖計算直方圖距離。

  以此作為下界切端。

• 把軌跡轉(zhuǎn)換成軌跡的直方圖：

  首先彻坛，給出軌跡的x維度上的最大值和最小值，把[min. max]這段分成τx個相等的子范圍踏枣，每一個子范圍的大小都是e昌屉。對y緯度進行同樣的操作降瞳。這兩個子序列集之間的元素的任意組合都是直方圖的bin华坦。總得組合總數(shù)自然是τx * τy铛碑。其實也就是把x和y方向分成τx * τy個小格马昨，每個小格都是直方圖的一個bin竞帽。然后去數(shù)每個bin中存在的元素數(shù)量（也就是采樣點的數(shù)量）扛施。

• 定義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 de?ned 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轉(zhuǎn)換到HR所需要的最小的步數(shù)。

  假如HR和HS是臨近的鄰居）堆巧，那么R只需要一次edit operation就可以從S轉(zhuǎn)換成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.

• 算法內(nèi)容：

  The algorithm for computing HD between two histograms H R and H S . In procedure CompHisDist, the ?rst for loop is used to compute the difference between two histograms, the second loop (line 4-7) is used to ?nd 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待續(xù)

4.4Combination of three pruning methods

上面討論的三種修建方式都是比較原始的，實際上谍肤，可以做到把三種方法結(jié)合起來使用——use one pruning method to save the computation of the true distance EDR(Q, S) after another.

(1)EDRCombineK-NN

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

先使用直方圖修剪方式懦冰，在使用均值Q-gram過濾器。最后谣沸，在已經(jīng)計算得到的EDR距離的基礎上刷钢，使用近似三角形去除錯誤的候選者。

(2)算法

image.png

五乳附、EXPERIMENTS

實驗部分展示了兩方面的實驗結(jié)果：

• 每一種修剪技術(shù)的效率

• 方法之間的組合

實驗測量的尺度有兩方面

• 加速率：Speedup Ratio

  使用順序掃描的平均時間 和 使用修剪策略時的平均時間只比内地。

  越大越好，越大越快赋除。假如小于1阱缓，那么就要比直接順序搜索，不修剪的效率還要低举农。

  Speedup ratio is de?ned 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，數(shù)據(jù)集S中的沒有被計算EDR的軌跡所占的分數(shù)颁糟。

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

  （沒有被被計算的棱貌，就是節(jié)省下來的計算力熬撩摹）

  Given a k-NN query Q, the pruning power is de?ned 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).

測量參數(shù)：

• k取值從1到20。

  （k是k-NN的k）

• 閾值e婚脱。

  使用多個e探測k-NN算法今魔，選取最符合人類觀察的一個e。

1. Ef?ciency of Pruning by Q-gram Mean Values

(1)數(shù)據(jù)來源

• UCI KDD 的 ASL 數(shù)據(jù)集障贸。

• Kungfu 數(shù)據(jù)集

• Slip 數(shù)據(jù)集

(2)數(shù)據(jù)形式

ASL：710條軌跡错森，長度從60-140

Kungfu：有495條數(shù)據(jù)，記錄著人在打功夫的時候 身體的關(guān)節(jié)的移動數(shù)據(jù)篮洁，每個軌跡長度是640涩维。

Slip：一共495條數(shù)據(jù)，記錄著人跌倒并且試圖站起來的時候的身體關(guān)節(jié)的移動數(shù)據(jù)嘀粱，每個軌跡的長度是400激挪。

(3)測試項目

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

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

• 兩維Q-gram vs 一z維Q-gram

(4)最終結(jié)論

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).

最終測試結(jié)論：

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. Ef?ciency of Pruning by Near Triangle Inequality

假如數(shù)據(jù)庫中的軌跡都只有相同的大小锋叨，那么近似三角形就不能去除錯誤的候選者垄分。

(1)數(shù)據(jù)來源 & 數(shù)據(jù)形式

同Pruning by Q-gram Mean Values。

因為Kungfu和Slip的軌跡的長度都一樣娃磺，所以可以這兩個不會被測試薄湿。

我們用來兩個數(shù)據(jù)集，每個數(shù)據(jù)集有1000個軌跡數(shù)據(jù)偷卧。

而且保證每一個數(shù)據(jù)集的數(shù)據(jù)的長度從30到256不相同豺瘤。

其中一個數(shù)據(jù)集的數(shù)據(jù)的長度 符合 均勻分布。兩一個數(shù)據(jù)集的數(shù)據(jù)長度符合 正態(tài)分布听诸。

(2)測試結(jié)果

可以看出：

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

  主要是因為近似三角形中的|S|實在是太大了桥嗤，導致近似三角形的效果變得更差。找一個相比于|S|更小的數(shù)值仔蝌，可以作為一個將來的工作泛领。

• 近似三角形不等式在滿足均勻分布的數(shù)據(jù)集中，表現(xiàn)的更好敛惊。

  這再一次印證了之前的假設：在數(shù)據(jù)長度越分散和均勻的情況下渊鞋，效果越好。（ASL滿足近似正態(tài)分布）

3. Ef?ciency of Pruning by Histograms

(1)測試變量

• 兩種方法：

  • HSR：histogram sorted scan

  • HSE：histogram sequential scan

• 不同的bin size

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

• bin大小為e的 一維數(shù)據(jù)序列 直方圖

(2)測試數(shù)據(jù)

section 5.1中的所有數(shù)據(jù)

(3)測試結(jié)果

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

• 一維的序列數(shù)據(jù)的修建效率锡宋，要有更大e的比軌跡直方圖表現(xiàn)更好。

  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)測試結(jié)果

對比均值Q-gram的修剪功率和加速比率特恬，我們可以發(fā)現(xiàn)员辩，直方圖方式在移除錯誤的候選者這方面（也就是這兩個指標上）要普遍的強。

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 ?nd that histograms generally perform better than mean value Q-grams on removing false candidates.

4.Efficiency of Combined Methods

(1)測試項目

使用4.4中提出的結(jié)合方法：

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

先使用直方圖修剪方式鸵鸥，在使用均值Q-gram過濾器奠滑。最后，在已經(jīng)計算得到的EDR距離的基礎上妒穴，使用近似三角形去除錯誤的候選者宋税。

直方圖選擇：HRE方式

均值Q-gram過濾器選擇PS2形式

(2)測試數(shù)據(jù)

• NHL數(shù)據(jù)集：國家冰球聯(lián)盟球員的二維軌跡

  • 5000條軌跡

  • 每條軌跡30-256的長度

• 混合數(shù)據(jù)集

  • 32768條軌跡

  • 每條長度60-2000

• 隨機走動軌跡數(shù)據(jù)集

  • 10000條