基于位置演進(jìn)模型的兩類時(shí)空查詢算法

劉 林，劉 磊，熊小鵬

（1.重慶郵電大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，重慶400065；2.中國(guó)移動(dòng)通信集團(tuán)河南有限公司洛陽分公司，河南 洛陽471000；3.中國(guó)移動(dòng)通信集團(tuán)重慶有限公司，重慶401121）

0 引 言

智能交通、數(shù)字戰(zhàn)場(chǎng)、疾病傳播研究等領(lǐng)域的新型應(yīng)用依賴于物體歷史位置的采集、存儲(chǔ)、索引與查詢。位置采集中，移動(dòng)對(duì)象依靠通訊基站、GPS、北斗信號(hào)等方式獲取自身位置，通過GPRS、TCP／IP、WLAN 等網(wǎng)絡(luò)傳輸協(xié)議向時(shí)空數(shù)據(jù)庫提交位置信息。受耗電量、網(wǎng)絡(luò)帶寬與數(shù)據(jù)庫性能限制，位置信息傳輸通常按預(yù)設(shè)規(guī)則間隔觸發(fā)，例如距上次采集超過預(yù)設(shè)時(shí)間閥值 （如60s）或距離閥值（如500m）。時(shí)空數(shù)據(jù)庫記錄對(duì)象在離散時(shí)間點(diǎn)上對(duì)應(yīng)位置坐標(biāo)，對(duì)于這些時(shí)間點(diǎn)外任意時(shí)刻，前期多數(shù)研究假定對(duì)象位置保持靜止，該模型稱為位置跳躍模型 （location hop model，LHM）。

本文針對(duì)兩類時(shí)空查詢，即歷史時(shí)間窗范圍查詢與歷史時(shí)間窗近鄰查詢，分析LHM 下存在的查詢結(jié)果偏差問題，提出位置演進(jìn)模型 （location evolution model，LEM）與該模型中上述兩類時(shí)空查詢處理的理論算法。針對(duì)現(xiàn)實(shí)環(huán)境條件與效率要求，文中進(jìn)一步給出按勻速直線運(yùn)動(dòng)簡(jiǎn)化的位置演進(jìn)模型（LEM＿uniform linear，LEM＿UL）與對(duì)應(yīng)查詢處理算法。本文提出的位置演進(jìn)模型與兩類時(shí)空查詢處理算法，可有效消除并降低位置跳躍模型下的查詢偏差。

1 背景分析

根據(jù)查詢維度差異，時(shí)空查詢具有不同類別劃分。例如：①根據(jù)查詢時(shí)段分為歷史信息查詢［1，2］、當(dāng)前信息查詢與未來預(yù)測(cè)查詢［3－5］；②根據(jù)條件時(shí)長(zhǎng)分為時(shí)間窗查詢與時(shí)間片查詢［2－6］；③根據(jù)空間條件分為范圍查詢、多種近鄰查詢、逆近鄰查詢、Reachability查詢等等［6－12］；④根據(jù)查詢區(qū)域／點(diǎn)可否移動(dòng)，分為靜止查詢與移動(dòng)查詢［10－14］；⑤存在更多類別劃分方式。其中范圍查詢與近鄰查詢是多種衍生查詢的基礎(chǔ)，具有重要研究?jī)r(jià)值。結(jié)合位置采集與傳輸技術(shù)臻于成熟的現(xiàn)狀，本文研究?jī)深惥邆鋵?shí)用前景的基礎(chǔ)查詢：歷史時(shí)間窗范圍查詢（historical time－window range query，HTWRQ）與歷史時(shí)間窗近鄰查詢（historical time－window k－nearest－neighbor query，HTWkNNQ）。

1.1 歷史時(shí)間窗范圍查詢 （HTWRQ）

HTWRQ：假定目標(biāo)對(duì)象總數(shù)為N。已知對(duì)象標(biāo)志集O＝ ｛o1，o2，…，oN｝，與對(duì)象位置函數(shù)集L＝ ｛l1（t），l2（t），…，lN（t）｝，其中l(wèi)（t）為對(duì)應(yīng)o隨時(shí)間變化的位置函數(shù)。根據(jù)給定查詢歷史時(shí)段W 與查詢區(qū)域R，求W 時(shí)段內(nèi)位于R 內(nèi)的對(duì)象集。

輸出結(jié)果Result＝ （＜W1，O1＞，＜W2，O2＞，…，＜WS，OS＞），其中：

（1）S 為正整數(shù)；

（3）Oi代表Wi時(shí)段內(nèi)位于R 內(nèi)的對(duì)象標(biāo)志集，OiO；對(duì)ia＝ib－1，滿足Oia≠Oib。

1.2 歷史時(shí)間窗近鄰查詢 （HTWkNNQ）

HTWkNNQ：同HTWRQ，已知對(duì)象標(biāo)志集O 與對(duì)象位置函數(shù)集L。根據(jù)給定查詢歷史時(shí)段W 與查詢中心點(diǎn)H，求W 時(shí)段內(nèi)距離H 最近的k個(gè)對(duì)象。

輸出結(jié)果Result＝ （＜W1，O1＞，＜W2，O2＞，…，＜WS，OS＞），其中：

（1）S 為正整數(shù)；

（2）Wi代表W 內(nèi)子時(shí)段，當(dāng)1≤ia＜ib≤S，滿足（Wia早于Wib）且（Wia∩Wib＝Φ）且（∪S

i＝1Wi＝W）；（3）Oi代表Wi時(shí)段內(nèi)距離H 最近的k 個(gè)對(duì)象標(biāo)志所組成的有序集合，OiO；對(duì)ia＝ib－1，滿足Oia≠Oib（即Oia與Oib元素或元素排序不完全一致）。

針對(duì)HTWRQ 與HTWkNNQ 在內(nèi)的各種時(shí)空查詢，前期研究多基于以下模型進(jìn)行處理，本文將其定義為位置跳躍模型。

1.3 位置跳躍模型LHM

假設(shè)對(duì)象o的位置更新時(shí)刻為 （t1，t2，…，tm），對(duì)應(yīng)所更新位置為 （u1，u2，…，um）。則對(duì)任意時(shí)刻t∈［ti－1，ti），o的位置由函數(shù)l（t）＝ui－1計(jì)算 （其中i，m∈N＋，i≤m）。圖1對(duì)LHM 進(jìn)行說明，對(duì)象o在 ｛ti、ti＋1、ti＋2｝時(shí)刻更新位置為 ｛ui、ui＋1、ui＋2｝。易見更新時(shí)間點(diǎn)外任意時(shí)刻，單實(shí)曲線代表的對(duì)象實(shí)際位置與雙實(shí)直線代表的對(duì)象計(jì)算位置存在位置偏差。該位置偏差可導(dǎo)致3類查詢結(jié)果偏差。

圖1 位置跳躍模型位置偏差

1.3.1 結(jié)果遺漏

圖2描述一個(gè)已知O、L、R 與W ＝ ［t，t＋60s］的HTWRQ。虛線代表某對(duì)象A 實(shí)際軌跡。W 時(shí)段內(nèi)，A 的位置信息在a1、a3、a5處更新。A 在位置a2與a4分別進(jìn)入與離開R。a1～a5對(duì)應(yīng)時(shí)間點(diǎn)分別為t1～t5。

圖2 HTWRQ 示例

直觀易見本查詢正確結(jié)果為＜ ［t2，t4），｛A｝＞。而LHM 模型下查詢結(jié)果為＜ ［t3，t5）， ｛A｝＞。注意A 在［t2，t3）時(shí)段LHM 計(jì)算位置始終為a1。因a1處于R 外，該時(shí)段A 不在LHM 查詢結(jié)果中。然而該時(shí)段A 實(shí)際位于R 內(nèi)。因此LHM 模型導(dǎo)致該查詢?cè)?［t2，t3）時(shí)段結(jié)果遺漏。

1.3.2 結(jié)果超出

接上例。A 在時(shí)段 （t4，t5）LHM 計(jì)算位置始終為a3。因a3在R 內(nèi)，A 在該時(shí)段LHM 查詢結(jié)果中。而該時(shí)段A實(shí)際位于R 外，LHM 模型導(dǎo)致該查詢?cè)?（t4，t5）時(shí)段結(jié)果超出。

1.3.3 結(jié)果錯(cuò)誤

圖3描述一個(gè)已知O、L、H、W ＝ ［t，t＋60s］、k＝1的HTWkNNQ。有向線段代表對(duì)象A 與B 的實(shí)際軌跡。時(shí)刻t－10s、t＋40s對(duì)象A 更新位置信息至at－10、at＋40；時(shí)刻t－10s、t＋50s對(duì)象B更新位置信息至bt－10、bt＋50。

選取 （t＋20s，t＋40s）子時(shí)段進(jìn)行分析，LHM 下A與B位置信息值分別為at－10、bt－10，距離比較為B＜A，則該子時(shí)段查詢結(jié)果為｛B｝。而該子時(shí)段A 實(shí)際位置較B 實(shí)際位置更鄰近H。因此LHM 模型導(dǎo)致該子時(shí)段內(nèi)查詢結(jié)果錯(cuò)誤。

圖3 HTWkNNQ 示例

2 位置演進(jìn)模型時(shí)空查詢算法

針對(duì)LHM 下查詢結(jié)果偏差問題，本章提出位置演進(jìn)模型LEM，并給出該模型下HTWRQ 與HTWkNNQ 理論算法。

2.1 位置演進(jìn)模型LEM

軌跡函數(shù)：依據(jù)對(duì)象實(shí)際運(yùn)動(dòng)軌跡，描述對(duì)象位置隨時(shí)間連續(xù)變化的函數(shù)。對(duì)象o在D 維空間中的軌跡函數(shù)表示為

其中xi（t）（其中i＝ ｛1，…，D｝）表示o在第i維空間位置隨時(shí)間t的運(yùn)動(dòng)變化。在任意時(shí)刻，fo（t）的值與o實(shí)際所在位置一致。

位置演進(jìn)模型LEM：每個(gè)移動(dòng)對(duì)象o在歷史時(shí)段 ［ts，te］的軌跡函數(shù)fo（t）已知。對(duì)任意時(shí)刻t∈ ［ts，te］，o的位置由函數(shù)l（t）＝fo（t）計(jì)算。

相較位置跳躍模型，位置演進(jìn)模型LEM 最重要的特性是任何對(duì)象在任意時(shí)刻的位置可通過其軌跡函數(shù)被準(zhǔn)確計(jì)算。該特性也意味著即使歷史對(duì)象未進(jìn)行顯式的位置更新，也能根據(jù)軌跡函數(shù)持續(xù)進(jìn)行隱式位置變更。LEM 一方面從根本上消除對(duì)象計(jì)算位置與實(shí)際位置的偏差，進(jìn)而消除查詢結(jié)果偏差；另一方面對(duì)時(shí)空查詢算法提出新要求以支持對(duì)象位置隱式、持續(xù)的變更。

本章假設(shè)所有對(duì)象的軌跡函數(shù)已知。軌跡函數(shù)的求取存在多種計(jì)算方法不在本文討論范圍。第3節(jié)中給出一種高效實(shí)用的軌跡函數(shù)近似方法與查詢處理算法。

2.2 基于LEM 的歷史時(shí)間窗范圍查詢

算法思想：查詢時(shí)段內(nèi)，單個(gè)移動(dòng)對(duì)象軌跡與查詢區(qū)域R 邊界存在零個(gè)、一個(gè)或多個(gè)相交時(shí)刻。求得所有對(duì)象的所有相交時(shí)刻并升序排列，形成查詢邊界交點(diǎn)時(shí)刻集C。由交點(diǎn)間單一關(guān)系定律1，當(dāng)且僅當(dāng)在C 中各交點(diǎn)時(shí)刻發(fā)生對(duì)象進(jìn)入或離開查詢區(qū)域。則C 中各時(shí)刻在查詢時(shí)段內(nèi)產(chǎn)生的若干子時(shí)段，正是查詢結(jié)果子時(shí)段Wi。根據(jù)對(duì)象軌跡函數(shù)求得各Wi子時(shí)段對(duì)應(yīng)的結(jié)果對(duì)象標(biāo)識(shí)集Oi。

交點(diǎn)間單一關(guān)系定律1 對(duì)于D 維空間中單連通區(qū)域P與連續(xù)曲線Q，若P 與Q 邊界存在x 個(gè)交點(diǎn)將Q 切分為x＋1條曲線段，則任一曲線段上所有點(diǎn) （除交點(diǎn)外）或全在P內(nèi)，或全在P外。該定律易通過反證法求得證明，此處不贅述。

基于LEM 的歷史時(shí)間窗范圍查詢算法：

輸入：

對(duì)象標(biāo)識(shí)集O＝ ｛o1，o2，…oN｝

對(duì)象位置函數(shù)集L＝ ｛l1（t），l2（t），…lN（t）｝

查詢歷史時(shí)段W ＝ ［ts，te］

查詢區(qū)域R

輸出：

Result＝ （＜W1，O1＞，＜W2，O2＞，…＜WS，OS＞），其中S、Wi、Oi同第1節(jié)中HTWRQ 定義

算法過程：

（1）查詢邊界交點(diǎn)時(shí)刻集C＝null；Result＝null；

（2）對(duì)每個(gè)對(duì)象oi∈O

1）求函數(shù)li（t）與R 的交點(diǎn)時(shí)刻集Ci

2）Ci中排除掉大于ts或小于te的時(shí)刻

3）若Ci≠null或li（（ts＋te）／2）屬于R

C＝C∪Ci

標(biāo)記oi為結(jié)果對(duì)象成員；

（3）C＝C∪ ｛ts，te｝，去重，并升序排列成有序集合；

（4）for i＝1to｜C｜－1

1）Wk＝ ［C ［i］，C ［i＋1］），Oi＝null；

2）對(duì)每個(gè)結(jié)果對(duì)象成員o

若li（（C ［i］＋C ［i＋1］）／2）屬于R

Oi＝Oi∪ ｛o｝；

3）Result＝Result＋＜Wi，Oi＞；

（5）返回Result；

算法步驟 （2）中1）通過各個(gè)對(duì)象軌跡函數(shù)，求每個(gè)對(duì)象在查詢時(shí)段內(nèi)與查詢邊界的相交時(shí)刻。若查詢時(shí)段內(nèi)有交點(diǎn)時(shí)刻存在，則該對(duì)象在結(jié)果集中至少出現(xiàn)一次，步驟 （2）中3）標(biāo)記該對(duì)象為結(jié)果對(duì)象成員。若查詢時(shí)段內(nèi)無交點(diǎn)存在，步驟 （2）中3）利用交點(diǎn)間單一關(guān)系定律1，檢測(cè)當(dāng)前對(duì)象在查詢時(shí)段中間時(shí)刻位置，判斷是否是對(duì)象在整個(gè)W 時(shí)段處于區(qū)域R 內(nèi)的特殊情況。步驟 （2）同時(shí)獲得查詢邊界交點(diǎn)時(shí)刻集C。將C 升序排列后，步驟 （4）通過檢測(cè)子時(shí)段中間時(shí)刻，判斷當(dāng)前對(duì)象是否屬于該子時(shí)段結(jié)果集，從而求取該時(shí)段內(nèi)位于查詢區(qū)域內(nèi)的對(duì)象集合。

2.3 基于LEM 的歷史時(shí)間窗近鄰查詢

不同于HTWRQ 只需獨(dú)立考察單個(gè)對(duì)象與查詢區(qū)域R的位置關(guān)系，HTWkNNQ 需跟蹤各對(duì)象與查詢中心點(diǎn)H的距離變化，并根據(jù)距離遠(yuǎn)近對(duì)各對(duì)象排序。LEM 下各對(duì)象位置隨時(shí)間持續(xù)變化，因此HTWkNNQ 查詢算法的核心在于確定各對(duì)象距中心點(diǎn)距離排序產(chǎn)生變化的時(shí)刻。

2.3.1 中心點(diǎn)距離函數(shù)

單個(gè)對(duì)象距中心點(diǎn)的距離隨時(shí)間變化的函數(shù)。已知對(duì)象o的軌跡函fo（t）＝ （x1（t），x2（t），…，xD（t）） （如2.1節(jié)所定義），中心點(diǎn)H 的位置坐標(biāo)H＝ （h1，h2，…，hD），則o與H 的中心點(diǎn)距離函數(shù)do，H（t）表示為

2.3.2 算法思想

對(duì)每個(gè)對(duì)象，通過其軌跡函數(shù)求得中心點(diǎn)距離函數(shù)，并求解任意2個(gè)對(duì)象距中心點(diǎn)距離相同的時(shí)刻集。合并以上時(shí)刻集，去重并按升序排序，形成距離函數(shù)相交時(shí)刻集C。根據(jù)下述交點(diǎn)間單一關(guān)系定律2及推論1，當(dāng)且僅當(dāng)在C 中各交點(diǎn)時(shí)刻k 最近鄰有序?qū)ο蠹习l(fā)生變化，則C 中各時(shí)刻在查詢時(shí)段內(nèi)產(chǎn)生的若干子時(shí)段，正是查詢結(jié)果子時(shí)段Wi。根據(jù)各對(duì)象中心點(diǎn)距離函數(shù)，求得各Wi子時(shí)段距離中心點(diǎn)最近的k 個(gè)對(duì)象標(biāo)識(shí)集Oi。

交點(diǎn)間單一關(guān)系定律2 對(duì)于D 維空間中相同定義域內(nèi)的2個(gè)連續(xù)函數(shù)f1（t）、f2（t），若解集 ｛t｜f1（t）＝f2（t）｝存在，設(shè)該解集為 ｛t1，t2，…，tx｝ （t1＜t2＜…＜tx），那么對(duì)于任意t∈（tk，tk＋1）（k∈ ｛1，…，x－1｝），對(duì)于同一個(gè)k，f1（t）始終大于f2（t）或始終小于f2（t）。

推論1 已 知 連 續(xù) 函 數(shù) 集 合F（t）＝ ｛f1（t），f2（t），…fm（t）｝，求解F（t）中所有函數(shù)兩兩之間解集 ｛t｜fi（t）＝fj（t），i≠j且i、j∈ ｛1，…，m｝｝，以上解集的并集記為 ｛t1，t2，…，ty｝（t1＜t2＜…＜ty），則對(duì)于開區(qū)域 （tk，tk＋1）（k∈ ｛1，…，y－1｝）與固定k，F(xiàn)（t）內(nèi)所有函數(shù)值的大小關(guān)系在該區(qū)域內(nèi)保持不變。以上定律及推論均容易通過反證法證明，此處不贅述。

基于LEM 的歷史時(shí)間窗時(shí)空近鄰查詢算法：

輸入：

對(duì)象標(biāo)識(shí)集O＝ ｛o1，o2，…oN｝

對(duì)象位置函數(shù)集L＝ ｛l1（t），l2（t），…lN（t）｝

查詢中心點(diǎn)H＝ （h1，h2，…，hD）

最近鄰個(gè)數(shù)值k

查詢歷史時(shí)段W ＝ ［ts，te］

輸出：

Result＝ ｛＜W1，O1＞，＜W2，O2＞，…＜WS，OS＞｝，其中S、Wi、Oi同第1節(jié)中HTWkNNQ 定義

算法過程：

（1）距離函數(shù)相交時(shí)刻集C＝null；

中心點(diǎn)距離函數(shù)集DisSet＝null；Result＝null；

（2）對(duì)每個(gè)對(duì)象oi∈O

1）根據(jù)式 （1）得到中心點(diǎn)距離函數(shù)dOi，H（）t ；

2）DisSet＝DisSet∪ （dOi，H（t） ）；

（3）for i＝1to｜DisSet｜－1，

for j＝i＋1to｜DisSet｜

1）求解DisSet［i］＝DisSet ［j］ （其中t定義域?yàn)閃），其解集記為C（i，j）；

2）C＝C∪C （i，j）；

（4）C＝C∪ ｛ts，te｝，去重，并升序排列成有序集合；

（5）for i＝1to｜C｜－1；

1）Wi＝ （C ［i］，C ［i＋1］］，Oi＝null；

2）計(jì)算DisSet（（C ［i］＋C ［i＋1］）／2））并升 序排序；

／／DisSet（tx）代表DisSet中各函數(shù)在tx值的集合；

3）Oi＝DisSet（（C ［i］＋C ［i＋1］）／2））中前k個(gè)值對(duì)應(yīng)對(duì)象；

4）Result＝Result∪ ｛＜Wi，Oi＞｝；

（6）返回Result；

步驟 （2）通過式 （1）得到查詢時(shí)段內(nèi)每個(gè)對(duì)象與查詢中心點(diǎn)間距離函數(shù)，記入集合DisSet；步驟 （3）對(duì)Dis－Set中所有距離函數(shù)兩兩等式計(jì)算，求解任意兩函數(shù)在查詢時(shí)段W 內(nèi)的交點(diǎn)時(shí)刻集C（i，j），合并至距離函數(shù)相交時(shí)刻集C；去重并升序排序C 后，步驟 （5）對(duì)每個(gè)結(jié)果子時(shí)段求取該時(shí)段內(nèi)距離中心點(diǎn)H 最近的k 個(gè)對(duì)象的有序集合。其中步驟 （5）中2）計(jì)算各對(duì)象在每個(gè)子時(shí)段內(nèi)中間時(shí)刻距H 的距離，并升序排列。利用交點(diǎn)間單一關(guān)系定律2及推論1，該順序在相應(yīng)子時(shí)段內(nèi)不會(huì)改變。因此步驟（5）中3）取步驟 （5）中2）所得集合中前k 個(gè)對(duì)象作為相應(yīng)子時(shí)段結(jié)果對(duì)象集。

注意步驟 （5）的1）中取Wi為前開后閉區(qū)間。由于在步驟 （5）的3）中，在子時(shí)段端點(diǎn)時(shí)刻上，序位第k 的對(duì)象可能與后續(xù)一個(gè)或多個(gè)相鄰對(duì)象距中心點(diǎn)的距離相同。該情況下，本算法保持子時(shí)段內(nèi)既有結(jié)果對(duì)象作為端點(diǎn)時(shí)刻結(jié)果。

3 基于LEM＿UL的時(shí)空查詢

本章節(jié)將說明LEM 時(shí)空查詢面臨的挑戰(zhàn)。針對(duì)這些挑戰(zhàn)，本文采用移動(dòng)對(duì)象在相鄰位置更新時(shí)刻間做勻速直線運(yùn)動(dòng)思想，求解移動(dòng)對(duì)象近似軌跡函數(shù)，建立勻速直線位置演進(jìn)模型LEM ＿UL；同時(shí)伴隨查詢區(qū)域邊界函數(shù)、中心近似距離函數(shù)的獲取，實(shí)現(xiàn)相應(yīng)基于LHM 的時(shí)空查詢向基于LEM＿UL的時(shí)空查詢轉(zhuǎn)化。

由于基于LEM＿UL 的歷史時(shí)間窗范圍查詢、近鄰查詢算法與基于LEM 的相應(yīng)查詢算法的算法思想、輸入輸出形式、算法中使用變量的描述基本相同，因此算法過程將不再贅述。

3.1 基于LEM 時(shí)空查詢面臨的挑戰(zhàn)

LEM 時(shí)空查詢從理論上能夠消除LHM 時(shí)空查詢存在的結(jié)果偏差問題，但在實(shí)際時(shí)空查詢應(yīng)用中存在以下挑戰(zhàn)：

（1）由于移動(dòng)對(duì)象在位置采集時(shí)刻外任意時(shí)刻的位置信息缺失，因此移動(dòng)對(duì)象真實(shí)的軌跡函數(shù)難以獲取，使LEM 的建立無法實(shí)現(xiàn)。進(jìn)而致使基于LHM 的時(shí)空查詢難以向相應(yīng)基于LEM 的時(shí)空查詢轉(zhuǎn)化。

（2）目前研究中存在多種合成移動(dòng)對(duì)象軌跡函數(shù)的方法，例如高階插值［15］，但合成函數(shù)具有高階性質(zhì)且形式復(fù)雜，使算法效率難滿足高實(shí)時(shí)要求的應(yīng)用。

3.2 移動(dòng)對(duì)象近似軌跡函數(shù)及LEM＿UL定義

本文通過假設(shè)移動(dòng)對(duì)象在其相鄰位置更新時(shí)刻間做勻速直線運(yùn)動(dòng)求得對(duì)象的軌跡函數(shù)，稱為移動(dòng)對(duì)象近鄰軌跡函數(shù)。另外，為使章節(jié)內(nèi)容更易理解，本節(jié)針對(duì)二維空間中移動(dòng)對(duì)象近似軌跡函數(shù)進(jìn)行求解。

3.2.1 移動(dòng)對(duì)象近似軌跡函數(shù)

二維空間中，已知移動(dòng)對(duì)象o在相鄰位置更新時(shí)刻ti、ti＋1下 的 記 錄 為ui（oid，xi，yi，ti）、ui＋1（oid，xi＋1，yi＋1，ti＋1），則對(duì)象o在 ［ti，ti＋1］時(shí)段內(nèi)的軌跡函數(shù)fo（t）為

由于本章節(jié)時(shí)空范圍算法涉及查詢時(shí)段W 內(nèi)對(duì)象軌跡函數(shù)，因此需求解該時(shí)段內(nèi)的軌跡函數(shù)。已知對(duì)象o的位置更新集合為 ｛u1，…，un｝（t1＜…＜tn），求解W 內(nèi)軌跡函數(shù)首先需從該集合中獲取滿足ti≤ts＜ti＋1、tj－1≤te＜tj的子集 ｛ui，…uj｝，然后使用式 （2）求解o 在 ［ti，tj］內(nèi)的近似軌跡函數(shù)，進(jìn)而求解查詢時(shí)段W 內(nèi)對(duì)象o的近似軌跡函數(shù)

3.2.2 位置勻速直線演進(jìn)模型LEM＿UL

每個(gè)移動(dòng)對(duì)象o在歷史時(shí)段 ［ts，te］的軌跡函數(shù)fo（t）（如式 （3））已知。對(duì)任意時(shí)刻t∈ ［ts，te］，o的位置由函數(shù)l（t）＝fo（t）計(jì)算。

3.3 查詢區(qū)域及其邊界函數(shù)

二維空間中時(shí)空范圍查詢的查詢區(qū)域有多種類型，例如矩形、圓等，本節(jié)以矩形查詢區(qū)域?yàn)槔o出查詢時(shí)段內(nèi)靜態(tài)查詢區(qū)域的表示及其邊界函數(shù)。

本節(jié)采用中心點(diǎn)與邊長(zhǎng)表示矩形，即矩形對(duì)角線交點(diǎn)－－中心點(diǎn)C（xc，yc），矩形的長(zhǎng)和寬分別為2a和2b （a＞0，b＞0），則矩形頂點(diǎn)坐標(biāo)分別為：（xc＋a，yc＋b）、（xc－a，yc＋b）、（xc－a，yc－b）和 （xc＋a，yc－b）。

查詢時(shí)段W 內(nèi)，矩形查詢區(qū)域R 的中心點(diǎn)為C （xc，yc），R 的長(zhǎng)和寬分別為2a、2b。則W 內(nèi)，查詢區(qū)域R 表示為

式 （4）說明：對(duì)于tx∈W，當(dāng)且僅當(dāng)移動(dòng)對(duì)象o的位置坐標(biāo) （xo（tx），yo（tx））滿足xc－a≤xo（tx）≤xc＋a 且yc－b≤yo（tx）≤yc＋b時(shí)，該對(duì)象在tx時(shí)刻位于R 內(nèi)。

查詢區(qū)域R 的邊界由左、右、上、下4條區(qū)域邊界線段組成，分別為lleft、lright、lup、ldown（如式 （5））。二維空間中，查詢時(shí)段W 內(nèi)矩形區(qū)域R 的邊界函數(shù)為

式 （5）說明：當(dāng)且僅當(dāng)對(duì)象o在tx時(shí)刻的位置坐標(biāo)（xo（tx），yo（tx））滿足以下條件之一時(shí)，該對(duì)象位于查詢區(qū)域邊界上

3.4 中心點(diǎn)近似距離函數(shù)

本節(jié)通過式 （1）求解查詢時(shí)段W 內(nèi)移動(dòng)對(duì)象與查詢中心點(diǎn)間的距離函數(shù)。但求解中使用移動(dòng)對(duì)象近似軌跡函數(shù) （如式 （3）），因此該距離函數(shù)是近似距離函數(shù)。

中心點(diǎn)近似距離函數(shù)：二維空間中，已知對(duì)象o在相鄰位 置 更 新 點(diǎn)ui、ui＋1間 的 軌 跡 函 數(shù) 為fo（t） ＝（（t－ ti）voxi＋xi， （t－ ti）voyi＋yi）（由 式 （2）得），查詢中心點(diǎn)H 的位置坐標(biāo)為 （xH，yH）。由式 （1）得，［ti，ti＋1］時(shí)段內(nèi)對(duì)象o和查詢中心點(diǎn)H 的距離函數(shù)為

其中Ai＝ （voxi）2＋ （（voyyi））2，Bi＝2 ［（xi－xH）voxi ＋（yi－yH）voyi－ti（（（voxxi））2＋ （（voyyi））2）］，Ci＝ti2（（voxi）2＋ （（voyyi））2）＋（xi－xH）2＋（yi－yH）2。

由于本章節(jié)時(shí)空最近鄰算法涉及查詢時(shí)段W 內(nèi)中心點(diǎn)近似距離函數(shù)，因此需求解該時(shí)段內(nèi)的距離函數(shù)。已知二維空間中，查詢時(shí)段W 內(nèi)移動(dòng)對(duì)象o的近似軌跡函數(shù) （如式 （3）），使用式 （6）求得o與H 在W 內(nèi)的距離函數(shù)

由式 （7）得，二維空間中查詢時(shí)段W 內(nèi)移動(dòng)對(duì)象與查 詢 中 心 點(diǎn) 的 距 離 函 數(shù) 集 為 DisSet ＝｛do1，H（t） ，...doN，H（t） ｝。

4 實(shí)驗(yàn)分析

本節(jié)給出基于LEM 時(shí)空查詢的近似查詢定義和基于LHM、LEM＿UL的HTWRQ （HTWkNNQ）結(jié)果準(zhǔn)確度計(jì)算方法。并在相同實(shí)驗(yàn)環(huán)境和準(zhǔn)確度計(jì)算方法下，通過仿真實(shí)驗(yàn)證明基于LEM ＿UL 的HTWRQ （HTWkNNQ）查詢結(jié)果準(zhǔn)確度普遍比基于LEM 的相應(yīng)查詢結(jié)果準(zhǔn)確度高。

4.1 基于LEM 時(shí)空查詢的近似查詢

基于LEM 的時(shí)空查詢依賴移動(dòng)對(duì)象實(shí)際軌跡對(duì)應(yīng)的軌跡函數(shù)。由于移動(dòng)對(duì)象位置采用離散采集，因此目前針對(duì)移動(dòng)對(duì)象實(shí)際運(yùn)動(dòng)軌跡及其函數(shù)的獲取方法尚不存在。為描述對(duì)象的運(yùn)動(dòng)軌跡，多數(shù)研究使用人工合成方法獲取對(duì)象軌跡函數(shù)的近似解［15］。本實(shí)驗(yàn)通過提高位置采集頻率（如每秒或每10m 更新一次）獲取對(duì)象位置數(shù)據(jù)集，采用在相鄰位置采集點(diǎn)間做勻速直線運(yùn)動(dòng)思想獲取移動(dòng)對(duì)象軌跡函數(shù)的近似解。因此基于該近似解建立的模型的實(shí)質(zhì)為L(zhǎng)EM＿UL，本實(shí)驗(yàn)稱基于高位置采集頻率上的LEM＿UL時(shí)空查詢是基于LEM 時(shí)空查詢的近似查詢。

4.2 兩類查詢結(jié)果準(zhǔn)確度計(jì)算方法

基于LHM 的時(shí)空查詢結(jié)果準(zhǔn)確度：在相同查詢條件下，查詢子時(shí)段Wi內(nèi)，基于LHM 的時(shí)空查詢結(jié)果相似度（如式 （8）中ciHTWRQ）同相應(yīng)時(shí)段長(zhǎng)度 （時(shí)段兩端點(diǎn)差的絕對(duì)值）積的總和與查詢時(shí)段W 長(zhǎng)度的比值。同理可定義基于LHM 的時(shí)空查詢結(jié)果準(zhǔn)確度

W：查 詢 時(shí) 段 W，W ＝w1＋w2＋ … ＋wn；CHTWRQ（HTWkNNQ）：查詢時(shí)段W 內(nèi)，基于LHM、LEM＿UL的HTWRQ 或HTWkNNQ 查詢結(jié)果準(zhǔn)確度；ciHTWRQ：wi內(nèi)基于LHM 或LEM ＿HL 的HTWRQ 查詢結(jié)果相似度，即wi內(nèi)基于LHM 或LEM ＿UL 的HTWRQ 結(jié)果對(duì)象集與基于LEM 的HTWRQ 結(jié)果對(duì)象集中相同對(duì)象的個(gè)數(shù)同后者對(duì)象集數(shù)的比值；ciHTWkNNQ：wi內(nèi)基于LHM 或LEM＿HL的HTWkNNQ 查詢結(jié)果相似度，即wi內(nèi)基于LHM或LEM＿UL的HTWkNNQ 結(jié)果有序?qū)ο蠹c基于LEM的HTWkNNQ 結(jié)果有序?qū)ο蠹形恍蚯覍?duì)象相同的個(gè)數(shù)與k （最近鄰數(shù)）的比值。

4.3 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)使用類似于GSTD 的移動(dòng)對(duì)象數(shù)據(jù)產(chǎn)生器生成對(duì)象的位置更新信息。對(duì)于所有對(duì)象 （12000個(gè)），生成器首先初始化所有對(duì)象的初始位置，使對(duì)象初始位置信息滿足期望為50000 m、方差為10002的正態(tài)分布N～ （50000，10002）。在初始位置的基礎(chǔ)上，不同對(duì)象以10～60s更新周期進(jìn)行位置更新，每個(gè)新的位置都是在其前次位置信息上給予一個(gè)更新周期、角度偏值、速度值計(jì)算而得。其中，角度偏值在0°～90°、90°～180°、180°～270°、270°～360°之一內(nèi)滿足均勻分布，速度值在1～5m／s、10～15m／s、20～25m／s、30～50m／s之一內(nèi)滿足均勻分布。具體的移動(dòng)對(duì)象集、更新周期、角度偏差范圍、速度范圍的配置見表1。

表1 實(shí)驗(yàn)環(huán)境變量配置

4.4 實(shí)驗(yàn)結(jié)果

圖4、圖5分別給出了基于LHM、LEM＿UL 的HTWRQ 和HTWkNNQ 查詢結(jié)果準(zhǔn)確度隨更新周期的變化曲線。由圖4和圖5 可知，隨著移動(dòng)對(duì)象更新周期的增大，基于上述兩類模型的HTWRQ 和HTWkNNQ 查詢結(jié)果準(zhǔn)確度都普遍降低，原因?yàn)椋簩?duì)于時(shí)間周期位置更新策略，相較于高頻繁的位置更新，低頻率的位置更新將產(chǎn)生更多位置信息缺失。同一實(shí)驗(yàn)環(huán)境、查詢條件、準(zhǔn)確度計(jì)算方法下，對(duì)于不同更新周期，基于LEM＿UL 的HTWRQ 查詢結(jié)果準(zhǔn)確度高于基于LHM 的相應(yīng)查詢結(jié)果準(zhǔn)確度，如圖4所示。

同一實(shí)驗(yàn)環(huán)境、查詢條件、準(zhǔn)確度計(jì)算方法下，對(duì)于不同更新周期，基于LEM ＿UL 的HTWkNNQ 結(jié)果準(zhǔn)確度高于基于LHM 的相應(yīng)查詢結(jié)果準(zhǔn)確度，如圖5所示。

圖4 HTWRQ 結(jié)果準(zhǔn)確度

圖5 HTWkNNQ 結(jié)果準(zhǔn)確度

5 結(jié)束語

本文舉例分析了前期研究中采用LHM 處理歷史時(shí)間窗時(shí)空查詢中的結(jié)果偏差，提出位置演進(jìn)模型，從理論上消除基于LHM 的時(shí)空查詢中的結(jié)果偏差。同時(shí)，針對(duì)實(shí)際時(shí)空查詢應(yīng)用，提出LEM ＿UL，給出LEM ＿UL 歷史時(shí)間窗范圍查詢和歷史時(shí)間窗近鄰查詢算法。經(jīng)實(shí)驗(yàn)驗(yàn)證，相較于基于LHM 的歷史時(shí)間窗范圍查詢和歷史時(shí)間窗近鄰查詢算法，相應(yīng)基于LEM ＿UL 的相應(yīng)時(shí)空查詢算法顯著提高了查詢結(jié)果準(zhǔn)確度。

［1］Zheng Kai，Goce Trajecvski，Zhou Xiaofang，et al.Probabilistic range queries for uncertain trajectries on road networks ［C］／／ACM Proceedings of the 14th International Conference on Extending Database Technology，2011：283－294.

［2］Ralf Hartmut Güting，Thomas Behr，Xu Jianqiu.Efficient k－nearest neighbor search on moving object trajectories［C］／／Proceedings of the International Conference on VLDB，2010：687－714.

［3］Stojanovic D，Papadopoulos AN，Predic B，et al.Continuous range monitoring of mobile objects in road networks［J］.Data and Knowledge Engineering，2008，64 （1）：77－100.

［4］Ugur Demiryurek，F(xiàn)arnoush Banaei－Kashani，Cyrus Shahabi.Efficient continuous nearest neighbor query in spatial networks using Euclidean restriction ［C］／／Processings of 11th International Symposium SSTD，2009：25－43.

［5］Ahmed M Aly，Walid G Aref，Mourad Ouzzani.Spatial queries with two kNN predicates［C］／／Proceedings of the VLDB Endowment，2012：1100－1111.

［6］Yong Hun PARK，Kyoung Soo BDK，Jae Soo YOO.Continuous range query processing over moving objects［J］.IEICE Transactions on Information and Systems，2008（11）：2727－2730.

［7］Xuan Kefeng，Zhao Geng，David Taniar，et al.Voronoibased range and continuous range query processing in mobile databases［J］.Journal of Computer and System Sciences IEEE AIAN，2009，77 （4）：637－651.

［8］LI Chun.K－nearest neighbor search on moving object trajectories［D］.Hangzhou：Zhejiang University，2007：25－70 （in Chinese）.［李春.移動(dòng)對(duì)象軌跡的最近鄰居查詢研究 ［D］.杭州：浙江大學(xué)，2007：25－70.］

［9］Reynold Cheng，Chen Lei，Chen Jinchuan.Evaluation probability threshold k－nearest－neighbor queries over uncertain data ［C］／／Proceedings of the 12th International Conference on Extending Database Technology，2009：672－683.

［10］Rimantas Benetis，Christian S Jensen，Gytis Karciauskas，et al.Nearest and reverse nearest neighbor queries for moving objects［C］／／Proceedings of the International Conference on VLDB，2006：229－250.

［11］Houtan Shirani－Mehr，F(xiàn)arnoush，Cyrus Shahabi.Efficient reachability query evaluation in large spatiotemporal contact datasets［C］／／Proceedings of the International Conference on VLDB Endowment，2012：848－859.

［12］Yildirim H，Chaoji V，Zaki MJ.GRAIL：Scalable reachability index for large graphs［C］／／Proceedings of the International Conference on VLDB Endowment，2010：276－284.

［13］Li Chuanwen，Gu Yu，Li Fangfang，et al.Moving k－nearest neighbor query over obstructed regions ［C］／／IEEE Web Conference（APWEB），2010：29－35.

［14］Yin Xiaolan，Ding Zhiming，Li Jing.Moving continuous k－nearest neighbor queries in spatial network databases ［J］.Computer Science and Information Engineering，2009，10（4）：535－541.

［15］Byunggu Yu，Seon Ho Kim，Thomas Bailey，et al.Curvebased representation of moving object trajectories［C］／／Proceedings of the International Database Engineering and Applications Symposium，2004：1098－1105.