基于目標(biāo)軌跡的函數(shù)連接算法研究

張冠男 張煒

摘 要：隨著觀測(cè)手段的增加，人們觀測(cè)目標(biāo)的能力得到增強(qiáng)，為了能夠使這些觀測(cè)到的數(shù)據(jù)得到更好的理解，我們提出了基于目標(biāo)軌跡的函數(shù)連接算法。在關(guān)系數(shù)據(jù)庫(kù)中，關(guān)系表的元組依據(jù)時(shí)空限制條件來與目標(biāo)軌跡進(jìn)行關(guān)聯(lián)操作，進(jìn)而能夠得到更加豐富的可理解的信息。我們提出了函數(shù)連接的操作過程，給出了一種以時(shí)間空間以及屬性值限制條件下的函數(shù)連接的過程。之后我們提出了循環(huán)函數(shù)連接算法。這種算法能夠用來在數(shù)據(jù)庫(kù)中進(jìn)行大量的操作，完成數(shù)據(jù)庫(kù)中大量數(shù)據(jù)的函數(shù)連接操作。我們提出了一種改進(jìn)的策略來優(yōu)化循環(huán)函數(shù)連接算法。最后我們給出了算法的復(fù)雜性分析和實(shí)驗(yàn)的分析。

關(guān)鍵字：函數(shù)連接；目標(biāo)軌跡；壓縮優(yōu)化

中圖分類號(hào)：TP311.13 文獻(xiàn)標(biāo)識(shí)號(hào)：A 文章編號(hào)：2095-2163（2014）05-

Research of Function Join based on Target Trajectory

ZHANG Guannan， ZHANG Wei

（School of Computer Science and Technology，Harbin Institute of Technology，Harbin 150001，China）

Abstract： In order to obtain comprehensive information， which are acquired from different observing approaches， about interested objects， a trajectory based function join operation is studied. Tuples in data tables are associated based on trajectories according to spatial-temporal constraints. The paper proposes the operation of function join which shows how to do join operation in condition of spatial-temporal constraints and attribute constraints. This process helps to finish the operation in tuples. Nested loop join algorithm is proposed. This algorithm can be used in database. Then the paper also proposes an optimization method to improve the nested loop algorithm. At last the paper gives out the complexity analysis of the algorithm and the experiment.

Key words： Function Join； Target trajectory； Compression optimization

0 引 言

當(dāng)今時(shí)代，為了清楚明徹地觀察分析現(xiàn)實(shí)物理世界，人們采用了種類各異的信息數(shù)據(jù)收集方法。而為了能夠收獲具有更好理解力尺度的信息數(shù)據(jù)，就要通過不同方法針對(duì)所獲得的信息數(shù)據(jù)進(jìn)行重新的梳理解析，以求盡量多地得到感興趣物體的各類屬性信息并加以進(jìn)一步地融合處理。例如，動(dòng)物保護(hù)組織和生物學(xué)家往往使用不同種工具來觀測(cè)野生動(dòng)物[1]。正如位置跟蹤設(shè)備、全球定位導(dǎo)航和無線電遙感器等設(shè)備即更經(jīng)常地用于動(dòng)物的運(yùn)動(dòng)軌跡跟蹤。而配有紅外觸發(fā)的相機(jī)[2]也正用來探測(cè)野生物種的存在，并以此來估算種群密度等參數(shù)[3]。同樣，種群的規(guī)模則要依靠飛行器從空中的俯拍觀測(cè)[4]，而物種棲息地的采光，溫度，濕度等數(shù)據(jù)依靠傳感器網(wǎng)絡(luò)的集成采集[5]。在調(diào)用這些數(shù)據(jù)收集的方法后，就能夠得到同一種群的大量數(shù)據(jù)，比如圖片、種群規(guī)模、運(yùn)動(dòng)軌跡、氣候溫度/濕度和棲息地生存條件等。如果能夠?qū)@得的這些數(shù)據(jù)通過某種方法進(jìn)行有機(jī)地融合，這將對(duì)野生動(dòng)物行為習(xí)慣的研究產(chǎn)生重大的推動(dòng)以及幫助。

在軍事偵查領(lǐng)域中，許多設(shè)備和復(fù)雜的系統(tǒng)正用于完成其對(duì)應(yīng)的相關(guān)任務(wù)。因此雷達(dá)設(shè)備的需求也進(jìn)入了上升階段，多種不同的雷達(dá)系統(tǒng)已經(jīng)或即將建造起來。這些雷達(dá)系統(tǒng)能夠檢測(cè)目標(biāo)的方位，速度，經(jīng)度和緯度等等，而其中的目標(biāo)則包括汽車，船只，飛機(jī)等[6]。雷達(dá)警示接收器[7]或者被動(dòng)雷達(dá)均能夠有效收集目標(biāo)發(fā)出的各種雷達(dá)信號(hào)[8]。頻率信息，脈寬、脈沖能量波等許多雷達(dá)信號(hào)特征全部能由這兩種雷達(dá)探測(cè)并捕獲。如果能夠?qū)⒅鲃?dòng)偵測(cè)到的目標(biāo)信息與被動(dòng)捕獲到的信息進(jìn)行一種技術(shù)結(jié)合，就將對(duì)人們分析目標(biāo)特征帶來較大便利及助益。

然而，由于這些信息是通過不同種觀測(cè)方法收集得到的，目前并不存在一種直接獨(dú)特的方法可對(duì)這些信息數(shù)據(jù)進(jìn)行自動(dòng)完善的關(guān)聯(lián)。為了解決這一問題，文中給出了一種新穎的基于目標(biāo)軌跡的函數(shù)連接算法。在算法中，目標(biāo)的軌跡信息數(shù)據(jù)可作為索引，剩余的其他信息數(shù)據(jù)則通過建立的索引來和軌跡信息形成關(guān)聯(lián)。在基于目標(biāo)軌跡的函數(shù)連接算法中，基于時(shí)間和空間關(guān)系的條件則主要用于決定獲得的軌跡信息是否與屬性信息完成了關(guān)聯(lián)。這其中，時(shí)空關(guān)系條件可以理解為在同一時(shí)間段內(nèi)，多組數(shù)據(jù)在空間上是否相近。同時(shí)，與軌跡信息關(guān)聯(lián)的其他信息數(shù)據(jù)均可看作被觀察物體的屬性信息數(shù)據(jù)。并且，除了時(shí)間空間關(guān)系，基于目標(biāo)軌跡的函數(shù)連接算法還要滿足人為給定的限制條件。例如，紅外觸發(fā)的相機(jī)能夠探測(cè)一個(gè)扇形區(qū)域，但當(dāng)且僅當(dāng)需要分析在27～42度之間的區(qū)域信息時(shí)[9]，這種狀況下的角度就成為了限制條件，而本文的研究目標(biāo)也將隨之變換為在給定范圍做函數(shù)連接算法[10，11]。

對(duì)于所有和GPS獲得的數(shù)據(jù)所關(guān)聯(lián)的圖像信息，限制條件則是野生動(dòng)物的毛發(fā)顏色和圖像中的種群大小。通過關(guān)聯(lián)圖像信息和GPS軌跡信息，生物學(xué)家即能得到更為精確的來自不同野生動(dòng)物棲息地的種群密度估計(jì)。同樣，通過被動(dòng)雷達(dá)接收到的雷達(dá)信號(hào)能夠和飛行器的軌跡相關(guān)聯(lián)，相應(yīng)條件則是在滿足時(shí)空條件的前提下，信號(hào)方向恰好位于軌跡點(diǎn)集的內(nèi)部。在滿足相應(yīng)給定的限制條件后，大量的信號(hào)數(shù)據(jù)信息就能夠關(guān)聯(lián)到軌跡信息當(dāng)中。

這篇論文研究了基于目標(biāo)軌跡的函數(shù)連接算法。研究首先給出了連接操作的定義，接著又給出了軌跡段數(shù)據(jù)和屬性數(shù)據(jù)的元組匹配過程的設(shè)計(jì)。再以這個(gè)匹配過程為基礎(chǔ)，相應(yīng)地給出了循環(huán)連接算法。其后，為了改進(jìn)這種算法，又相繼提出了軌跡壓縮的方法，同時(shí)也給出了壓縮方法的準(zhǔn)確率。最后，實(shí)驗(yàn)的結(jié)果則給出了同一數(shù)據(jù)規(guī)模下的不同的算法的效率。

1 問題的定義

定義1 一條軌跡段是一系列具有時(shí)間戳的連續(xù)的點(diǎn)，這些點(diǎn)有一個(gè)獨(dú)特的標(biāo)識(shí)，表示為 ，其中 表示物體在時(shí)間戳 的坐標(biāo)是 。

在本部分章節(jié)當(dāng)中，需要假定所有通過不同種偵測(cè)手段獲得的數(shù)據(jù)都存儲(chǔ)在關(guān)系數(shù)據(jù)庫(kù)當(dāng)中。在關(guān)系數(shù)據(jù)庫(kù)中軌跡點(diǎn)集的關(guān)系模式可表示為 ，其中 是每個(gè)物體的特定標(biāo)識(shí)， 是軌跡集合中點(diǎn)的坐標(biāo)，而 則是每個(gè)點(diǎn)的時(shí)間戳屬性。通過觀測(cè)手段獲得的數(shù)據(jù)集合的關(guān)系模式可標(biāo)記為 ，其中 表示收集到的信息的屬性特征， 代表相對(duì)于觀測(cè)點(diǎn)（例如紅外攝像頭或者被動(dòng)雷達(dá)的坐標(biāo)位置）的空間參考信息， 即代表了獲得屬性信息的時(shí)間戳。在此，需要關(guān)注的一點(diǎn)是，軌跡點(diǎn)信息的觀測(cè)時(shí)間戳和屬性信息的觀測(cè)時(shí)間戳是獨(dú)立的，即多種設(shè)備的時(shí)間信息并不同步。

定義2 給定軌跡點(diǎn)集 ，數(shù)據(jù)信息集合 ，時(shí)間空間限制條件 ，另外的屬性值限制條件為 ，基于目標(biāo)軌跡的函數(shù)連接則可表示為，在限制條件 和 下，數(shù)據(jù)信息集合 與軌跡點(diǎn)集 做連接運(yùn)算。具體地，運(yùn)算公式可描述為：

（1）

其中，

針對(duì)時(shí)間空間關(guān)系限制條件 ，任意兩個(gè)連續(xù)的坐標(biāo)點(diǎn) ，并且相應(yīng)的時(shí)間戳 ，存在一系列關(guān)聯(lián)結(jié)果 而且滿足：

對(duì) ；

同時(shí)，對(duì) ，使 成為相對(duì)于 在 的空間參考信息，如果 并且 ， 即為真。

而對(duì)于屬性值限制條件 來說，任意有獨(dú)特標(biāo)識(shí) 的軌跡點(diǎn)集 ，可令 表示 的時(shí)間段，則存在一系列結(jié)果集 ，滿足對(duì) ，條件為 ， 并且 。

在基于目標(biāo)軌跡的函數(shù)連接定義中，研究采用了通用形式表現(xiàn)了時(shí)間空間限制條件和屬性值限制條件。但這些條件卻需要根據(jù)具體的實(shí)際應(yīng)用來相應(yīng)地確定。例如，假設(shè)O點(diǎn)表示攝像頭的位置坐標(biāo)，AO表示所有捕獲的圖像相對(duì)于O點(diǎn)的空間參考信息。通過分析圖像的空間參考信息，就可以得到動(dòng)物相對(duì)于當(dāng)前攝像頭的詳細(xì)方位。并且，ON表示正北方向，動(dòng)物圖像的角度OA是以O(shè)N為起點(diǎn)，順時(shí)針旋轉(zhuǎn)所得到的角度，可以表示為Dir（O，A）=α。同樣，基于軌跡點(diǎn)也可以計(jì)算得到每一個(gè)點(diǎn)相對(duì)于O點(diǎn)的角度。時(shí)間空間限制條件則可以定義為野生動(dòng)物的方位恰好在某一對(duì)連續(xù)的軌跡信息點(diǎn)的情況。同時(shí)，當(dāng)前圖像的獲取時(shí)間也要隸屬于這兩個(gè)軌跡點(diǎn)的時(shí)間戳之間。形式化表示即為Dir（O，p_1 ）≤α≤Dir（O，p_2）且t_1≤t≤t_2，其中p_1，p_2是兩個(gè)連續(xù)的軌跡點(diǎn)，t_1，t_2是兩個(gè)連續(xù)的時(shí)間戳。數(shù)據(jù)屬性值的限制條件可以是一系列值的集合，也可以是一段連續(xù)的值，即一段范圍。該限制條件可以設(shè)定于每一個(gè)屬性值上，也可以設(shè)定在每一個(gè)軌跡點(diǎn)上。例如野生動(dòng)物皮毛的顏色特征，以及每個(gè)圖像中野生動(dòng)物的最少數(shù)目。

2 函數(shù)連接算法處理過程

令 和 作為兩個(gè)連續(xù)的軌跡點(diǎn)和時(shí)間戳信息。給定關(guān)系表 中某一個(gè)元組 ，首先檢查屬性值的限制條件。當(dāng) 滿足這些條件時(shí)，即需檢查時(shí)間空間關(guān)系限制條件 。 的定義將要根據(jù)應(yīng)用的實(shí)際情況，可以為線性函數(shù)，二次函數(shù)或者其他類型的函數(shù)。

屬性值關(guān)系表中存儲(chǔ)著所有屬性值數(shù)據(jù)。在本文中，采用了線性函數(shù)滿足時(shí)間空間限制條件以簡(jiǎn)化計(jì)算。由于這一組數(shù)據(jù)滿足了時(shí)間空間限制條件和屬性值限制條件，算法返回了一個(gè)新的連接后的元組。如果一個(gè)元組能夠和一段軌跡滿足連接條件，那么軌跡段的第一個(gè)時(shí)間點(diǎn)信息將會(huì)用于生成的新的元組M。實(shí)現(xiàn)過程即如算法1所示。

如果有超過一個(gè)屬性值關(guān)系表可以和當(dāng)前軌跡點(diǎn)關(guān)系表連接，那么屬于這些關(guān)系表的每一條元組都將按照一定順序與軌跡點(diǎn)進(jìn)行比對(duì)。得到結(jié)果集的屬性值的時(shí)間戳并不需要按照時(shí)間順序排列，只要該屬性元組滿足了時(shí)間空間關(guān)系和屬性值限制條件即可。例如，令 ， 和 分別是三個(gè)屬性值關(guān)系表的一個(gè)元組， 和 則是 的兩個(gè)連續(xù)的軌跡點(diǎn)。當(dāng)這三個(gè)元組與軌跡段連接時(shí)，如果 不滿足時(shí)間空間限制條件，那么連接的結(jié)果就可以表示為 。如果下一個(gè)位于 中的元組不滿足連接條件，第二個(gè)關(guān)系表的元組卻滿足了關(guān)系條件，則連接結(jié)果就可以表示為 。而在三個(gè)屬性值關(guān)系表的當(dāng)前元組都和當(dāng)前軌跡段完成了匹配連接之后，即可繼續(xù)讀取下一段軌跡段數(shù)據(jù)，并重新使用以上元組進(jìn)行匹配連接。在連接的過程中，每一個(gè)屬性值數(shù)據(jù)將只能讀取一次。

算法1給出了匹配過程的細(xì)節(jié)。令k表示屬性值關(guān)系表的總數(shù)，m表示最大的屬性值關(guān)系表的元組總數(shù)。當(dāng)前匹配算法的時(shí)間復(fù)雜度即為O（kmT）。其中，T表示檢查時(shí)間空間關(guān)系限制條件和屬性值限制條件的總時(shí)間。

3 循環(huán)函數(shù)連接算法

最直接的用于連接屬性值數(shù)據(jù)和軌跡點(diǎn)集數(shù)據(jù)的連接算法就是循環(huán)函數(shù)連接算法。所有的軌跡點(diǎn)都是從軌跡點(diǎn)關(guān)系表中獲取的。對(duì)每一個(gè)軌跡點(diǎn)關(guān)系表的軌跡段，循環(huán)函數(shù)連接算法即不斷調(diào)用匹配過程來實(shí)現(xiàn)連接操作。算法可以通過排序的方法來進(jìn)行優(yōu)化，即通過對(duì)屬性值的數(shù)據(jù)元組依照元組的時(shí)間戳進(jìn)行排序來提升性能。而且由于數(shù)據(jù)都是通過偵測(cè)設(shè)備來獲取的，因此所有的數(shù)據(jù)將都是按照時(shí)間順序存儲(chǔ)在數(shù)據(jù)庫(kù)中。如果內(nèi)存足夠大，就能將所有的元組全部存放于其中時(shí)，循環(huán)連接算法將會(huì)非常地高效。否則，即使元組按照時(shí)間實(shí)現(xiàn)排序了，也會(huì)在算法運(yùn)行時(shí)產(chǎn)生很多的磁盤I/O。一般來講，軌跡點(diǎn)關(guān)系表元組的總數(shù)均要少于屬性值關(guān)系表元組的總數(shù)，因此軌跡點(diǎn)即可設(shè)定于外層循環(huán)當(dāng)中。算法2則給出了基于目標(biāo)軌跡的循環(huán)函數(shù)連接算法。算法中，假定在軌跡點(diǎn)關(guān)系表中有n個(gè)元組，最長(zhǎng)的軌跡包括c個(gè)段，那么循環(huán)連接算法需要調(diào)用匹配段過程的時(shí)間復(fù)雜度則為O（cn）。

接下來分析I/O代價(jià)。令B（T）表示軌跡點(diǎn)數(shù)據(jù)的數(shù)據(jù)塊總數(shù)，B（D）表示屬性值數(shù)據(jù)的數(shù)據(jù)塊總數(shù)，M表示內(nèi)存緩沖區(qū)的大小。假設(shè)B（T）<=B（D），如果（M-k）>B（T），則所有的軌跡段信息均可進(jìn)入內(nèi)存當(dāng)中，這時(shí)I/O代價(jià)為 。如果M

4 循環(huán)連接算法改進(jìn)策略

改進(jìn)匹配方法的主要操作就是減少在一條軌跡段內(nèi)的精確匹配次數(shù)，即減少時(shí)間空間函數(shù)的運(yùn)行次數(shù)。給定一個(gè)物體o，一個(gè)偵測(cè)設(shè)備D，如果o圍繞著D做勻速圓周運(yùn)動(dòng)時(shí)，就可以根據(jù)o相對(duì)于D的方位信息的起點(diǎn)和終點(diǎn)來估計(jì)任意時(shí)刻o點(diǎn)所在的方位信息。

更一般的情況下，考慮軌跡點(diǎn)集中k個(gè)連續(xù)的點(diǎn) ，其中k>2，令 和 代表壓縮后的軌跡段，用兩個(gè)點(diǎn)來代替k個(gè)點(diǎn)，壓縮比為k/2。假設(shè)O是觀測(cè)設(shè)備， 和 表示起始點(diǎn)和終點(diǎn)相對(duì)于遠(yuǎn)點(diǎn)的方位信息，令 設(shè)為每一步的平均時(shí)間，總的時(shí)間則為 。給定元組r，相應(yīng)的觀測(cè)角度 和時(shí)間戳t。并根據(jù)假設(shè)元組r可以與軌跡段連接，當(dāng)且僅當(dāng) 滿足軌跡段第i個(gè)夾角，其中 ， 。研究即可使用 和 作為軌跡段而在時(shí)間t來對(duì)匹配算法進(jìn)行估算。

5 實(shí)驗(yàn)

本文給出了大量的實(shí)驗(yàn)來評(píng)估基于目標(biāo)軌跡的函數(shù)連接算法，接下來又評(píng)估了循環(huán)函數(shù)連接算法以及其改進(jìn)策略。而在給出了循環(huán)連接算法與優(yōu)化版的循環(huán)連接算法的對(duì)比實(shí)驗(yàn)后，又制作了圖表來顯示數(shù)據(jù)規(guī)模與效率的關(guān)系。實(shí)驗(yàn)環(huán)境：PC機(jī)3.10GHz CPU，4G內(nèi)存，Ubuntu 12.04系統(tǒng)。

圖1即描述了每一個(gè)算法在不同的數(shù)據(jù)規(guī)模下的運(yùn)行時(shí)間，利用這些時(shí)間即可得到圖表來進(jìn)一步顯示時(shí)間和對(duì)比效率。結(jié)果圖表主要呈現(xiàn)了不同算法的效率的曲線。

圖1 改進(jìn)后的算法效率的對(duì)比

Fig.1 Comparison of efficient with different algorithm

6 結(jié)束語

通過函數(shù)連接操作，能夠?qū)⒃緵]有相同屬性的關(guān)系表的元組實(shí)現(xiàn)連接操作。這種操作的發(fā)生則需要時(shí)間、空間限制條件以及屬性值限制條件。循環(huán)連接算法的提出使得在大型數(shù)據(jù)庫(kù)中完成這種連接操作成為可能。對(duì)于給出的循環(huán)連接的算法，又進(jìn)行了算法的復(fù)雜性分析，同時(shí)也給出了大量的實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明，優(yōu)化算法可以在一定程度上提升函數(shù)連接算法的效率。

參考文獻(xiàn)：

[1]. Wildlife monitoring. http：//www.nps.gov/pore/ aturescience/ wildlife monitoring.htm. Accessed： 2014-01-05.

[2]. Camera traps. http：//worldwildlife.org/initiatives/ camera-traps. Accessed： 2014-01-05.

[3]. ROWCLIFFE J M， FIELD J， TURVEY S T， et al. Estimating animal density using camera traps without the need for individual recognition[J]. Journal of Applied Ecology， 2008，45（4）：1228–1236.

[4]. Gps wildlife tracking. http：//en.wikipedia.org/wiki/GPS wildlife tracking. Accessed： 2014-01-05.

[5]. AKYILDIZ I F， SU W， SANKARASUBRAMANIAM Y， et al. Wireless sensor networks： a survey[J]. Computer Networks， 2002，38：393–422.

[6]. Radar. http：//en.wikipedia.org/wiki/Radar. Accessed： 2014-01-05.

[7]. Radar warning receiver. http：//en.wikipedia.org/wiki/Radar warning receiver. Accessed： 2014-01-05.

[8]. FABRIZIO G， COLONE F， LOMBARDO P， et al. Adaptive beamforming for high- frequency over-the-horizon passive radar[J]. IET radar， sonar & navigation， 2009，3（4）：384–405.

[9]. BECKER L， HINRICHS K， FINKE U. A new algorithm for computing joins with grid ?les[C]//Data Engineering， 1993. Proceedings. Ninth International Conference on， IEEE， 1993：190-197.

[10]. BENTLEY J L. Multidimensional binary search trees used for associative searching[J]. Com- munications of the ACM， 1975，18（9）：509–517.

[11]. KITSUREGAWA M， HARADA L， TAKAGI M. Join strategies on kd-tree indexed relations[C]//Data Engineering， 1989. Proceedings. Fifth International Conference on IEEE， 1989：85-93.