技術(shù)領(lǐng)域

本發(fā)明屬于地理信息分析處理技術(shù)領(lǐng)域，涉及一種在大規(guī)模軌跡數(shù)據(jù)集上基于Fréchet(費(fèi)雷歇)距離閾值的軌跡相似性快速匹配方法。

背景技術(shù)

隨著移動(dòng)互聯(lián)網(wǎng)絡(luò)的深入普及，移動(dòng)設(shè)備上的各類傳感器一刻不停地記錄著攜帶者的各類信息，其中人員或設(shè)備隨著時(shí)間推移的位置變化軌跡是最為常見、也是最具應(yīng)用價(jià)值的數(shù)據(jù)之一，針對(duì)軌跡數(shù)據(jù)的處理與分析也成為地理信息和數(shù)據(jù)挖掘領(lǐng)域的熱點(diǎn)問題。在這當(dāng)中，軌跡的相似性度量和相似性查詢是很多分析過程的基礎(chǔ)。由于軌跡距離的絕對(duì)值隨著定義的不同具有不同的實(shí)際意義，在實(shí)際應(yīng)用中往往只是起到一個(gè)過濾或者分類的作用，并且實(shí)際對(duì)象的軌跡數(shù)據(jù)不可避免地存在噪聲擾動(dòng)，所以大多數(shù)情況下只要能夠得到給定距離閾值內(nèi)的查詢結(jié)果集即可滿足應(yīng)用需求。

軌跡的相似性查詢?cè)谌藗兊纳a(chǎn)生活、相關(guān)部門的政策決策以及商業(yè)公司的市場(chǎng)調(diào)查、產(chǎn)品推廣中有很多有價(jià)值的應(yīng)用。例如，查詢某區(qū)域內(nèi)具有相似作息規(guī)律的人員和頻繁行動(dòng)軌跡，可以獲得生活習(xí)慣相近的人群，政府部門可以用來作為政策或基礎(chǔ)設(shè)施建設(shè)方案的參考，商業(yè)部門可以用作精準(zhǔn)的廣告投放或產(chǎn)品設(shè)計(jì)的依據(jù)。在宇宙天文學(xué)領(lǐng)域，通過天文望遠(yuǎn)鏡可獲得大量星軌數(shù)據(jù)，只要對(duì)其進(jìn)行一定距離閾值的搜索過濾，即可初步得到星系的大致劃分和各星體的星系歸屬以及星系內(nèi)星體的相對(duì)結(jié)構(gòu)。但由于軌跡相似性計(jì)算的復(fù)雜性和實(shí)際軌跡數(shù)據(jù)集的龐大，現(xiàn)有算法的效率難以滿足要求。

軌跡的相似性查詢包含兩個(gè)層面的問題，一是軌跡距離的度量的選擇，二是查找距離閾值內(nèi)軌跡的算法。軌跡數(shù)據(jù)不同于簡(jiǎn)單的線數(shù)據(jù)，其前后點(diǎn)之間有嚴(yán)格的次序關(guān)系，所以對(duì)軌跡距離的度量有很多種方案，包括最大距離、最小距離、平均距離、Hausdorff距離、Fréchet距離、動(dòng)態(tài)時(shí)間規(guī)整(Dynamic Time Warping,DTW)、最長(zhǎng)公共子序列(Longest Common Subsequence，LCSS)、時(shí)間規(guī)整編輯距離(Time Warp Edit Distance,TWED)等。研究表明，F(xiàn)réchet距離定義中包含了軌跡點(diǎn)間的時(shí)序關(guān)系，計(jì)算過程考慮了軌跡內(nèi)部的節(jié)點(diǎn)結(jié)構(gòu)，可以更加精確地描述軌跡間的相似程度，在軌跡出現(xiàn)回退、環(huán)、交錯(cuò)等情況時(shí)不會(huì)出現(xiàn)度量值失真，所以Fréchet距離度量的描述能力更強(qiáng)，更適合作為衡量軌跡相似性的度量。

精確Fréchet距離的計(jì)算是NP難問題，理想的連續(xù)曲線Fréchet距離求解不存在多項(xiàng)式復(fù)雜度的方法，只能先將連續(xù)曲線采樣后折線化再進(jìn)行計(jì)算。Godau于1991年提出一種描述兩條軌跡距離關(guān)系的圖，稱為Free-Space Diagram，在此基礎(chǔ)上，提出一種對(duì)折線軌跡的計(jì)算方法，即逐步縮小ε的值，直到達(dá)到臨界值，使得恰好有一條通路可以貫穿(0,0)和(p,q)，其中，p、q分別為兩條軌跡的長(zhǎng)度(下同)，從符合條件的ε中取最小值，即為兩軌跡的近似Fréchet距離，計(jì)算復(fù)雜度為Ο((p²q+pq²)logpq)；Alt和Godau于1995年一起改進(jìn)了算法，優(yōu)化了尋找ε的策略，將計(jì)算出兩個(gè)軌跡的Fréchet距離的時(shí)間復(fù)雜度降為Ο(pqlogpq²)。

Eiter與Mannila于1994年提出了一種Fréchet距離的變種版本，稱為離散Fréchet距離，即先將軌跡近似成有序的離散點(diǎn)，再計(jì)算離散點(diǎn)對(duì)之間的配對(duì)距離，作為連續(xù)Fréchet距離的近似，并證明了離散Fréchet距離是連續(xù)Fréchet距離的上界，其計(jì)算時(shí)間復(fù)雜度僅為O(pq)，這種簡(jiǎn)化模型更加貼合實(shí)際中的軌跡數(shù)據(jù)，在幾乎不損失度量效果的情況下降低了計(jì)算復(fù)雜度，所以之后的相關(guān)Fréchet算法研究大多也是基于離散Fréchet距離設(shè)計(jì)的，在這種情況下Free-Space圖簡(jiǎn)化為軌跡點(diǎn)之間的距離矩陣。Agarwal使用有限狀態(tài)機(jī)方法尋找距離矩陣的貫通路徑，推導(dǎo)出可在O(pqlog(log q)/log²q)復(fù)雜度內(nèi)判斷出Fréchet距離上界，進(jìn)而計(jì)算出Fréchet距離值。Aronov則提出先對(duì)軌跡數(shù)據(jù)進(jìn)行簡(jiǎn)化，減少描述軌跡的點(diǎn)個(gè)數(shù)，再計(jì)算其Fréchet距離衡量軌跡間的相似度，降低了計(jì)算量。Driemel引入一種新型逼近簡(jiǎn)化軌跡類型c-packed曲線，利用此類曲線提出一種簡(jiǎn)單實(shí)用的(1+ε)近似方法，以在接近線性復(fù)雜度的時(shí)間內(nèi)計(jì)算出軌跡的近似Fréchet距離。Har-Peled針對(duì)一種Fréchet距離的變種：同倫Fréchet距離(homotopic>

Sook Yoon針對(duì)Fréchet距離計(jì)算復(fù)雜度高的問題，提出一種卷積神經(jīng)網(wǎng)絡(luò)(Convolutional Neural Network,CNN)結(jié)構(gòu)映射兩條軌跡的距離矩陣，可以充分利用CNN的并行計(jì)算能力，將比較兩條軌跡與參考軌跡的Fréchet距離大小的復(fù)雜度降低到O(max(p,q)-1)。Buchin對(duì)兩條軌跡的距離矩陣進(jìn)行單元?jiǎng)澐郑瑯?gòu)建了一個(gè)樹狀查找表(lookup table)加快遍歷Free Space的效率，將判斷離散Fréchet距離是否在閾值內(nèi)的復(fù)雜度降到O(pq(loglogq)²/logq)。Gheibi針對(duì)可回退的軌跡，提出基于變形Free-space>

Bringmann對(duì)近二十年關(guān)于計(jì)算Fréchet距離以及其變種的算法復(fù)雜度進(jìn)行了總結(jié)，并在強(qiáng)指數(shù)時(shí)間假設(shè)條件(Strong Exponential Time Hypothesis,SETH)下，對(duì)Fréchet距離的計(jì)算復(fù)雜度進(jìn)行了理論分析與假設(shè)推導(dǎo)，指出該問題在1.001的誤差范圍內(nèi)不存在強(qiáng)二次函數(shù)復(fù)雜度解法。

從現(xiàn)有技術(shù)中可以看出，對(duì)Fréchet距離的研究主要集中于對(duì)原始定義的簡(jiǎn)化和設(shè)計(jì)加速計(jì)算的數(shù)據(jù)結(jié)構(gòu)方面，但大多止步于理論設(shè)計(jì)和推導(dǎo)。

發(fā)明內(nèi)容

為解決上述技術(shù)問題，本發(fā)明針對(duì)軌跡Fréchet距離的閾值過濾問題提出一種快速搜索與匹配方法——排序覆蓋判決(OCJ：Ordered Coverage Judge)方法，通過基于軌跡特征的過濾和順序覆蓋判斷兩步操作，快速得到與目標(biāo)軌跡的Fréchet距離在設(shè)定閾值以內(nèi)的結(jié)果集，并且對(duì)方法進(jìn)行了并行優(yōu)化，提升了效率。

為更好地闡述本發(fā)明的技術(shù)方案，將問題中涉及到的相關(guān)名詞和概念解釋如下：

Fréchet距離定義：

其中μ:A→B，是指從軌跡A上的點(diǎn)到軌跡B上的點(diǎn)的一對(duì)一連續(xù)映射。如圖1所示，該圖為采用Fréchet距離度量的示意圖。作為軌跡相似性的度量，F(xiàn)réchet距離定義中包含了軌跡點(diǎn)間的時(shí)序關(guān)系，計(jì)算過程考慮了軌跡內(nèi)部的節(jié)點(diǎn)結(jié)構(gòu)，可以更加精確地描述軌跡間的相似程度，在軌跡出現(xiàn)節(jié)點(diǎn)回退、節(jié)點(diǎn)環(huán)、方向交錯(cuò)等情況時(shí)，用其他距離度量會(huì)得到一個(gè)過大或過小的值，或者對(duì)不同形狀軌跡的相似性表達(dá)質(zhì)量不穩(wěn)定，而Fréchet距離則在直觀上更符合軌跡實(shí)際的相似情況，且穩(wěn)定性更高，不會(huì)出現(xiàn)距離失真的情況。

目標(biāo)軌跡：作為距離判斷基準(zhǔn)的一條軌跡，在實(shí)際應(yīng)用中指需要尋找與其Fréchet距離在給定閾值以內(nèi)的其他軌跡，具體可以為各類傳感器記錄或探測(cè)到的移動(dòng)目標(biāo)的位置軌跡，如車輛、行人在一段時(shí)間內(nèi)的定位數(shù)據(jù)，根據(jù)實(shí)際數(shù)據(jù)采集情況，目標(biāo)軌跡數(shù)據(jù)一般為間隔一定的、具有時(shí)間屬性的離散位置點(diǎn)序列。目標(biāo)軌跡的集合稱為目標(biāo)軌跡集；

候選軌跡：待判斷與目標(biāo)軌跡距離的軌跡，同樣可以為各類傳感器記錄或探測(cè)到的移動(dòng)目標(biāo)的位置軌跡，具體形式也是間隔一定的、具有時(shí)間屬性的離散位置點(diǎn)序列。候選軌跡的集合稱為候選軌跡集；

總問題：在初始的候選軌跡數(shù)據(jù)集中找出與目標(biāo)軌跡的Fréchet距離在給定閾值ε之內(nèi)的軌跡；

子問題：判斷兩個(gè)軌跡的Fréchet距離是否在給定閾值ε之內(nèi)；

距離：未特別注明的距離指普通距離，即指笛卡爾空間下的歐幾里得距離；

節(jié)點(diǎn)：構(gòu)成軌跡的有序離散點(diǎn)，由二維或三維坐標(biāo)和該點(diǎn)在軌跡中的時(shí)序組成；

軌跡長(zhǎng)度：軌跡包含的節(jié)點(diǎn)個(gè)數(shù)；

片段(Seg)：相鄰兩個(gè)點(diǎn)構(gòu)成的有向線段，多個(gè)片段首尾相連即構(gòu)成軌跡；

連接(Link)：分別屬于兩條軌跡的兩個(gè)節(jié)點(diǎn)可以建立連接，當(dāng)且僅當(dāng)此連接關(guān)系與其他連接關(guān)系不違反軌跡點(diǎn)的時(shí)序關(guān)系，即時(shí)序位于后面的點(diǎn)，其連接點(diǎn)在時(shí)間線上也位于靠后的位置，此即為Fréchet距離考慮軌跡點(diǎn)時(shí)序關(guān)系的表現(xiàn)。一般地，認(rèn)為軌跡A的首尾點(diǎn)在軌跡B上的連接點(diǎn)就是其首尾點(diǎn)(即表示兩條軌跡的首尾點(diǎn)互為連接點(diǎn))；

有效連接(valid link)：可以建立連接的兩個(gè)節(jié)點(diǎn)的距離小于給定閾值ε，則稱此連接方式為有效連接；

覆蓋(coverage)：對(duì)于軌跡A中的某個(gè)節(jié)點(diǎn)a，軌跡B上有相應(yīng)的一個(gè)或多個(gè)節(jié)點(diǎn)b_i，b_i+1，b_i+2，…，b_j可以與a建立有效連接(其中0≤i≤j≤L_B，L_B為B的軌跡長(zhǎng)度)。

本發(fā)明的核心思想是在基于軌跡特征進(jìn)行預(yù)過濾的基礎(chǔ)上，以給定閾值依次計(jì)算目標(biāo)軌跡的每一個(gè)節(jié)點(diǎn)在候選軌跡上的覆蓋范圍，如果其覆蓋范圍是連續(xù)且有序的，且其并集可以涵蓋候選軌跡中的所有節(jié)點(diǎn)，則候選軌跡符合查詢條件，即兩條軌跡的Fréchet距離在給定閾值范圍內(nèi)。具體技術(shù)方案如下：

一種基于Fréchet距離閾值的軌跡相似性快速匹配方法，包括以下步驟：

(S1)設(shè)初始的候選軌跡集為T₀，在T₀上進(jìn)行基于軌跡首尾點(diǎn)的過濾操作，得到處理后的候選軌跡集T₁；

(S2)在T₁上進(jìn)行基于軌跡最小外包框(Minimum>2；

(S3)在T₂上進(jìn)行基于軌跡緩沖區(qū)(Buffer)的過濾操作，得到處理后的候選軌跡集T₃；Buffer表示緩沖區(qū)，具體指在空間對(duì)象周圍建立的一定寬度的多邊形。

(S4)對(duì)T₃進(jìn)行精確Fréchet距離閾值過濾處理，輸出最終結(jié)果集。

進(jìn)一步地，所述步驟(S1)中的基于軌跡首尾點(diǎn)的過濾操作具體過程為：

(S11)遍歷初始的候選軌跡集T₀，分別提取候選軌跡集T₀中每條軌跡的第一個(gè)位置點(diǎn)和最后一個(gè)位置點(diǎn)，所有第一個(gè)位置點(diǎn)組成候選軌跡的首點(diǎn)集合，所有最后一個(gè)位置點(diǎn)組成尾點(diǎn)集合，然后分別對(duì)首點(diǎn)集合和尾點(diǎn)集合建立空間R樹索引；

(S12)提取目標(biāo)軌跡的首點(diǎn)位置坐標(biāo)和尾點(diǎn)位置坐標(biāo)，并基于所述首點(diǎn)位置坐標(biāo)、尾點(diǎn)位置坐標(biāo)向四周擴(kuò)展給定的閾值ε，分別生成以目標(biāo)軌跡的首點(diǎn)、尾點(diǎn)為中心的，以2ε為邊長(zhǎng)的首、尾正方形查詢框；

(S13)使用步驟(S11)中建立的兩個(gè)空間R樹索引，分別以步驟(S12)中得到的首、尾正方形查詢框進(jìn)行空間范圍查詢，得到命中的所有軌跡組成候選軌跡集T₁。

進(jìn)一步地，所述步驟(S2)中最小外包框過濾的具體過程為：

(S21)求取目標(biāo)軌跡的最小外包框，遍歷目標(biāo)軌跡上的位置點(diǎn)，保留處于左上角和右下角的點(diǎn)坐標(biāo)，以左上角、右下角坐標(biāo)為端點(diǎn)確定的矩形空間范圍即最小外包框；

(S22)將目標(biāo)軌跡的最小外包框MBR向外擴(kuò)展ε，形成待查擴(kuò)展區(qū)eMBR；

(S23)判斷所述步驟S13中得到的候選軌跡集T₁中的候選軌跡是否位于eMBR內(nèi)部，保留軌跡位于eMBR內(nèi)部的候選軌跡，所有位于eMBR內(nèi)部的候選軌跡組成候選軌跡集T₂。

進(jìn)一步地，所述步驟(S3)中基于軌跡緩沖區(qū)過濾的具體過程為：

(S31)以給定閾值ε為半徑求取目標(biāo)軌跡緩沖區(qū)，首先將目標(biāo)軌跡位置點(diǎn)按順序連接形成線對(duì)象，然后對(duì)所述線對(duì)象求取緩沖區(qū)，即目標(biāo)軌跡緩沖區(qū)；

(S32)判斷T₂中的候選軌跡是否位于目標(biāo)軌跡緩沖區(qū)內(nèi)部，保留軌跡位于目標(biāo)軌跡緩沖區(qū)內(nèi)部的候選軌跡，所有位于目標(biāo)軌跡緩沖區(qū)內(nèi)部的候選軌跡組成候選軌跡集T₃。

進(jìn)一步地，所述步驟(S4)中精確Fréchet距離閾值過濾處理的具體過程為：

(S41)記P_i為目標(biāo)軌跡的第i個(gè)位置點(diǎn)，P_i+1為目標(biāo)軌跡的第i+1個(gè)位置點(diǎn)，從目標(biāo)軌跡的第一個(gè)點(diǎn)i＝1開始處理；

(S42)分別對(duì)候選軌跡集T3中的每一條候選軌跡進(jìn)行有效連接搜索，即遍歷候選軌跡的位置點(diǎn)，判斷其是否與P_i、P_i+1形成有效連接，計(jì)算P_i的覆蓋范圍得到C_i，C_i包含的m個(gè)位置點(diǎn)序號(hào)為P_i+1的覆蓋范圍得到C_i+1，C_i+1包含的n個(gè)位置點(diǎn)為所述有效連接定義為兩條軌跡中建立連接的兩個(gè)節(jié)點(diǎn)的距離小于給定閾值ε，則稱為有效連接；符號(hào)表示位置點(diǎn)序號(hào)為…，表示位置點(diǎn)序號(hào)為：…，m，n為整數(shù)。

(S43)若C_i+1與C_i在候選軌跡上形成順序覆蓋關(guān)系，即C_i+1的起始點(diǎn)位于C_i的范圍內(nèi)或緊鄰C_i的結(jié)束點(diǎn)，用位置點(diǎn)符號(hào)表示為則i自增1，返回步驟S42；若C_i+1與C_i所包括的位置點(diǎn)在候選軌跡上不連續(xù)或者不能順序覆蓋候選軌跡，即C_i+1的起始點(diǎn)與C_i包含的位置點(diǎn)集之間形成回退或間隔，用位置點(diǎn)符號(hào)表示為或則搜索終止，輸出軌跡不匹配的判斷結(jié)果；

(S44)當(dāng)P_i取值為目標(biāo)軌跡的最后一個(gè)點(diǎn)，且覆蓋范圍的并集涵蓋整個(gè)候選軌跡，則輸出軌跡匹配判斷結(jié)果，否則輸出軌跡不匹配的判斷結(jié)果。目標(biāo)軌跡數(shù)據(jù)為間隔一定的、具有時(shí)間屬性的離散位置點(diǎn)序列，目標(biāo)軌跡位置點(diǎn)總數(shù)根據(jù)實(shí)際情況確定，i的取值范圍為1至位置點(diǎn)總數(shù)。

上述表明步驟(S4)中包含多個(gè)子問題，即需要以目標(biāo)軌跡為基準(zhǔn)，對(duì)經(jīng)過(S1)、(S2)、(S3)三輪過濾剩下的候選軌跡集T₃中的每一個(gè)候選軌跡采用本發(fā)明提出的OCJ方法進(jìn)行精確的Fréchet距離閾值判斷。

進(jìn)一步地，實(shí)現(xiàn)過程中，有效連接搜索與順序覆蓋判斷是同步進(jìn)行的，在遍歷到某一節(jié)點(diǎn)時(shí)，發(fā)現(xiàn)覆蓋范圍與上一節(jié)點(diǎn)的結(jié)果不連續(xù)，此時(shí)即可終止搜索，得到否定的查詢結(jié)果，而不必計(jì)算余下節(jié)點(diǎn)的覆蓋范圍。

進(jìn)一步地，某一節(jié)點(diǎn)可能會(huì)計(jì)算出多段不連續(xù)的覆蓋范圍，假定為兩段seg1、seg2，而下一節(jié)點(diǎn)的有效連接可能恰好從seg1和seg2間的空隔區(qū)開始，且滿足從seg1繼續(xù)的順序覆蓋，而不滿足從seg2繼續(xù)的順序覆蓋，這時(shí)會(huì)判斷為不滿足匹配條件，這種情況在軌跡形狀較為扭曲時(shí)可能出現(xiàn)，而實(shí)際上兩條軌跡仍然可能符合匹配判斷條件。該方法可以只保存每個(gè)節(jié)點(diǎn)的第一段有效連接對(duì)下一節(jié)點(diǎn)的順序覆蓋進(jìn)行判斷，但為了提高搜索效率，使覆蓋范圍能更快地向后延伸，有必要對(duì)OCJ方法進(jìn)行改進(jìn)。通過增加一個(gè)棧結(jié)構(gòu)，將當(dāng)前節(jié)點(diǎn)的每一段有效覆蓋范圍都?jí)簵?，?dāng)某一節(jié)點(diǎn)a無法正常進(jìn)行順序覆蓋時(shí)，就從棧中彈出上一節(jié)點(diǎn)的上一個(gè)有效覆蓋范圍，重新對(duì)a進(jìn)行搜索，只有當(dāng)棧為空時(shí)，才判定為不滿足查詢條件。

為更好的理解本發(fā)明，現(xiàn)將有關(guān)原理作進(jìn)一步說明：根據(jù)Fréchet距離的定義，需要為軌跡目標(biāo)軌跡A和候選軌跡B找到一種連接方式，使得A和B中的所有點(diǎn)都有相應(yīng)的連接點(diǎn)。理論上兩條軌跡有無數(shù)種連接方式，在每種連接方式中，總有一條連接的長(zhǎng)度最長(zhǎng)，記為Dlink，而Fréchet距離，就是所有連接方式中Dlink的最小值。這個(gè)問題轉(zhuǎn)化為判斷目標(biāo)軌跡的有效連接范圍是否能夠有序地覆蓋候選軌跡。本發(fā)明的核心思想就是以給定閾值依次計(jì)算軌跡A的每一個(gè)節(jié)點(diǎn)在軌跡B上的覆蓋范圍，直至遍歷完A中的所有點(diǎn)，如果其覆蓋范圍是連續(xù)的，且其并集可以涵蓋軌跡B中的所有節(jié)點(diǎn)，則軌跡A與軌跡B符合查詢條件，即兩條軌跡的Fréchet距離在給定閾值范圍內(nèi)。

進(jìn)一步地，考慮目標(biāo)軌跡數(shù)據(jù)集和候選軌跡數(shù)據(jù)集往往包含大量軌跡，本發(fā)明采用多個(gè)目標(biāo)軌跡并行查詢和單個(gè)目標(biāo)軌跡并行搜索結(jié)合的并行策略。即：將目標(biāo)軌跡數(shù)據(jù)集劃分為多個(gè)子集，作為進(jìn)程級(jí)并行查詢?nèi)蝿?wù)；每個(gè)目標(biāo)軌跡的查詢都包含一對(duì)多的Fréchet距離閾值判斷，而每個(gè)判斷之間不存在數(shù)據(jù)依賴，作為線程級(jí)并行任務(wù)。

采用本發(fā)明獲得的有益效果是：(1)本發(fā)明進(jìn)行Fréchet距離閾值判斷的效率高。本發(fā)明方法復(fù)雜度為O(n²)，不需要計(jì)算出兩軌跡間的精確Fréchet距離即可得到結(jié)果集。交叉進(jìn)行的有效連接搜索和順序覆蓋判斷能夠盡可能早地尋找出不符合查詢條件的節(jié)點(diǎn)，得到閾值判斷結(jié)果，而不必做后續(xù)冗余的計(jì)算。(2)本發(fā)明提出的基于軌跡特征的預(yù)過濾方法具有創(chuàng)新性。僅對(duì)軌跡的首尾點(diǎn)建立R樹索引，構(gòu)建代價(jià)小，查詢效率高，且三步過濾可以濾除大多數(shù)不符合條件的軌跡，極大減小了精確的基于Fréchet距離過濾的計(jì)算壓力。(3)本發(fā)明的穩(wěn)定性高。本發(fā)明方法可對(duì)任意形態(tài)的軌跡進(jìn)行Fréchet距離閾值判斷，且隨軌跡長(zhǎng)度的增加，本發(fā)明執(zhí)行時(shí)間上升幅度較小，優(yōu)于傳統(tǒng)方法。(4)本發(fā)明的擴(kuò)展性好，并行優(yōu)化簡(jiǎn)易可行。設(shè)計(jì)了多進(jìn)程與多線程結(jié)合的并行優(yōu)化方案，任務(wù)劃分合理，進(jìn)程間不存在數(shù)據(jù)依賴，能夠更好地利用當(dāng)前常見的多機(jī)多核硬件環(huán)境，極大地提高了方法處理效率。

附圖說明

圖1是本發(fā)明中采用的Fréchet距離度量的示意圖；

圖2是本發(fā)明中距離閾值查詢子問題的一個(gè)示例；

圖3是基于軌跡MBR的過濾操作示意圖；

圖4是本發(fā)明中有效連接搜索和順序覆蓋判斷的一個(gè)實(shí)例；

圖5是本發(fā)明方法中精確Fréchet距離閾值過濾處理的流程圖；

圖6是本發(fā)明中進(jìn)程級(jí)和線程級(jí)結(jié)合的并行查詢方案設(shè)計(jì)圖；

圖7是本發(fā)明對(duì)不同長(zhǎng)度的軌跡進(jìn)行Fréchet距離閾值的進(jìn)行判斷的耗時(shí)統(tǒng)計(jì)以及與傳統(tǒng)方法的對(duì)比圖；

圖8是本發(fā)明查詢不同規(guī)模軌跡數(shù)據(jù)集的耗時(shí)與傳統(tǒng)方法的對(duì)比圖。

具體實(shí)施方式

下面結(jié)合附圖和具體實(shí)施例對(duì)本發(fā)明作進(jìn)一步說明。

本發(fā)明提供了一種基于Fréchet距離閾值的軌跡相似性快速匹配方法，包括以下步驟：

(S1)設(shè)初始的候選軌跡集為T₀，在T₀上進(jìn)行基于軌跡首尾點(diǎn)的過濾操作，得到處理后的候選軌跡集T₁；

(S2)在T₁上進(jìn)行基于軌跡最小外包框的過濾操作，得到處理后的候選軌跡集T₂；

(S3)在T₂上進(jìn)行基于軌跡緩沖區(qū)的過濾操作，得到處理后的候選軌跡集T₃；

(S4)對(duì)T₃進(jìn)行精確Fréchet距離過濾處理，得到最終結(jié)果集。

如圖2所示，為本發(fā)明中距離閾值查詢子問題的一個(gè)示例，圖中A、B分別表示目標(biāo)軌跡和候選軌跡，ε為給定閾值，圖中繪制了節(jié)點(diǎn)a₄的以ε為半徑的緩沖區(qū)，從圖中可以看出，a₄與軌跡B上的b₄、b₅、b₆建立有效連接關(guān)系，即a₄的覆蓋范圍為{b₄,b₅,b₆}。

圖3是基于軌跡MBR的過濾操作示意圖。將目標(biāo)軌跡的MBR向外擴(kuò)展ε，則符合查詢條件的候選軌跡的MBR一定位于擴(kuò)展區(qū)內(nèi)，所以在點(diǎn)過濾的基礎(chǔ)上，對(duì)新的候選軌跡集進(jìn)行MBR過濾，得到更小的候選軌跡集，以備進(jìn)一步過濾。對(duì)于基于軌跡緩沖區(qū)(Buffer)過濾的示意圖也與圖3類似(附圖省略)。

圖4是本發(fā)明中有效連接搜索和順序覆蓋判斷的一個(gè)實(shí)例。依次對(duì)示例軌跡A中的節(jié)點(diǎn)進(jìn)行軌跡B上的有效連接的搜索，結(jié)果如下表1所示：

表1有效連接搜索結(jié)果

從表中可以看出，a₀與a₁的覆蓋范圍是連續(xù)的，a₂與a₃的覆蓋范圍是連續(xù)的，全部四個(gè)點(diǎn)的搜索結(jié)果形成的順序覆蓋范圍是{b₀,b₁,b₂,b₃}和{b₅,b₆,b₇,b₈}兩段，跳過了b4節(jié)點(diǎn)，不能涵蓋整個(gè)軌跡B，所以此實(shí)施例中軌跡B不符合軌跡匹配條件。而實(shí)現(xiàn)過程中，在遍歷到節(jié)點(diǎn)a2時(shí)，發(fā)現(xiàn)覆蓋范圍與a1的結(jié)果不連續(xù)，此時(shí)，即可終止搜索，得到否定的查詢結(jié)果，而不必計(jì)算軌跡余下節(jié)點(diǎn)的覆蓋范圍。

圖5是本發(fā)明方法中精確Fréchet距離閾值過濾處理的流程圖；記P_i為目標(biāo)軌跡的第i個(gè)位置點(diǎn)，從目標(biāo)軌跡的第一個(gè)點(diǎn)i＝1開始處理；分別對(duì)候選軌跡集T3中的每一條候選軌跡進(jìn)行有效連接搜索，即遍歷候選軌跡的位置點(diǎn)，判斷其是否與P_i、P_i+1形成有效連接，計(jì)算P_i的覆蓋范圍得到C_i，P_i+1的覆蓋范圍得到C_i+1；所述有效連接定義為兩條軌跡中建立連接的兩個(gè)節(jié)點(diǎn)的距離小于給定閾值ε，則稱為有效連接；若C_i+1與C_i在候選軌跡上形成順序覆蓋關(guān)系，即C_i+1的起始點(diǎn)位于C_i的范圍內(nèi)或緊鄰C_i的結(jié)束點(diǎn)，則i增1繼續(xù)進(jìn)行下一個(gè)點(diǎn)的有效連接搜索；若C_i+1與C_i所包括的位置點(diǎn)在候選軌跡上不連續(xù)或者不能順序覆蓋候選軌跡，則搜索終止，得到否定的軌跡匹配判斷結(jié)果；當(dāng)P_i取值為目標(biāo)軌跡的最后一個(gè)點(diǎn)(流程圖5中的目標(biāo)軌跡長(zhǎng)度即實(shí)施例中采集的目標(biāo)軌跡數(shù)據(jù)的位置點(diǎn)總數(shù)，當(dāng)i取值等于該總數(shù)值時(shí)，即P_i取值為目標(biāo)軌跡的最后一個(gè)點(diǎn))，且覆蓋范圍的并集涵蓋整個(gè)候選軌跡，則得到肯定的軌跡匹配判斷結(jié)果，否則返回否定結(jié)果(軌跡不匹配)。

圖6是本發(fā)明中進(jìn)程級(jí)和線程級(jí)結(jié)合的并行查詢方案設(shè)計(jì)。目標(biāo)軌跡集和候選軌跡集往往包含大量軌跡，本發(fā)明采用多個(gè)目標(biāo)軌跡并行查詢和單個(gè)目標(biāo)軌跡并行搜索結(jié)合的并行策略。即：將目標(biāo)軌跡集劃分為多個(gè)子集，作為進(jìn)程級(jí)并行查詢?nèi)蝿?wù)；每個(gè)目標(biāo)軌跡的查詢都包含一對(duì)多的Fréchet距離閾值判斷，而每個(gè)判斷之間不存在數(shù)據(jù)依賴，作為線程級(jí)并行任務(wù)。

圖7是本發(fā)明對(duì)不同長(zhǎng)度的軌跡進(jìn)行Fréchet距離閾值的進(jìn)行判斷的耗時(shí)統(tǒng)計(jì)以及與按照Fréchet距離原始定義進(jìn)行計(jì)算的傳統(tǒng)方法的對(duì)比。采用消息傳遞接口(Message Passing Interface,MPI)和分布式計(jì)算平臺(tái)Spark分別實(shí)現(xiàn)了方法。隨著軌跡長(zhǎng)度的增加，Spark平臺(tái)的OCJ方法效率基本保持不變，這是因?yàn)榉植际接?jì)算平臺(tái)的在進(jìn)行具體方法之前需要進(jìn)行較為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)封裝、并行任務(wù)劃分與并行資源調(diào)度，即使執(zhí)行的任務(wù)量很小，也要耗費(fèi)同樣代價(jià)的準(zhǔn)備時(shí)間，且對(duì)單對(duì)軌跡的距離判斷的計(jì)算代價(jià)與準(zhǔn)備時(shí)間相比幾乎可以忽略，所以總的任務(wù)執(zhí)行時(shí)間幾乎不受軌跡長(zhǎng)度影響。而用MPI并行框架實(shí)現(xiàn)的OCJ方法，隨著軌跡長(zhǎng)度的增加，計(jì)算耗時(shí)呈現(xiàn)平緩的線性增長(zhǎng)態(tài)勢(shì)，穩(wěn)定性良好。與之對(duì)比明顯的是，傳統(tǒng)方法耗時(shí)增長(zhǎng)更加陡峭。

圖8是本發(fā)明查詢不同規(guī)模軌跡數(shù)據(jù)集的耗時(shí)與傳統(tǒng)方法的對(duì)比。傳統(tǒng)方法在大規(guī)模查詢時(shí)已經(jīng)達(dá)到小時(shí)量級(jí)，不能滿足應(yīng)用需求。而Spark通過一種分布式彈性數(shù)據(jù)結(jié)構(gòu)RDD組織數(shù)據(jù)，加速性能很好，但初始效率低，內(nèi)存消耗更大，更適合在高性能計(jì)算集群上運(yùn)行大規(guī)模的任務(wù)。MPI版本的并行OCJ方法，內(nèi)存消耗適中，性能穩(wěn)定，擴(kuò)展性良好，隨著數(shù)據(jù)量的增加維持了較為理想的加速比?？梢钥闯鲈跀?shù)據(jù)集包含萬條以上軌跡時(shí)，OCJ方法的兩種實(shí)現(xiàn)相比于原始暴力計(jì)算法都有數(shù)量級(jí)的性能提升。所以可得出本發(fā)明OCJ方法及其并行實(shí)現(xiàn)具有較為理想的計(jì)算效率和良好的并行擴(kuò)展性的結(jié)論，在實(shí)際應(yīng)用中具有良好的應(yīng)用價(jià)值。