基于位置演進模型的兩類時空查詢算法

劉 林，劉 磊，熊小鵬

（1.重慶郵電大學 計算機科學與技術學院，重慶400065；2.中國移動通信集團河南有限公司洛陽分公司，河南 洛陽471000；3.中國移動通信集團重慶有限公司，重慶401121）

0 引 言

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

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

1 背景分析

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

1.1 歷史時間窗范圍查詢 （HTWRQ）

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

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

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

（3）Oi代表Wi時段內位于R 內的對象標志集，OiO；對ia＝ib－1，滿足Oia≠Oib。

1.2 歷史時間窗近鄰查詢 （HTWkNNQ）

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

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

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

（2）Wi代表W 內子時段，當1≤ia＜ib≤S，滿足（Wia早于Wib）且（Wia∩Wib＝Φ）且（∪S

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

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

1.3 位置跳躍模型LHM

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

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

1.3.1 結果遺漏

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

圖2 HTWRQ 示例

直觀易見本查詢正確結果為＜ ［t2，t4），｛A｝＞。而LHM 模型下查詢結果為＜ ［t3，t5）， ｛A｝＞。注意A 在［t2，t3）時段LHM 計算位置始終為a1。因a1處于R 外，該時段A 不在LHM 查詢結果中。然而該時段A 實際位于R 內。因此LHM 模型導致該查詢在 ［t2，t3）時段結果遺漏。

1.3.2 結果超出

接上例。A 在時段 （t4，t5）LHM 計算位置始終為a3。因a3在R 內，A 在該時段LHM 查詢結果中。而該時段A實際位于R 外，LHM 模型導致該查詢在 （t4，t5）時段結果超出。

1.3.3 結果錯誤

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

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

圖3 HTWkNNQ 示例

2 位置演進模型時空查詢算法

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

2.1 位置演進模型LEM

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

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

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

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

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

2.2 基于LEM 的歷史時間窗范圍查詢

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

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

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

輸入：

對象標識集O＝ ｛o1，o2，…oN｝

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

查詢歷史時段W ＝ ［ts，te］

查詢區(qū)域R

輸出：

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

算法過程：

（1）查詢邊界交點時刻集C＝null；Result＝null；

（2）對每個對象oi∈O

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

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

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

C＝C∪Ci

標記oi為結果對象成員；

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

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

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

2）對每個結果對象成員o

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

Oi＝Oi∪ ｛o｝；

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

（5）返回Result；

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

2.3 基于LEM 的歷史時間窗近鄰查詢

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

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

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

2.3.2 算法思想

對每個對象，通過其軌跡函數(shù)求得中心點距離函數(shù)，并求解任意2個對象距中心點距離相同的時刻集。合并以上時刻集，去重并按升序排序，形成距離函數(shù)相交時刻集C。根據(jù)下述交點間單一關系定律2及推論1，當且僅當在C 中各交點時刻k 最近鄰有序對象集合發(fā)生變化，則C 中各時刻在查詢時段內產生的若干子時段，正是查詢結果子時段Wi。根據(jù)各對象中心點距離函數(shù)，求得各Wi子時段距離中心點最近的k 個對象標識集Oi。

交點間單一關系定律2 對于D 維空間中相同定義域內的2個連續(xù)函數(shù)f1（t）、f2（t），若解集 ｛t｜f1（t）＝f2（t）｝存在，設該解集為 ｛t1，t2，…，tx｝ （t1＜t2＜…＜tx），那么對于任意t∈（tk，tk＋1）（k∈ ｛1，…，x－1｝），對于同一個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），則對于開區(qū)域 （tk，tk＋1）（k∈ ｛1，…，y－1｝）與固定k，F(xiàn)（t）內所有函數(shù)值的大小關系在該區(qū)域內保持不變。以上定律及推論均容易通過反證法證明，此處不贅述。

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

輸入：

對象標識集O＝ ｛o1，o2，…oN｝

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

查詢中心點H＝ （h1，h2，…，hD）

最近鄰個數(shù)值k

查詢歷史時段W ＝ ［ts，te］

輸出：

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

算法過程：

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

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

（2）對每個對象oi∈O

1）根據(jù)式 （1）得到中心點距離函數(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定義域為W），其解集記為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）計算DisSet（（C ［i］＋C ［i＋1］）／2））并升 序排序；

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

3）Oi＝DisSet（（C ［i］＋C ［i＋1］）／2））中前k個值對應對象；

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

（6）返回Result；

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

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

3 基于LEM＿UL的時空查詢

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

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

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

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

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

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

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

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

3.2.1 移動對象近似軌跡函數(shù)

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

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

3.2.2 位置勻速直線演進模型LEM＿UL

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

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

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

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

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

式 （4）說明：對于tx∈W，當且僅當移動對象o的位置坐標 （xo（tx），yo（tx））滿足xc－a≤xo（tx）≤xc＋a 且yc－b≤yo（tx）≤yc＋b時，該對象在tx時刻位于R 內。

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

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

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

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

中心點近似距離函數(shù)：二維空間中，已知對象o在相鄰位 置 更 新 點ui、ui＋1間 的 軌 跡 函 數(shù) 為fo（t） ＝（（t－ ti）voxi＋xi， （t－ ti）voyi＋yi）（由 式 （2）得），查詢中心點H 的位置坐標為 （xH，yH）。由式 （1）得，［ti，ti＋1］時段內對象o和查詢中心點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é)時空最近鄰算法涉及查詢時段W 內中心點近似距離函數(shù)，因此需求解該時段內的距離函數(shù)。已知二維空間中，查詢時段W 內移動對象o的近似軌跡函數(shù) （如式 （3）），使用式 （6）求得o與H 在W 內的距離函數(shù)

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

4 實驗分析

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

4.1 基于LEM 時空查詢的近似查詢

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

4.2 兩類查詢結果準確度計算方法

基于LHM 的時空查詢結果準確度：在相同查詢條件下，查詢子時段Wi內，基于LHM 的時空查詢結果相似度（如式 （8）中ciHTWRQ）同相應時段長度 （時段兩端點差的絕對值）積的總和與查詢時段W 長度的比值。同理可定義基于LHM 的時空查詢結果準確度

W：查 詢 時 段 W，W ＝w1＋w2＋ … ＋wn；CHTWRQ（HTWkNNQ）：查詢時段W 內，基于LHM、LEM＿UL的HTWRQ 或HTWkNNQ 查詢結果準確度；ciHTWRQ：wi內基于LHM 或LEM ＿HL 的HTWRQ 查詢結果相似度，即wi內基于LHM 或LEM ＿UL 的HTWRQ 結果對象集與基于LEM 的HTWRQ 結果對象集中相同對象的個數(shù)同后者對象集數(shù)的比值；ciHTWkNNQ：wi內基于LHM 或LEM＿HL的HTWkNNQ 查詢結果相似度，即wi內基于LHM或LEM＿UL的HTWkNNQ 結果有序對象集與基于LEM的HTWkNNQ 結果有序對象集中位序且對象相同的個數(shù)與k （最近鄰數(shù)）的比值。

4.3 實驗環(huán)境

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

表1 實驗環(huán)境變量配置

4.4 實驗結果

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

同一實驗環(huán)境、查詢條件、準確度計算方法下，對于不同更新周期，基于LEM ＿UL 的HTWkNNQ 結果準確度高于基于LHM 的相應查詢結果準確度，如圖5所示。

圖4 HTWRQ 結果準確度

圖5 HTWkNNQ 結果準確度

5 結束語

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

［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］.杭州：浙江大學，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.