目錄

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

Abstract

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

一 、Introduction

1. 背景

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

2. 軌跡

一個(gè)移動(dòng)物體的軌跡S的，被定義為一系列的“對(duì)”。例如：

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

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

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

而我們感興趣去的，是許多軌跡的移動(dòng)的形狀。

對(duì)于兩條軌跡，抽樣得出的數(shù)據(jù)（也就是si）非常重要，可以用于測(cè)量?jī)蓚€(gè)軌跡的相似度。而時(shí)間數(shù)據(jù)，經(jīng)?？梢员缓雎?。

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

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

當(dāng)si是一維（例如股票、商品價(jià)格預(yù)測(cè)、銷售量、天氣數(shù)據(jù)、生物醫(yī)學(xué)數(shù)據(jù)）的時(shí)候，已經(jīng)有了許多出色的成果。但是，一維數(shù)據(jù)的許多成果，不能直接被用于軌跡數(shù)據(jù)。因?yàn)槎嗑S數(shù)據(jù)有以下的特點(diǎn)：

• 軌跡數(shù)據(jù)通常是2、3維的，而且通常有不同的長(zhǎng)度。

• 軌跡通常包含離群值、異常點(diǎn)。

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

  對(duì)于以上這種噪聲點(diǎn)的處理，LCSS方法是一個(gè)不錯(cuò)的解決辦法。但是它沒有考慮兩個(gè)軌跡之間的各種gap

  間隙(gap)指的是兩個(gè)軌跡中兩個(gè)識(shí)別的相似分量之間的子軌跡。（沒看懂）（為什么會(huì)導(dǎo)致不準(zhǔn)確？）

• 兩條軌跡，可能在不同的區(qū)域，出現(xiàn)了相似的模式。這主要是因?yàn)閘ocal time shifting：

  由于不同的采樣率或者物體不同的移動(dòng)速度，導(dǎo)致雖然兩個(gè)物體移動(dòng)的軌跡很相似，但是某一些時(shí)間段可能因?yàn)閷?shí)驗(yàn)原因而對(duì)應(yīng)不上。

  對(duì)于以上local time shifting問題，DTW、ERP是好的解決辦法，但是他們對(duì)噪聲很敏感。

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

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

  ED(edit distance是次方法的基礎(chǔ))，EDR通過把距離量化成0、1來實(shí)現(xiàn)噪聲點(diǎn)的抑制，而edit distance這個(gè)方法本身又對(duì)local time shifting情況有所改善（尤其是當(dāng)local timeshifting不是很大的時(shí)候）。當(dāng)local time shifting很大的時(shí)候，EDR的結(jié)果也會(huì)出現(xiàn)偏差。

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

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

  這是因?yàn)椴煌贚CSS、DTW，因?yàn)镋DR將距離轉(zhuǎn)化成了0 1，因此不滿足三角不等式，不能使用傳統(tǒng)的方式來檢索。

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

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

• 展示了如何把這三種方法結(jié)合起來，提升準(zhǔn)確率。

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

二、Background

1. 范圍定義——?jiǎng)澏ǖ蕉S

為了簡(jiǎn)單和不失一般性，把軌跡設(shè)定為二維的（文中所有的定義、定理都可以被擴(kuò)展到三維或者更高維度），因此

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

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

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

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

可以對(duì)軌跡S進(jìn)行歸一化：

u(x),u(y)是其兩個(gè)唯獨(dú)的均值

σ(x),σ(y)是兩個(gè)唯獨(dú)的方差

image.png

歸一化很推薦的，因?yàn)闅w一化使得兩個(gè)軌跡之間的距離對(duì)于空間縮放和移位是不變的。（不太懂）（空間縮放能明白，這個(gè)位移沒懂）

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

3. 符號(hào)說明

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

image.png

• Eu、DTW、ERP對(duì)噪聲敏感

• Eu不能處理local time shifting和長(zhǎng)度不一致的軌跡

• LCSS可以處理有噪聲的軌跡，但是它是一個(gè)非常“粗糙的”的算法。（gaps）（it does not differentiate trajectories with similar common subsequences but different sizes of gaps in between.）

三、EDR

EDR比 已存在的 測(cè)量?jī)蓚€(gè)軌跡之間相似度的 方法 更加的魯棒、精確。

1. Edit Distance on Real Sequences

Edit distacne(ED)是本方法的基礎(chǔ)：

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.

但是由于軌跡不是字符串，也不是一維的，因此，合理的定義兩個(gè)軌跡的元素對(duì)“匹配”這一概念，就顯得十分重要了。

(1).兩個(gè)定義

• Defination 1: match

  假如兩個(gè)軌跡的兩個(gè)元素ri和sj相互匹配，當(dāng)且僅當(dāng)他們滿足：

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

  e是匹配閾值，此時(shí)可以寫作match(ri, sj) = true

• Defination 2: EDR數(shù)值的計(jì)算公式

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

  image.png

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

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

  例如：

  假如(t1, 0.9), (t2, 1.2)。e=1的時(shí)候，這兩個(gè)點(diǎn)（軌跡）相匹配，EDR是0。但是實(shí)際的edit distance是1。但是隨著e的減少（即精度的增加，EDR越來越去趨近于實(shí)際的edit distance）

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

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

• “最小的 把 R 變成 S ”的這個(gè)過程，自然也就賦予了EDR處理local time shifting的能力。當(dāng)時(shí)，假如shifting太大了，最后的EDR結(jié)果也會(huì)很大。

• 對(duì)于不匹配的，subcost = 1。這其實(shí)是一個(gè)懲罰手段（而LCSS中選擇直接跳過），因此EDR又要比LCSS更加準(zhǔn)確。

2. Evaluation of EDR

總之就是好好好。

四、Efficient Trajectory Retrieval Using EDR

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

其實(shí)基本上所有的對(duì)噪聲有抑制作用的算法，通常都不符合三角準(zhǔn)則。

另外，心理學(xué)研究表明，人類的相似性判斷也不符合三角準(zhǔn)則。

因此，問題現(xiàn)在就在于如何提升相似性搜索的檢索效率。每次EDR操作的時(shí)空復(fù)雜度是O(m×n)，m和n是兩個(gè)軌跡的長(zhǎng)度。（DTW、ERP、LCSS都是二次的）

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

1. Pruning by Mean Value Q-gram

(1)預(yù)備知識(shí)：

近似字符串匹配問題：

對(duì)于一個(gè)長(zhǎng)度為n的字符串文本，和一個(gè)長(zhǎng)度為m的模式（m<n)，檢索出所有的子字符串，這些字符串需要滿足他們到這個(gè)模式的edit distance最大是k。

Q-gram：

Q-gram是字符串S的一個(gè)長(zhǎng)度為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長(zhǎng)度分別是m和n，假如P和S的edit distance在k之內(nèi)，那么一定滿足，他們有至少p = max(m, n) - q + 1 - kq個(gè)共同的Q-gram.

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

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

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

定義 3：

給定兩個(gè)序列R和Q的兩個(gè)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))] ，當(dāng)說r匹配s的時(shí)候，當(dāng)且僅當(dāng)r的每一個(gè)元素對(duì)應(yīng)匹配s的每一個(gè)元素。（Q-gram一定是q長(zhǎng)度啦）

定理2：

對(duì)于給定的閾值e，假如兩個(gè)Q-gram，r和s（與定義3中相同）匹配，那么他們的均值也匹配。

image.png

Q-gram的均值，就是一個(gè)q緯度“元包”，每一個(gè)“元包”具體是多少維度，主要是要看軌跡采樣點(diǎn)的緯度。例如(1,2,3,4,5,6)的q=3時(shí)的Q-gram就是三維元包，元包是一維的（實(shí)際上就是(3, 4, 5)

但是對(duì)于二維元包：S=((1,2),(3,4),(5,6),(7,8),(9,10))的q=3時(shí)的Q-gram的均值就是三維元包，元包是二維的（實(shí)際上就是((3, 4), (5, 6), (7, 8))

而每一個(gè)Q-gram適合均值一樣形式的。

(2) 存在的問題

• 每一個(gè)軌跡的Q-gram都需要?jiǎng)e存儲(chǔ)的話，那么存儲(chǔ)消耗非常高。

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

• 直接應(yīng)用Q-gram還會(huì)導(dǎo)致維度災(zāi)難。

最終，定理一只能用于范圍查詢（？？？），而在大多數(shù)情況下，用戶實(shí)現(xiàn)又不知道一個(gè)范圍。

引出k-NN search.

(3)對(duì)以上問題的改善

使用定理二，我們就不需要再存儲(chǔ)大量的Q-gram了。

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

例如：

image.png

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

k-NN查詢響應(yīng)

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

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

2. Pruning by Near Triangle Inequality

(1) 近似三角不等式

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

對(duì)于給定的三條軌跡Q，S，R，有如下不等式：

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

其中，|S|是軌跡S的長(zhǎng)度。

移項(xiàng)得到：

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

R可以當(dāng)作是一個(gè)中間臨時(shí)軌跡，EDR(Q, R), EDR(S, R)都可以直接算出。

(2)lower bound——下界

根據(jù)近似三角不等式，可以獲得EDR(Q, S)的一個(gè)下界。可以用來被用來去除錯(cuò)誤的候選項(xiàng)。

(3)算法

image.png

算法說明：

S某一條軌跡（數(shù)據(jù)庫(kù)中的），Q是當(dāng)前要尋找匹配軌跡的軌跡。procArray存儲(chǔ)著EDR(Q, Ri)。pmatrix存儲(chǔ)者EDR(Ri, S)。result是最后結(jié)果，注意，傳入的時(shí)候就已經(jīng)有內(nèi)容了。

使用時(shí)需要用到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.

預(yù)選的軌跡應(yīng)該在查詢時(shí)刻有查詢引擎準(zhǔn)備好，也就是說，近似三角形準(zhǔn)則并不是一個(gè)完善的方法，不太同于4.1，甚至可以作為4.1的一個(gè)子部分。maxTriangle越大，說明下限越高，說明修剪的越好。

因此實(shí)際應(yīng)用時(shí)的需要如下：

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)對(duì)于算法的理解（個(gè)人）

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

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

而后根據(jù)近似三角形準(zhǔn)則，先計(jì)算maxPruneDist——EDR(Q, S)的下界，計(jì)算的中介就是此時(shí)的procArray和pmatrix中的候選者們。假如此下界<此時(shí)最大的k-NN距離，那么說明這個(gè)軌跡可能是真正的候選者。但是近似三角形準(zhǔn)則畢竟只是一個(gè)弱化版本的三角形準(zhǔn)則，其限制范圍本身就是被弱化的，非常有限。所以，之后要再去計(jì)算EDR(Q, S)——真實(shí)的EDR距離。

這是因?yàn)椋珽DR(Q, S)大于這個(gè)下界，當(dāng)這個(gè)下界小于k-NN的最大距離，并不代表EDR(Q, S)就比k-NN距離小。

假如此距離確實(shí)比當(dāng)前的realDist，假如此時(shí)的realDist確實(shí)要比bestSoFar(k-NN的最大距離)更好（?。?，那么說明這個(gè)軌跡S確實(shí)是真正的候選者。

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

回到上一行自己括號(hào)里面的問題：

確實(shí)不需要插入到pmatrix中。

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

procArray是EDR(Q, Ri)，在這個(gè)過程中Q是不變的，所以當(dāng)追尋下一個(gè)軌跡的時(shí)候，這個(gè)procArray還需要繼續(xù)使用。

pmatricx是EDR(S, Ri)，當(dāng)追尋下一條軌跡的時(shí)候，pmatricx是需要重新計(jì)算的！所以不需要插入。

與procArray同理，result是下次查詢肯定要被用到的（畢竟是k-NN查詢的結(jié)果?。?！所以也需要重寫！z

然后把此時(shí)的S和realDist插入到result中。

(5)其他

我們應(yīng)當(dāng)清楚，近似三角形準(zhǔn)則是三角形準(zhǔn)則的一個(gè)弱化版本。

假如軌跡們都有相同的長(zhǎng)度，“避免錯(cuò)誤解雇”的效果將會(huì)消失。（估計(jì)是因?yàn)閨S|吧）。

其他的把非三角形準(zhǔn)則轉(zhuǎn)化成三角形準(zhǔ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 .

但是我們不使用這種方法，因?yàn)椋?/p>

• 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). 預(yù)備知識(shí)

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

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

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

為了避免錯(cuò)誤的“解雇”，embedded space的長(zhǎng)度就是字符串的edit distance的下界。（喵喵喵？）

許多的embedding 方法被提了出來，但是只有兩個(gè)介紹了“false dismials”，他們都是用了一樣的方法：

FV & FD & 一個(gè)定理

• 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)證明，兩個(gè)串的FV之間的頻率距離（FD）是實(shí)際編輯距離的下限。

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

咱們這里比較的是兩個(gè)字符串的FVs的距離，所以兩個(gè)字符串的FVs之間的ED距離又稱作FD？？？（我怎么覺得有點(diǎn)奇怪）

使用FV、FD的一些特點(diǎn)的分析

FV顯然是一維的直方圖（也就是柱狀圖），他的每一個(gè)bin都是字母表里的字母。

(2)算法

• 算法的主要目的

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

  以此作為下界。

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

  首先，給出軌跡的x維度上的最大值和最小值，把[min. max]這段分成τx個(gè)相等的子范圍，每一個(gè)子范圍的大小都是e。對(duì)y緯度進(jìn)行同樣的操作。這兩個(gè)子序列集之間的元素的任意組合都是直方圖的bin?？偟媒M合總數(shù)自然是τx * τy。其實(shí)也就是把x和y方向分成τx * τy個(gè)小格，每個(gè)小格都是直方圖的一個(gè)bin。然后去數(shù)每個(gè)bin中存在的元素?cái)?shù)量（也就是采樣點(diǎn)的數(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分別是兩個(gè)軌跡H和S的直方圖。那么HD(HR, HS)定義成：

  通過每一步移動(dòng)一個(gè)臨近點(diǎn)，把從HR轉(zhuǎn)換到HR所需要的最小的步數(shù)。

  假如HR和HS是臨近的鄰居），那么R只需要一次edit operation就可以從S轉(zhuǎn)換成R。

• 定義5：克服兩個(gè)直方圖靠近的邊緣點(diǎn)之間的匹配問題：

  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

上面討論的三種修建方式都是比較原始的，實(shí)際上，可以做到把三種方法結(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)計(jì)算得到的EDR距離的基礎(chǔ)上，使用近似三角形去除錯(cuò)誤的候選者。

(2)算法

image.png

五、EXPERIMENTS

實(shí)驗(yàn)部分展示了兩方面的實(shí)驗(yàn)結(jié)果：

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

• 方法之間的組合

實(shí)驗(yàn)測(cè)量的尺度有兩方面

• 加速率：Speedup Ratio

  使用順序掃描的平均時(shí)間 和 使用修剪策略時(shí)的平均時(shí)間只比。

  越大越好，越大越快。假如小于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

  修剪功率（不知道是不是這么翻譯）指的是，對(duì)于給定的k-NN序列Q，數(shù)據(jù)集S中的沒有被計(jì)算EDR的軌跡所占的分?jǐn)?shù)。

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

  （沒有被被計(jì)算的，就是節(jié)省下來的計(jì)算力?。?/p>

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

測(cè)量參數(shù)：

• k取值從1到20。

  （k是k-NN的k）

• 閾值e。

  使用多個(gè)e探測(cè)k-NN算法，選取最符合人類觀察的一個(gè)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條軌跡，長(zhǎng)度從60-140

Kungfu：有495條數(shù)據(jù)，記錄著人在打功夫的時(shí)候 身體的關(guān)節(jié)的移動(dòng)數(shù)據(jù)，每個(gè)軌跡長(zhǎng)度是640。

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

(3)測(cè)試項(xiàng)目

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

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

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

(4)最終結(jié)論

image.png

四個(gè)測(cè)試方法：

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

最終測(cè)試結(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)

以下是文中沒有詳細(xì)說明的第二種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).

• 詳細(xì)算法如下：

image.png

2. Ef?ciency of Pruning by Near Triangle Inequality

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

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

同Pruning by Q-gram Mean Values。

因?yàn)镵ungfu和Slip的軌跡的長(zhǎng)度都一樣，所以可以這兩個(gè)不會(huì)被測(cè)試。

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

而且保證每一個(gè)數(shù)據(jù)集的數(shù)據(jù)的長(zhǎng)度從30到256不相同。

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

(2)測(cè)試結(jié)果

可以看出：

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

  主要是因?yàn)榻迫切沃械膢S|實(shí)在是太大了，導(dǎo)致近似三角形的效果變得更差。找一個(gè)相比于|S|更小的數(shù)值，可以作為一個(gè)將來的工作。

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

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

3. Ef?ciency of Pruning by Histograms

(1)測(cè)試變量

• 兩種方法：

  • HSR：histogram sorted scan

  • HSE：histogram sequential scan

• 不同的bin size

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

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

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

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

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

對(duì)比均值Q-gram的修剪功率和加速比率，我們可以發(fā)現(xiàn)，直方圖方式在移除錯(cuò)誤的候選者這方面（也就是這兩個(gè)指標(biāo)上）要普遍的強(qiáng)。

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)測(cè)試項(xiàng)目

使用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)計(jì)算得到的EDR距離的基礎(chǔ)上，使用近似三角形去除錯(cuò)誤的候選者。

直方圖選擇：HRE方式

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

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

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

  • 5000條軌跡

  • 每條軌跡30-256的長(zhǎng)度

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

  • 32768條軌跡

  • 每條長(zhǎng)度60-2000

• 隨機(jī)走動(dòng)軌跡數(shù)據(jù)集

  • 10000條