萬靜 唐貝貝 何云斌 李松

摘 要：針對時空數(shù)據(jù)庫中的連續(xù)移動對象的最近鄰查詢問題，提出COpKNN（continuous obstructed possible k-nearest neighbor）查詢：在二維空間中，給定一個移動查詢點(diǎn)q、一組移動查詢對象集合P和一組多邊形障礙物集合O，根據(jù)障礙距離的概念，查詢q所有可能的k最近鄰集合。由于移動對象本身的不確定性以及現(xiàn)實生活中障礙物的存在，已有的查詢方式不再適用COpKNN查詢。COpKNN查詢包括三個子過程：根據(jù)可視圖、R樹和堆排序的概念，給出計算兩點(diǎn)之間障礙距離（大于等于歐幾里得距離）的方法；基于R樹的查詢方式查找在用戶給定時間段內(nèi)q所有可能的k最近鄰結(jié)果集（初步結(jié)果，也叫候選集）；采用Mindist（E，q）和候選集更新算法UpdataC（pn）對k最近鄰結(jié)果集進(jìn)行剪枝，得到較為精確的k最近鄰結(jié)果集。實驗數(shù)據(jù)集和障礙物集均采用真實的數(shù)據(jù)集，理論研究和實驗結(jié)果表明，該方法具有良好的效率。

關(guān)鍵詞：R樹；k最近鄰查詢；不確定性；可視性；障礙距離

DOI：10.15938/j.jhust.2018.03.008

中圖分類號： TP311.13

文獻(xiàn)標(biāo)志碼： A

文章編號： 1007-2683（2018）03-0044-07

A Continuous k-Nearest Neighbor Query Method

for Moving Data in Obstructed Spaces

WAN Jing， TANG Bei-bei， HE Yun-bin， LI Song

（School of Computer Science and Technology，Harbin University of Science and Technology，Harbin 150080，China）

Abstract：To solve the nearest neighbor query of continuously moving objects in Spatio-temporal database， we study novel form of continuous k-nearest neighbor query in the presence of obstacles， namely continuous obstructed possible k- nearest neighbor （COpKNN） search. Given a data set P， an obstacle set O， and a query point q in a two-dimensional space， a COpKNN query retrieves all possible k-nearest neighbors of each point on q according to the obstructed distance. Duo to the inherent of moving data objects and the existence of obstacles in our real life， previous techniques to answer nearest neighbor （NN） query cannot be directly applied to the COpKNN problem. The P COpKNN query method mainly includes three sub-algorithms： according to the concept of Visibility graph， R-tree and Heap Sort，given the method of calculation of the obstacle distance（greater than or equal Euclidean distance） between two points； find all possible k-nearest neighbors of q between user given time period based on R-tree； Using Mindist （E，q） and the candidate set update algorithm UpdataC （pn） to prune kNNs to get the correct k-nearest neighbors. Experimental data sets and obstacle sets are all based on real data sets，theoretical and experimental results show that the method with good efficiency mentioned herein.

Keywords：R-tree； k-nearest neighbor query； uncertainty； visibility； obstructed distance

0 引 言

最近鄰（nearest neighbor，NN）查詢是LBS（location based servies）眾多查詢類型和處理方法中一種最常用的查詢方式[1]，且隨著智能移動設(shè)備（如PAD、智能手機(jī)）的普及和無線通訊以及定位技術(shù)（如GPS）的快速增長，越來越多的用戶在他們移動的時候發(fā)出查詢請求，移動對象的動態(tài)查詢也迅速發(fā)展。然而，最近鄰的研究大多數(shù)是不考慮障礙物以及查詢對象移動的不確定性。MR Kolahdouzan等[2]提出時空網(wǎng)絡(luò)數(shù)據(jù)庫中的兩種CKNN查詢IE和UBD；YK Huang等[3]提出CPKNN（continuous possible KNN）查詢；A. Prasad Sistla等[4]研究了確定位置的連續(xù)KNN查詢以及不確定位置的連續(xù)KNN查詢，分別對兩種查詢進(jìn)行在線和不在線兩種方式進(jìn)行研究。國內(nèi)在空間和時空數(shù)據(jù)庫最近鄰查詢處理技術(shù)方向的研究也取得了較為豐碩的成果。孫冬璞等[5]研究了移動對象歷史軌跡的連續(xù)最近鄰查詢；黃敬良等[6]提出基于TPR樹的移動對象的K個連續(xù)最近鄰查詢，在該文獻(xiàn)中提出了分界時間的概念；劉斌，萬靜[7]提出了基于R樹的連續(xù)最近鄰查詢算法優(yōu)化研究；袁培森等[8]研究了一種基于學(xué)習(xí)的高維數(shù)據(jù)c-近似最近鄰查詢算法。

但以上算法都是基于理想的歐氏空間的。在障礙空間中，不能單純的以歐幾里得距離計算查詢點(diǎn)和查詢對象之間的距離。李松等[9]提出了障礙物環(huán)境下的單純型連續(xù)近鄰鏈查詢；張麗萍等[10]提出了基于Voronoi圖的障礙物環(huán)境下的單純型連續(xù)近鄰鏈查詢；Yunjun Gao等[11]提出了障礙空間下的CONN（continuous obstructed NN）查詢。上述算法中沒有考慮到查詢對象本身的不確定性。然而，不確定性是管理移動對象位置信息的時空數(shù)據(jù)庫的固有屬性。由于測量的不精確性、連續(xù)運(yùn)動本身的不確定性以及網(wǎng)絡(luò)延遲的因素，移動對象存儲在數(shù)據(jù)庫中的位置信息并不能總是精確地表示它們的真實位置。甚至在有的場景中，位置的不確定性是人為引入的。例如，為了保護(hù)基于服務(wù)的位置隱私性，不確定性被注入到用戶的位置信息中[12]。如文[13]給出了基于位置不確定性的k最近鄰（kNNs）查詢；文[4]也給出了相關(guān)不確定性查詢；文[14]提出了基于不確定Voronoi圖的概率性查詢，也給出了不確定性的相關(guān)查詢。

綜合以上論述，已有的最近鄰研究方法中，針對移動對象本身的不確定性上的研究有所不足，且現(xiàn)有kNN查詢大都只查詢要求的k個對象，而實際上只要在第k個最近鄰的相同范圍內(nèi)，可能會有大于等于k個對象。所以為了解決這些問題，進(jìn)一步提高查詢性能，本文研究一種空間COpKNN（continuous obstructed possible kNN）查詢：給定一個移動查詢點(diǎn)、一組移動查詢對象集合和一組多邊形障礙物集合（為了描述方便，本文障礙物定義為多邊形和線段），根據(jù)最短路徑度量dist_O（dist_O是指障礙距離，兩點(diǎn)之間最短避障路徑的長度）采用R樹索引結(jié)構(gòu)對移動目標(biāo)進(jìn)行索引，找到所有可能成為查詢點(diǎn)的kNNs的移動對象，并且樹的每個節(jié)點(diǎn)只被訪問一次。

1 問題定義

1.1 基本定義

本節(jié)中主要定義COPKNN（continuous obstructed possible k-nearest Neighbor）查詢，以及與COPKNN查詢相關(guān)的概念定義，且本文中任意兩可見點(diǎn)之間的距離均采用歐幾里得度量方法計算，兩點(diǎn)間的距離用dist_euc（）表示，障礙距離均用dist_o（）。

定義1 （k最近鄰查詢[15]） 給定查詢點(diǎn)q和查詢對象集P={p1，p2，…，pn}，k最近鄰查詢就是檢索任意p∈P，滿足dist（q，p）≤dist（q，pk）。即：kNN（q，P）={p1，p2，…，pk}，其中，p∈P-kNN（q，P），dist（q，p） ≤max{p∈kNN（q，P）|dist（q，p）}。

在定義1中，dist（）表示兩點(diǎn)之間的最短距離函數(shù)；pk∈P且pk是根據(jù)最短距離函數(shù)dist（）計算的q的第k個最近鄰點(diǎn)。

定義2 （點(diǎn)與點(diǎn)的可視性[16]）給定點(diǎn)p，p ∈P和障礙物集O，p和p可視當(dāng)且僅當(dāng)它們之間沒有任何障礙物阻擋，即o∈O，[p，p] ∩o=。

定義3 （最短障礙距離[1]）在數(shù)據(jù)點(diǎn)集P={p1，p2，…，pn}中，存在障礙物集O={o1，o2，…，om}。任意兩點(diǎn)p1，p2∈P。那么p1，p2之間的最短障礙距離

dist_O（p1，p2）=min{（∑n-1k=1dist_euc（vk，vk+1）+|pi，v1|+|pj，vn-1|}。

在定義3中，點(diǎn)vk，vk+1為任意兩可見點(diǎn)，n為可見點(diǎn)總數(shù)。即直線段vkvk+1不與O中任意障礙物相交，dist_euc（vk，vk+1）表示線段vkvk+1的歐幾里得距離長度。

定義4 （障礙最近鄰ONN查詢[17]）。給定一個數(shù)據(jù)集P，障礙集O和查詢點(diǎn)q。ONN（q）={ p∈P|pi∈P- {p}：dist_o（p，q） ≤dist_o（pi，q）}。

定義5 （COpKNN）給定一個查詢點(diǎn)q，查詢對象集合P={p1，p2，…，pn}以及障礙物集合O={o1，o2，…，om}。COpKNN查詢結(jié)果返回所有可能距離查詢點(diǎn)q最近的查詢對象，所以COpKNN（q，k）={p1，p2，…，pk，…ps∈P|p∈P-{p1，p2，…，pk，…ps}， dist_o （p， q） ≥max1≤i≤s dist_o （pi， q）}。

1.2 主存障礙路徑查詢

最短路徑查詢可以基于可視圖[18]進(jìn)行?？梢晥D中的節(jié)點(diǎn)由所有障礙物的頂點(diǎn)和點(diǎn)q、p組成，可視圖的邊由任意兩可視點(diǎn)的連線構(gòu)成，如圖1所示。圖1中的粗線代表q與p之間的最短障礙距離。

引理1[19] 假定B一組多邊形障礙物集合，點(diǎn)q與p之間的最短路徑在于B和{q，p}組成的可見圖。

在文[19]中，該引理表示點(diǎn)q與p之間可以有無限多條路徑，它依然證明最短的那條定是存在G中的其中一條路徑。最短路徑計算方法分為兩個步驟[17]，首先構(gòu)造可視圖，然后利用Dijkstra算法搜索G中的最短路徑。第一步利用平面掃描[20]的方法需要O（n2logn）時間，用輸出敏感算法[21]可以優(yōu)化到O（l+nlogn）時間，其中l(wèi)是G的邊的個數(shù)。第二步利用Dijkstra算法需要O（m+nlogn）時間，其中m是G中邊的個數(shù)，n是G中頂點(diǎn)的個數(shù)。

2 障礙空間中移動對象的連續(xù)k最近鄰查詢

本節(jié)提出障礙空間中連續(xù)移動對象的k最近鄰查詢的處理方法。由于移動對象本身的不確定性，首先定義移動對象的不確定區(qū)域；然后通過可視圖和R樹索引以及堆排序的概念，計算兩點(diǎn)之間的最短障礙距離；以最短障礙距離為基準(zhǔn)，通過R樹索引查詢q的所有可能的k最近鄰集合；采用Mindist（E，q）和候選集更新算法UpdateC（pn）完成剪枝過程，得到最終結(jié)果。

2.1 不確定查詢區(qū)域

本節(jié)假設(shè)查詢點(diǎn)和查詢對象均是連續(xù)移動的。每一個移動對象會不時向數(shù)據(jù)庫發(fā)送更新，更新包括該對象當(dāng)前的位置和速度矢量。在下一次更新之前，數(shù)據(jù)庫會按照上次更新的結(jié)果假設(shè)移動對象的運(yùn)動主區(qū)域。數(shù)據(jù)庫上次更新結(jié)果如圖2所示，查詢對象起始運(yùn)動點(diǎn)分別是圓環(huán)R1、R2對應(yīng)的圓心位置，運(yùn)動方向是Θ1、Θ2箭頭對應(yīng)的方向。

在用戶給定的時間段（ts-te）內(nèi)查詢?nèi)我粫r刻查詢點(diǎn)的k最近鄰（kNNs），且移動對象的速度大小以及運(yùn)動方向是不確定的。那么假設(shè)移動對象的速度大小在最大值和最小值之間，運(yùn)動方向是任意方向，下面提出移動對象的可能區(qū)域模型以及計算距離不確定查詢點(diǎn)可能區(qū)域最近的不確定對象集的算法。

移動對象o的可能區(qū)域Ro（t）隨著時間在不斷移動，Ro（t）的模型一個圓環(huán)，內(nèi)環(huán)對應(yīng)查詢對象的最小速度在數(shù)據(jù)庫下次更新之前所達(dá)到的位置，外環(huán)對應(yīng)查詢對象的最大速度在數(shù)據(jù)庫下次更新之前所達(dá)到的位置，運(yùn)動方向是圓環(huán)內(nèi)的任意方向。Ro（t）如圖2所示。

圖2表示了具有不確定移動速度和移動方向的移動對象CPKNN查詢的一個例子。圖中O1O2代表障礙物，查詢對象P1和P2的初始位置分別位于圓環(huán)R1和R2的圓心位置，且二者均具有不確定的移動速度，速度范圍在圓環(huán)內(nèi)環(huán)和外環(huán)之間，內(nèi)環(huán)半徑分別為|rp1|和|rp2|，外環(huán)半徑分別為|rp1|和|rp2|外環(huán)與內(nèi)環(huán)的半徑差為rp。那么，在該時刻P1和P2的位置如圖2所示，顯然在該時刻查詢點(diǎn)q的1NN是P1，且最近距離dist（q，p1）min=dist（q，O1）+dist（q，O2），易知dist（q，p2）> dist（q，p1）min。

為了提高查詢效率，可根據(jù)上次數(shù)據(jù)庫更新的結(jié)果確定查詢的主區(qū)域，而不需要整個圓環(huán)作為查詢區(qū)域。如圖2所示，上次數(shù)據(jù)庫更新的運(yùn)動方向為Θ1、Θ2箭頭對應(yīng)的方向，那么在下次數(shù)據(jù)庫更新時，二者的運(yùn)動區(qū)域的概率最大值分別在a1b1d1c1、a2b2d2c2兩個區(qū)域。這樣移動對象就只需在a1b1d1c1、a2b2d2c2兩個區(qū)域內(nèi)確定，提高了查詢效率。

2.2 查詢對象候選集更新

由于障礙距離的計算代價比較昂貴，所以我們可以對查詢對象進(jìn)行篩選，只計算最有希望的對象集合（即候選集）。通過對查詢對象候選集的選擇，可以在用戶給定的范圍和時間段內(nèi)快速的對一組查詢對象進(jìn)行k最近鄰查詢。盡管障礙距離和歐幾里得距離不同，但二者是相關(guān)的，顯然dist_O（p， q）≥dist_euc（p， q）。

算法核心思想：候選集更新算法既可判斷新加入對象pn是否屬于候選集Cn也是剪枝算法。當(dāng)有新的對象pn加入查詢對象集P時，首先根據(jù)新加入對象pn到查詢點(diǎn)的歐幾里得距離是否小于等于候選集中第n個對象到查詢點(diǎn)q的障礙距離，如果是，則把pn加入候選集Cn，再次判斷如果候選集Cn中任意一個對象p到查詢點(diǎn)q的最小障礙距離大于rmax（rmax是候選集中第n個對象到查詢點(diǎn)q的障礙距離），則p不可能是q的最近鄰，否則p屬于候選集Cn。作為剪枝算法直接判斷候選集Cn中任意一個對象p到查詢點(diǎn)q的最小障礙距離是否大于rmax，原理同上。

算法1 候選集更新UpdataC（pn）

輸入：查詢點(diǎn)q，障礙物R樹Tobs，新加入對象pn

輸出：候選集Cn

for i=1 to n ；

rmax←C[n]. dist_O；

while Cn≠；

if rmax≥dist_euc （pn，q） ；

Cn←Cn+{pn} ；

for p∈Cn；

if dist_O（p，q）+ rp+rq

≤rmax- rp-rq ；

Cn←Cn+{ p}；

return Cn.

定理1 算法UpdataC（pn）是正確的、可終止的，其時間復(fù)雜度為O（n）。

證明：（正確性）UpdataC（pn）算法采用Cn存放候選集，若查詢對象集是不為空，且判斷候選集中到查詢點(diǎn)的最大障礙距離大于等于查詢對象集中的查詢對象到查詢點(diǎn)的歐幾里得距離，那么如果查詢對象到查詢點(diǎn)的障礙距離最大值小于等于候選集中到查詢點(diǎn)的最大障礙距離最小值，那么該查詢對象就屬于候選集。依次循環(huán)，所以算法可有效選擇候選集，是正確的。

（可終止性）UpdataC（pn）算法主要是while循環(huán)。而while循環(huán)中的Cn是有限集合。所以算法是可終止的。

（時間復(fù)雜度分析）算法中主要是while循環(huán)，假設(shè)Cn中有n個對象，那么while循環(huán)所需的時間為O（n）。所算法的時間復(fù)雜度為O（n）。

2.3 最短障礙距離計算算法

算法核心思想：算法主要利用R樹、堆和可視圖的概念進(jìn)行最短路徑計算。首先將障礙R樹Tobs中未訪問的結(jié)點(diǎn)放入堆H中，依次判斷H中的結(jié)點(diǎn)是否為一個障礙物。若是且與p和點(diǎn)q之間的最短路徑相交，則把該障礙物加入可視圖，根據(jù)Dijkstra算法計算最短障礙路徑，否則把該點(diǎn)插入H中，重復(fù)上述步驟。

算法2 障礙距離計算算法Cdist_O（q，p）

輸入：查詢點(diǎn)q，查詢對象點(diǎn)p，障礙物R樹Tobs

輸出：點(diǎn)q與點(diǎn)p的障礙距離dist_O（q，p）

G←，H←，dist_O（q，p） ←∞ ；

從R樹Tobs的根結(jié)點(diǎn)開始進(jìn)行遍歷；

將Tobs的根插入到H中；

while H≠Φ do

將H中的第一個元素（o，key）出堆；

if o是障礙物的一個MBR；

for oi∈o；

將（oi，mindist（oi，q））插入到H中；

elseifo是一個內(nèi)部結(jié)點(diǎn)；

將（o，mindist（o，q））插入到H中；

else

if（o與q、p之間的最短路徑相交）；

o∈Co；

if（Co=）；

return dist_euc（p，q）；

else

更新可視圖G，將q、p、Co加入到G中；

dist_O（q，p）=Dijkstra（G，q，p）- rp- rq；

定理2 算法Cdist_O（q，p）是正確的、可終止的，其時間復(fù)雜度為O（|G|×log|G|×log|Tobs|+n），其中|G|為可視圖中節(jié)點(diǎn)的個數(shù)，|Tobs|為障礙樹的大小。

證明：（正確性）算法Cdist_O（q，p）將Tobs中未訪問的結(jié)點(diǎn)存放在堆H中，結(jié)點(diǎn)按照與q之間的最短距離的升序存放，這里的距離指歐幾里德距離。算法從根結(jié)點(diǎn)開始遍歷R樹，得到p和點(diǎn)q之間的障礙距離dist_O（p，q）。算法首先假設(shè)p和點(diǎn)q之間的最短路徑距離為∞，對于小于該距離的元素（o，key），如果o是一個障礙，且與p和點(diǎn)q之間的最短路徑相交，則o屬于障礙物候選集Co，把Co加入可視圖G中，利用Dijkstra算法重新計算最短路徑距離；如果o是一個障礙物的MBR或者內(nèi)部結(jié)點(diǎn)，則放入堆中繼續(xù)計算。遍歷R樹之后，如果Co之外的障礙物o與p和點(diǎn)q之間的最短路徑相交，那么把o加入Co中，更新G，重新計算最短路徑距離。當(dāng)障礙集中所有沒有訪問的節(jié)點(diǎn)的最小距離都大于當(dāng)前障礙距離dist_O（p，q）時，算法得到最后結(jié)果。因此算法是正確的。

（可終止性）算法Cdist_O（q，p）中有while循環(huán)和for循環(huán)。而算法的while循環(huán)是針對H中的元素進(jìn)行的，而H中元素的數(shù)量是有限的，另外for循環(huán)只和節(jié)點(diǎn)中元素個數(shù)有關(guān)是有限的，所以算法是可終止的。

（時間復(fù)雜度分析）算法的執(zhí)行時間主要是遍歷R樹Tobs的時間、Dijkstra算法的執(zhí)行時間和最后的for循環(huán)的時間。而Dijkstra算法的執(zhí)行時間為（|G|×log|G|），遍歷一次R樹Tobs的時間為log|Tobs|，假設(shè)Co之外的障礙物的個數(shù)為n，則for循環(huán)的時間復(fù)雜度為O（n）。故Cdist_O（q，p）算法的時間復(fù)雜度為O（|G|×log|G|×log|Tobs|+ n）。

2.4 COpKNN算法

本小節(jié)介紹在一種障礙空間中，給出查詢點(diǎn)q，查詢對象集P，障礙物集O，在用戶給定時間段內(nèi)查詢q所有可能的最近鄰集合Pn，其中Pn內(nèi)元素的個數(shù)可能大于k個。

算法核心思想：采用R樹索引移動目標(biāo)，通過深度優(yōu)先遍歷R樹完成查詢；采用Mindist（E，q）和候選集更新算法UpdateC（pn）完成剪枝過程；查詢基于最短障礙距離進(jìn)行，當(dāng)最近鄰結(jié)果集中的對象大于k個時，更新候選集上限r(nóng)max（即rmax等于當(dāng)前查詢對象的最短障礙距離），否則候選集上限不更新。

算法3 移動對象最近鄰生成算法COpKNN（q）

輸入：查詢點(diǎn)q，k值，查詢對象R樹Tp，障礙物R樹Tobs

輸出：最近鄰結(jié)果集Pn

Pn←，rmax←∞，n←0；

從Tp的根結(jié)點(diǎn)開始遍歷；

for （p∈Tp） ；

if p是一個查詢對象點(diǎn) ；

if dist_O（p， q）≤rmax；

Pn←Pn+{p}；

n←n+1；

if n≤k and rmax≠∞；

rmax←rmax ；

else

rmax←dist_O（p，q） ；

UpdateC（pn）//更新候選集；

else

將查詢對象的MBR根據(jù)Mindist（E，q）的升序排序，Mindist（E，q）最小值具有優(yōu)先訪問權(quán)；

for每一個MBR；

if dist_O（E， q）

對MBR內(nèi)的結(jié)點(diǎn)進(jìn)行判斷，返回第4行。

定理3 算法COpKNN（q）是正確的、可終止的，其時間復(fù)雜度為O（log|Tp|），其中Tp為查詢對象R樹的大小。

證明：（正確性）算法COpKNN（q）首先設(shè)最近鄰結(jié)果集為空，最近鄰結(jié)果集上限為無窮大，然后從R樹根結(jié)點(diǎn)開始向下逐層訪問。如果訪問結(jié)點(diǎn)是一個查詢對象點(diǎn)，通過dist_O（p， q）≤rmax判斷p是否為最近鄰，若是更新結(jié)果集和rmax；如果不是查詢對象點(diǎn)，將查詢對象的MBR根據(jù)Mindist（E，q）的升序排序，Mindist（E，q）最小值具有優(yōu)先訪問權(quán)，根據(jù)dist_O（E， q）< rmax判斷是否進(jìn)入下一層查詢，如果滿足條件，訪問下一層，返回算法第4行，直到查詢到所有可能的最近鄰結(jié)果集并完成剪枝。故該算法是正確的。

（可終止性）算法COpKNN（q）是針對Tp樹進(jìn)行遍歷，而Tp樹中的結(jié)點(diǎn)數(shù)是有限的。故算法COpKNN（q）是可終止的。

（時間復(fù)雜度分析）算法的執(zhí)行時間主要是遍歷R樹Tp的時間，而遍歷一次R樹Tp的時間為log|Tp|。故算法的時間復(fù)雜度為O（（log|Tp|）。

3 實驗結(jié)果與分析

在本節(jié)中，我們通過實驗對本文提出的算法COpKNN進(jìn)行性能評估。并與用基本方法（Basic）查詢障礙空間中的kNNs（即不使用R樹索引，查詢每個查詢對象到查詢點(diǎn)q的障礙距離）以及與文[21]中的算法（MKNN算法）中的k值變化對性能的影響進(jìn)行比較分析。為了方便比較，對實驗算法細(xì)節(jié)進(jìn)行了局部調(diào)整。試驗運(yùn)行環(huán)境為：1.70GHz Intel CoreTM i5-3317U CPU、4GB RAM、Windows7操作系統(tǒng)。障礙物集包含128971MBRs 的rivers①，為了盡可能符合現(xiàn)實中的情況，障礙物分布滿足Zipf分布，其中Zipf分布的斜相關(guān)系數(shù)設(shè)為α=0.85。對象集包含98451MBRs的California數(shù)據(jù)流①，根據(jù)每個對象的運(yùn)動速度（包括運(yùn)動方向和速度大?。┐_定對象的不確定區(qū)域，且在該區(qū)域內(nèi)服從高斯分布。查詢點(diǎn)q隨機(jī)從數(shù)據(jù)集中取出。每次的實驗結(jié)果為執(zhí)行100的平均值。

首先是k值對算法性能的影響。圖3和圖4分別給出了k值的變化對CPU時間和磁盤I/O代價的影響。其中CPU執(zhí)行時間和I/O代價花費(fèi)時間單位均為s。

由圖3可以看出，k值從1變化到25的過程中，CPU時間隨著k值的增加而增加。很明顯，COpKNN方法的CPU時間增長率快于傳統(tǒng)方法，是因為COpKNN方法剪枝過程中時間隨k增長得比傳統(tǒng)方法要快，而且兩種方法的CPU時間差距明顯。COpKNN方法和MKNN算法相比增長率不太明顯，但和MKNN的CPU時間要少。實驗結(jié)果表明本文提出的COpKNN方法要好于Basic方法和MKNN方法。

圖4給出了隨著k值的增加對磁盤I/O代價的影響。Basic方法的磁盤I/O代價隨著k值的增加而增加，MKNN方法和COpKNN方法的磁盤I/O代價隨著k值的增加變化不太明顯。由于k值越大，需要訪問的數(shù)據(jù)點(diǎn)越多，磁盤I/O越大，而COpKNN方法僅需要訪問離查詢點(diǎn)較近的數(shù)據(jù)點(diǎn)，MKNN方法只需訪問安全區(qū)域內(nèi)的點(diǎn)，因此磁盤I/O代價要小很多。從圖中可以看出，COpKNN方法要優(yōu)于Basic方法和MKNN方法。

然后是數(shù)據(jù)點(diǎn)個數(shù)的影響。圖5和圖6分別給出了數(shù)據(jù)點(diǎn)密度對CPU時間和磁盤I/O代價的影響。其中CPU執(zhí)行時間單位為s，數(shù)據(jù)點(diǎn)個數(shù)為×104。

由圖5可見，隨著訪問數(shù)據(jù)點(diǎn)數(shù)量的增加， COpKNN方法所花費(fèi)的CPU時間反而下降，而Basic方法的CPU用時是增加的。這是因為對于COpKNN方法，數(shù)據(jù)點(diǎn)越密集，查詢點(diǎn)和它的障礙鄰居之間越近，計算障礙距離的時候大多數(shù)不需要遍歷可視圖，只需要計算歐幾里得距離。而Basic方法需要計算距離查詢點(diǎn)較近的每個查詢對象的障礙距離，因此對于Basic方法，數(shù)據(jù)點(diǎn)越多，CPU用時越多。

圖6反映了隨著訪問數(shù)據(jù)點(diǎn)數(shù)量的增加，Basic方法的磁盤I/O代價隨之增加，而COpKNN方法的磁盤I/O代價卻是下降的。Basic方法需要計算距離查詢點(diǎn)較近的每個查詢對象，因而數(shù)據(jù)點(diǎn)越多，計算的數(shù)據(jù)點(diǎn)越多。而COpKNN方法，數(shù)據(jù)點(diǎn)越密集，需要訪問的障礙物越少，因此不需要訪問的數(shù)據(jù)點(diǎn)越多，所以COpKNN方法的磁盤I/O代價隨著k值的增加反而減少。

最后障礙物個數(shù)的影響。圖7和圖8分別給出了障礙物個數(shù)對CPU時間和磁盤I/O代價的影響。其中CPU執(zhí)行時間單位為s，障礙物個數(shù)為×104。

由圖7可見，障礙物密度越大，CPU執(zhí)行時間越多。障礙物個數(shù)越多，查詢時需要訪問的障礙物越多，CPU時間越大。而計算障礙距離要比計算歐氏距離用時更多， Basic方法需要計算距離查詢點(diǎn)較近的每個查詢對象的障礙距離， COpKNN方法只需計算部分障礙距離，因此它的CPU耗時更多。

圖8給出了不同數(shù)量的障礙物對磁盤I/O代價的影響。隨著障礙物個數(shù)的增加，兩種方法的I/O代價都隨之增加，但是COpKNN方法由于有效的剪枝策略極大地減少了障礙物的訪問數(shù)量，因此磁盤I/O代價明顯比Basic方法的代價少很多。

4 結(jié) 論

本文分析了現(xiàn)有kNN查詢方法的不足，在此基礎(chǔ)上對障礙空間中的移動對象的連續(xù)k最近鄰進(jìn)行了研究。隨著智能移動設(shè)備、無線通訊技術(shù)、全球定位技術(shù)等的迅速發(fā)展，許多用戶在他們移動的時候發(fā)出查詢請求，這說明現(xiàn)實生活中的查詢大多數(shù)不是在理想的歐氏空間中處理。所以，為了快速有效的對查詢請求進(jìn)行響應(yīng)，本文提出了基于R樹索引的障礙空間中移動對象連續(xù)k最近鄰查詢的方法。實驗證明在一定情況下，COpKNN方法提高了障礙空間下移動對象的連續(xù)kNN查詢效率。未來的研究重點(diǎn)主要集中在基于R樹的不確定反向最近鄰查詢。

參 考 文 獻(xiàn)：

[1] 李傳文，谷峪，李芳芳，等. 一種障礙空間中不確定對象的連續(xù)最近鄰查詢方法[J].計算機(jī)學(xué)報，2010，33（8）：1359-1368.

[2] KOLAHDOUZAN MR，SHAHABI C. Continuous K Nearest Neighbor Queries in Spatial Network Databases[C].STDBM，2004，9（4）：33-40.

[3] HUANG YK，LIAO SJ，LEE C. Efficient Continuous K-nearest Neighbor Query Processing Over Moving Objects with Uncertain Speed and Direction[J]. Springer Berlin Heidelberg，2008，5069 （5）：549-557.

[4] SISTLA A. Prasad， WOLFSON Ouri， XU Bo. Continuous Nearest-neighbor Queries with Location Uncertainty[J]. The VLDB Journal，2015，24（1）：25-50.

[5] 孫冬璞，郝忠孝. 移動對象歷史軌跡的連續(xù)最近鄰查詢算法[J].計算機(jī)工程，2009，35（1）：52-54.

[6] 黃敬良，郝忠孝. 移動對象的K個連續(xù)最近鄰查詢算法[J].哈爾濱理工大學(xué)學(xué)報，2007，12（6）：24-27.

[7] 劉彬，萬靜. 基于R-樹的連續(xù)最近鄰查詢算法優(yōu)[8] 袁培森，沙朝峰，王曉玲，等. 一種基于學(xué)習(xí)的高維數(shù)據(jù)c-近似最近鄰查詢算法[J].軟件學(xué)報，2012，23（8）：2018-2031.

[9] 李松，張麗平，劉艷，等. 障礙物環(huán)境下的動態(tài)單純型連續(xù)近鄰鏈查詢[J].計算機(jī)工程，2014，40（8）：52-57.

[10]張麗平，李松，郝忠孝，等. 障礙物增減情況下的單純型連續(xù)近鄰鏈查詢[J].計算機(jī)工程與應(yīng)用，2015，51（11）：99-113.

[11]GAO Yunjun， ZHENG Baihua. Continuous Obstructed Nearest Neighbor Queries in Spatial Databases[C]. Proceedings of the 28th ACM SIGMOD International Conference of Management of Data，2009，9（4）： 577-590.

[12]MOKBEL MF， CHOW CY， AREF WG.The Newcasper： Query Processing for Location Services Without Compromisingprivacy[C]// International Conference on Very Large Data Bases， 2009， 34（4）：763-774.

[13]HUANG Yuan-Ko， CHEN Chao-Chun， LEE Chiang. Continuous K-nearest Neighbor Query for Moving Objects with Uncertain Velocity[J]. Geoinformatica，2009，13（1）： 1-25.

[14]孫冬璞，郝曉紅，高爽，等. 概率可視最近鄰查詢算法[J].哈爾濱理工大學(xué)學(xué)報，2013，18（6）：58-63.

[15]郝忠孝. 時空數(shù)據(jù)庫查詢與推理[M].北京：科學(xué)出版社，2010.

[16]JUJR SACK.Handbook of Computat-ional Geometry[M]. Ottawa： Elsevier Science，2000：829-876.

[17]ZHANG J， PAPADIAS D， MOURATIDIS K， et al.Spatial Queries in the Presence of Obstacles[R]. Lecture Notes in Computer Science， 2004， 2992：366-384.

[18]BERG M De， KREVELD M Van， OVERMARS M， et al. Computational Geometry： Algorithms and Applications[C]. Library Philosophy & Practice，2011（1）：333-334.

[19]XIA C， HSU D， TUNG AKH. A Fast Filter for Obstructed Nearest Neighbor Queries[J]. Key Technologies for Data Management，2004，3112：203-215.

[20]SHARIR M， SCHORR A.On Shortest Paths Inpolyhedral Spaces[J]. SIAM Journal on Computing， 1987，15（1）：193-215.

[21]GHOSH SK， MOUNT DM.An Output Sensitive Algorithm for Computing Visibility Graphs[J]. Foundations of Computer Science Annual Symposium on，2012，20（5）：11-19.

[22]LI Chuanwen， GU Yu， LI Fangfang， et al. Moving K-nearest Neighbour Query Over Obstructed Regions[C]// Advances inWeb Technologies Application， 2010：29-35.化研究[J].信息技術(shù)，2008，32（1）：78-79.