障礙物環(huán)境下的動(dòng)態(tài)單純型連續(xù)近鄰鏈查詢

李 松，張麗平，劉 艷，郝曉紅，楊和禹

(哈爾濱理工大學(xué)a.計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院;b.計(jì)算中心，哈爾濱 150080)

1 概述

數(shù)據(jù)集中的近鄰查詢問題在空間數(shù)據(jù)庫(kù)、海量數(shù)據(jù)查詢與分析、大數(shù)據(jù)處理、數(shù)據(jù)挖掘、圖像處理和交通控制等領(lǐng)域具有重要的研究意義。國(guó)內(nèi)外學(xué)者對(duì)近鄰查詢問題進(jìn)行了廣泛研究，在簡(jiǎn)單最近鄰、反向最近鄰、組最近鄰、線段最近鄰和最近對(duì)查詢等方面取得了一些重要研究成果［1］。

近年來，由于數(shù)據(jù)量的顯著增長(zhǎng)和實(shí)際應(yīng)用的需要，數(shù)據(jù)集中的近鄰查詢及其變種問題成為研究的熱點(diǎn)。國(guó)內(nèi)外的研究進(jìn)一步拓展到移動(dòng)查詢點(diǎn)的最近鄰查詢［2］、道路網(wǎng)中的連續(xù)最近鄰查詢［3-4］、連續(xù)集合最近鄰查詢［5］、不確定數(shù)據(jù)集中的受限最近鄰查詢［6］、可視最近鄰查詢［7］、可視反向最近鄰查詢［8］、高維數(shù)據(jù)近似最近鄰查詢［9］、不確定數(shù)據(jù)集的概率頻繁最近鄰查詢［10］、基于Voronoi 圖的反向最近鄰查詢［11］等方面。所取得的成果解決了最近鄰查詢領(lǐng)域的一系列重要問題。

作為最近鄰查詢領(lǐng)域的一個(gè)變種問題，單純型連續(xù)近鄰鏈(Simple Continues Near Neighbor Chain，SCNNC)查詢?cè)诳臻g數(shù)據(jù)挖掘、數(shù)據(jù)相似性分析和智能推理等領(lǐng)域具有較大的作用。已有的研究成果［2-11］無法有效地查詢單純型連續(xù)近鄰鏈，為處理單純型連續(xù)近鄰鏈問題，文獻(xiàn)［12］基于計(jì)算幾何中的Voronoi 圖對(duì)數(shù)據(jù)集中單純型連續(xù)近鄰鏈問題進(jìn)行了研究，提出了一種查詢數(shù)據(jù)集中單純型連續(xù)近鄰鏈的方法。文獻(xiàn)［13］基于空間索引結(jié)構(gòu)R 樹給出了動(dòng)態(tài)數(shù)據(jù)集中的單純型連續(xù)近鄰鏈查詢的算法:SCNNC_R_ST 算法，SCNNC_R_SD 算法和SCNNC_R_XZ 算法。為處理預(yù)定數(shù)據(jù)鏈規(guī)模的單純型連續(xù)近鄰鏈問題，文獻(xiàn)［14］基于空間Hilbert 曲線給出了查詢算法和更新算法。但文獻(xiàn)［12-14］的研究成果主要適用于無障礙環(huán)境下的單純型連續(xù)近鄰鏈查詢，不適合處理存在空間障礙物情況下的近鄰鏈查詢問題。由于在現(xiàn)實(shí)中空間障礙物的存在較為常見，并且空間數(shù)據(jù)集往往不是恒定不變的，隨時(shí)間和應(yīng)用的變化，空間數(shù)據(jù)集經(jīng)常動(dòng)態(tài)地增加或減少。因此研究障礙物環(huán)境下的動(dòng)態(tài)數(shù)據(jù)集的單純型連續(xù)近鄰鏈的查詢具有一定的實(shí)際意義。針對(duì)已有方法的不足，本文對(duì)障礙物環(huán)境下的動(dòng)態(tài)數(shù)據(jù)集的單純型連續(xù)近鄰鏈的查詢方法進(jìn)行研究。

2 基本定義

為了研究障礙物環(huán)境下的動(dòng)態(tài)數(shù)據(jù)集合中的單純型連續(xù)近鄰鏈查詢方法，本節(jié)首先給出文中所需的基本定義。

定義1 最近鄰查詢［1］

假設(shè)有一d 維空間的點(diǎn)集W 和一個(gè)查詢點(diǎn)q，最近鄰查詢就是找出子集NN(q，W):NN(q，W)={w∈W|?v∈W:D(q，w)≤D(q，v)}。若要找出w 個(gè)最近鄰，該定義則可擴(kuò)展成w 個(gè)最近鄰的查詢，即:wNN(q，W)={v1，v2，…，vw}，其中，?v∈W -wNN(q，W)，w∈wNN(q，W)且D(q，w)≤D(q，v);D(vi，q)≤D(vj，q)，1≤i ＜j≤w。

在定義1 中，D(q，w)和D(q，v)等表示2 個(gè)數(shù)據(jù)點(diǎn)之間的距離。在不強(qiáng)調(diào)數(shù)據(jù)集的情況下，NN(q，W)也可簡(jiǎn)寫為NN(q)，表示q 的最近鄰。

基于定義1，下面給出單純型連續(xù)近鄰鏈查詢的形式化定義。

定義2 單純型連續(xù)近鄰鏈查詢［12］

設(shè)有一d 維空間中的數(shù)據(jù)點(diǎn)集V，V 中一組有序數(shù)據(jù)點(diǎn)的集合記為CL，CL={vm，vm+1，vm+2，…，vn-1，vn}。其中，vi+1∈NN(vi)(或vi+1?NN(vi)且vi+1∈wNN(vi))，i=m，m+1，…，n-1，稱CL 為V 集中的一條連續(xù)近鄰鏈，vm稱為鏈?zhǔn)c(diǎn)，vn稱為鏈尾點(diǎn)。若CL 滿足以下條件，則稱CL 為單純型連續(xù)近鄰鏈:

(1)?vi，vj∈CL，若i≠j，則有vi≠vj;

(2)?vi，vj∈CL，若vi+1≠vj+1，則有vi≠vj;

(3)?vi∈CL，vi+1?{vm，…，vi};

(4)?vi∈CL，若vi+1?NN(vi)且vi+1∈wNN(vi)，則有(w-1)NN(vi)?{vm，…，vi}。

在數(shù)據(jù)集V 中查找一條單純型連續(xù)近鄰鏈的查詢稱為單純型連續(xù)近鄰鏈查詢，簡(jiǎn)記為SCNNCquery。

如圖1 所示，{v1，v2，v3，v4，v5，v6，v7，v8，v9，v10，v11，v12，v13，v14，v15}即是1 條以v1為鏈?zhǔn)c(diǎn)，v15為鏈尾點(diǎn)，共包含15 個(gè)數(shù)據(jù)點(diǎn)的單純型連續(xù)近鄰鏈。

圖1 單純型連續(xù)近鄰鏈和空間障礙線

定義3 前驅(qū)點(diǎn)/后繼點(diǎn)

在單純型連續(xù)近鄰鏈CL 中，設(shè)前后有序的相鄰2 個(gè)數(shù)據(jù)點(diǎn)為vi和vj，則稱vi是vj的鏈內(nèi)直接前驅(qū)點(diǎn)，vj是vi的鏈內(nèi)直接后繼點(diǎn)。本文用PRE(vj)表示vj的鏈內(nèi)直接前驅(qū)點(diǎn)，ACE(vj)表示vj的鏈內(nèi)直接后繼點(diǎn)。對(duì)于CL 中的一個(gè)數(shù)據(jù)點(diǎn)vi，本文稱在CL中排序在vi之前的數(shù)據(jù)點(diǎn)集為vi的鏈內(nèi)前驅(qū)點(diǎn)集，記為QU(vt)，在CL 中排序在vi之后的數(shù)據(jù)點(diǎn)集為vi的鏈內(nèi)后繼點(diǎn)集，記為HJ(vt)。

例如，在圖1 中，v12的鏈內(nèi)直接前驅(qū)點(diǎn)為v11，鏈內(nèi)直接后繼點(diǎn)為v13，HJ(v11)則為{v12，v13，v14，v15}。

定義4 障礙線

本文中，空間內(nèi)的障礙物被抽象為直線段或曲線段，統(tǒng)稱為障礙線，記為TLl(如圖1 所示);障礙線的端點(diǎn)稱為障礙邊緣點(diǎn)，記為h。一條障礙線具有2 個(gè)障礙邊緣點(diǎn)(如圖1 中的h1和h2所示)。對(duì)于數(shù)據(jù)點(diǎn)對(duì)(v，w)，設(shè)lVw是v，w 間的直線段，若存在TLl，使得lVw∩TLl≠?且lVw∩TLl?h，則稱數(shù)據(jù)點(diǎn)v和w 被TLl阻斷，表示為OB(TLl，(v，w));否則，稱數(shù)據(jù)點(diǎn)v 和w 未被TLl阻斷，表示為┐OB(TLl，(v，w))。

定義5 最短繞障折線

若OB(TLl，(v，w))，稱數(shù)據(jù)點(diǎn)v 和w 之間的最短距離為最短繞障距離，記為MIN_BL(v，w)，v 和w之間的最短繞障距離連線稱為最短繞障折線，記為lm，lm∩TLl∈h。如圖1 中的折線段v3h2v30。若數(shù)據(jù)點(diǎn)對(duì)(v，w)的繞障折線僅和一條障礙線相關(guān)，則稱(v，w)被單級(jí)阻斷。

在本文中，如無特殊說明，v 和其無障環(huán)境下的最近鄰(NN(v))在有障環(huán)境下若被障礙線阻斷，則v和NN(v)被單級(jí)阻斷。

定義6 最近鄰判定圓域

設(shè)v 和w 之間的最短距離為MIN(v，w)，則以v為圓心，MIN(v，w)為半徑生成的圓域稱為v 的判定圓域。記為Circle(v，MIN(v，w))。若w 是v 的最近鄰，則稱該圓域?yàn)関 的最近鄰判定圓域，記為Circle(v，NN_MIN(v，w))。

如圖1 所示，Circle(v8，NN_MIN(v8，v9))即為v8的最近鄰判定圓域。

3 障礙物環(huán)境下動(dòng)態(tài)單純型SCNNC 查詢

在現(xiàn)實(shí)中，空間數(shù)據(jù)集往往不是靜態(tài)不變的，而是經(jīng)常會(huì)發(fā)生動(dòng)態(tài)變化。本文中，障礙物環(huán)境下的動(dòng)態(tài)數(shù)據(jù)集的動(dòng)態(tài)變化主要分為2 類。第1 類是數(shù)據(jù)集動(dòng)態(tài)增大;第2 類是數(shù)據(jù)集動(dòng)態(tài)減少。顯然，單純型連續(xù)近鄰鏈查詢結(jié)果往往會(huì)隨著數(shù)據(jù)集的變化而動(dòng)態(tài)改變。本文3.1 節(jié)給出了數(shù)據(jù)集增大情況下的單純型連續(xù)近鄰鏈查詢方法;3.2 節(jié)給出了數(shù)據(jù)集減小情況下的單純型連續(xù)近鄰鏈查詢方法。

3.1 數(shù)據(jù)集增大情況下的單純型連續(xù)近鄰鏈查詢

由于障礙物環(huán)境下的動(dòng)態(tài)數(shù)據(jù)集中的單純型連續(xù)近鄰鏈的查詢是由數(shù)據(jù)集的某個(gè)初始狀態(tài)開始的。本節(jié)首先討論障礙物環(huán)境下的初始靜態(tài)數(shù)據(jù)集中的單純型連續(xù)近鄰鏈的一種啟發(fā)式查詢方法(稱為OB_STASCNNC_Search 算法)，其主要思想為:由鏈?zhǔn)c(diǎn)pm 開始調(diào)用基于空間索引結(jié)構(gòu)(如空間填充曲線、四叉樹等)的最近鄰查詢算法進(jìn)行計(jì)算，若查詢點(diǎn)與其最近鄰之間無障阻斷，則繼續(xù)遞歸進(jìn)行;如果被阻斷，則進(jìn)行最近鄰的二次判斷計(jì)算，更新部分結(jié)果集，遞歸進(jìn)行，直到查詢出符合要求的近鄰鏈。其中，最近鄰的二次判斷計(jì)算可利用障礙判定圓進(jìn)行。OB_STASCNNC_Search 算法在無障礙物環(huán)境下基于空間索引結(jié)構(gòu)進(jìn)行單個(gè)數(shù)據(jù)點(diǎn)的最近鄰查詢的時(shí)間復(fù)雜度為O(logn)，計(jì)算含w 個(gè)連續(xù)近鄰鏈點(diǎn)的最近鄰的復(fù)雜度為O(wlogn)，設(shè)受障礙物影響的鏈中近鄰點(diǎn)對(duì)的個(gè)數(shù)為m，進(jìn)行最近鄰二次判定的平均計(jì)算量為s，則該算法總時(shí)間復(fù)雜度為O(wlogn+ms)。

當(dāng)空間數(shù)據(jù)點(diǎn)動(dòng)態(tài)增加時(shí)，障礙物環(huán)境下，由鏈?zhǔn)c(diǎn)vm開始的單純型連續(xù)近鄰鏈的查詢變得更為復(fù)雜。處理該問題的一個(gè)較直接的方法(稱為OB_ZJB_UPDATE 方法)即是數(shù)據(jù)集每次動(dòng)態(tài)更新時(shí)，均調(diào)用障礙物環(huán)境下的靜態(tài)數(shù)據(jù)集的單純型連續(xù)近鄰鏈查詢算法(如OB_STASCNNC_Search 算法)進(jìn)行重新計(jì)算。該方法操作較為簡(jiǎn)單，但忽略了新增點(diǎn)vnew對(duì)查詢的影響細(xì)節(jié)，對(duì)數(shù)據(jù)集沒有進(jìn)行預(yù)先的過濾判斷，往往會(huì)增加許多冗余計(jì)算，在數(shù)據(jù)量較大時(shí)，計(jì)算代價(jià)較大。為了彌補(bǔ)該方法的不足，本小節(jié)著重考慮新增點(diǎn)對(duì)初始近鄰鏈的影響情況，對(duì)數(shù)據(jù)集進(jìn)行有效篩選和過濾，提出了新的算法。

針對(duì)新增點(diǎn)vnew，為了利用判定圓域?qū)臻g數(shù)據(jù)集進(jìn)行篩選和過濾，本節(jié)首先給出首位點(diǎn)的概念。

定義7 首位點(diǎn)

以一條單純型連續(xù)近鄰鏈CL 中的各個(gè)點(diǎn)(鏈尾點(diǎn)除外)為圓心，以其到鏈路內(nèi)直接后繼點(diǎn)的最短距離為半徑所生成的圓域集稱為鏈內(nèi)最近鄰判定圓域集。圓域集中的一些圓域互相交疊。本文將新增點(diǎn)vnew所位于的鏈內(nèi)最近鄰判定圓域所對(duì)應(yīng)的圓心點(diǎn)中在鏈內(nèi)相對(duì)位置最靠前(即鏈內(nèi)序號(hào)最小)的數(shù)據(jù)點(diǎn)稱為vnew相對(duì)于判定圓域的首位點(diǎn)。

依據(jù)單純型連續(xù)近鄰鏈和判定圓的定義與性質(zhì)可知，在初始單純型連續(xù)近鄰鏈CL 生成的情況下，新增點(diǎn)vnew對(duì)CL 的影響情況的分析如下:

(1)若新增點(diǎn)vnew落在CL 鏈內(nèi)最近鄰判定圓域集之外，則對(duì)CL 不產(chǎn)生影響。

(2)若新增點(diǎn)vnew落在CL 的鏈內(nèi)最近鄰判定圓域集之內(nèi)，則分2 種情況進(jìn)一步判斷vnew和其在CL中的首位點(diǎn)vt的關(guān)系:

1)若vnew和vt之間沒有被障礙物阻斷，則vnew成為vt新的鏈內(nèi)直接后繼點(diǎn);

2)若vnew和vt之間被障礙物阻斷，則計(jì)算vnew和vt之間的最短繞障距離MIN_BL(vt，vnew)，并和vt及其在CL 中的鏈內(nèi)直接后繼點(diǎn)ACE(vt)的距離D(vt，ACE(vt))相比較，若MIN_ BL(vt，vnew)大于D(vt，ACE(vt))，則vnew對(duì)CL 不產(chǎn)生影響;若MIN_ BL(vt，vnew)小于D(vt，ACE(vt))，則vnew成為vt新的鏈內(nèi)直接后繼點(diǎn)。若MIN_ BL(vt，vnew)等于D(vt，ACE(vt))，則根據(jù)實(shí)際需求確定vt的鏈內(nèi)直接后繼點(diǎn)是否更新。

由以上討論，可得出障礙物環(huán)境下數(shù)據(jù)集動(dòng)態(tài)增大情況下的單純型連續(xù)近鄰鏈查詢算法如算法1所示。

算法1 OB_DYNSCNNC_ADD(V，vm，BL，w，vnew)

輸入 空間數(shù)據(jù)點(diǎn)集V，數(shù)據(jù)起始點(diǎn)vm，障礙線集BL，待查鏈的數(shù)據(jù)點(diǎn)數(shù)目w，新增數(shù)據(jù)點(diǎn)vnew

輸出 由鏈?zhǔn)c(diǎn)vm開始的包含w 個(gè)數(shù)據(jù)對(duì)象點(diǎn)的一條更新后的單純型連續(xù)近鄰鏈CL

* 判斷新增點(diǎn)vnew和CL 中的數(shù)據(jù)點(diǎn)的最近鄰判定圓域的位置關(guān)系;

//確定vnew所在的數(shù)據(jù)點(diǎn)的最近鄰判定圓域集NR

//確定vnew相對(duì)于NR 的首位點(diǎn)vt

//更新單純型連續(xù)近鄰鏈CL

//更新單純型連續(xù)近鄰鏈CL

由算法1 的核心步驟可知，該算法初始時(shí)調(diào)用OB_ STASCNNC_Search 算法生成初始單純型連續(xù)近鄰鏈的時(shí)間復(fù)雜度為O(wlogn +ms)。根據(jù)新增點(diǎn)vnew的空間位置，利用鏈內(nèi)最近鄰判定圓域確定受影響的鏈內(nèi)點(diǎn)vs的平均時(shí)間復(fù)雜度為O(s')，由vs為鏈?zhǔn)c(diǎn)開始調(diào)用OB_STASCNNC_Search 算法生成部分近鄰鏈的時(shí)間復(fù)雜度為O(w'logn +m's')，其中，w'是vs之后需要確定的鏈內(nèi)數(shù)據(jù)點(diǎn)的個(gè)數(shù);m'是需要二次計(jì)算和判斷的數(shù)據(jù)點(diǎn)的個(gè)數(shù)。該算法核心步驟總的時(shí)間復(fù)雜度即為O(w+w')logn+ms+m's')。該算法的效率和空間障礙物的數(shù)量、空間數(shù)據(jù)點(diǎn)的數(shù)量和受新增點(diǎn)vnew影響的鏈內(nèi)點(diǎn)的位置關(guān)系較大。

3.2 數(shù)據(jù)集減小情況下的單純型連續(xù)近鄰鏈查詢

數(shù)據(jù)集的動(dòng)態(tài)變化的另一種情況是數(shù)據(jù)集的動(dòng)態(tài)減小。與3.1 節(jié)的討論類似，處理該類問題也可用較為直接的方法(OB_ZJB_UPDATE 方法)。OB_ZJB_UPDATE 方法的主要思想是在數(shù)據(jù)集每次動(dòng)態(tài)減少時(shí)，均調(diào)用障礙物環(huán)境下的靜態(tài)數(shù)據(jù)集的單純型連續(xù)近鄰鏈查詢算法進(jìn)行重新計(jì)算。由于有大量的冗余計(jì)算，該方法的計(jì)算代價(jià)較高。本小節(jié)考慮減少點(diǎn)對(duì)初始近鄰鏈的影響情況，對(duì)數(shù)據(jù)集進(jìn)行有效篩選和過濾，提出新的算法。

依據(jù)單純型連續(xù)近鄰鏈和判定圓的定義與性質(zhì)可知，在初始單純型連續(xù)近鄰鏈CL 生成的情況下，減少點(diǎn)vdel對(duì)CL 的影響情況的分析如下:

2015年在2013年所采集的產(chǎn)生抗藥性種群13JLGY-6、13JLGY-9、13JYJD-1、13JCWJ-3的原采集地采集看麥娘種子，分別命名為15JLGY-6、15JLGY-9、15JYJD-1、15JCWJ-3，采用整株生物測(cè)定法測(cè)定其抗藥性。結(jié)果發(fā)現(xiàn)，這4個(gè)種群看麥娘對(duì)精唑禾草靈的相對(duì)抗性倍數(shù)在9.36～31.79倍之間(表5)。

(1)若減少點(diǎn)vdel不是CL 中的數(shù)據(jù)點(diǎn)，則CL 不受影響;

(2)若減少點(diǎn)vdel是CL 中的數(shù)據(jù)點(diǎn)，則減少vdel僅對(duì)vdel的鏈內(nèi)后繼點(diǎn)集有影響，對(duì)vdel的鏈內(nèi)前驅(qū)點(diǎn)集沒有影響。只需考慮vdel的鏈內(nèi)后繼點(diǎn)集的變化更新。

由以上討論，可得出障礙物環(huán)境下數(shù)據(jù)集動(dòng)態(tài)減少情況下的單純型連續(xù)近鄰鏈查詢算法如算法2所示。

算法2 OB_DYNSCNNC_DET(V，vm，w，TL，vdel)

輸入 空間數(shù)據(jù)點(diǎn)集V;數(shù)據(jù)起始點(diǎn)vm;待查鏈的數(shù)據(jù)點(diǎn)數(shù)目w;障礙線集TL;減少的數(shù)據(jù)點(diǎn)vdel

輸出 由鏈?zhǔn)c(diǎn)vm開始的包含w 個(gè)數(shù)據(jù)對(duì)象點(diǎn)的一條更新后的單純型連續(xù)近鄰鏈CL

判斷滿足輸入條件的初始單純型連續(xù)近鄰鏈CL 是否已生成;

由算法2 的核心步驟可知，該算法初始時(shí)調(diào)用OB_STASCNNC_Search 算法生成初始單純型連續(xù)近鄰鏈的時(shí)間復(fù)雜度為O(wlogn+ms)。根據(jù)刪減點(diǎn)vdel與CL 的關(guān)系確定受影響的vdel的鏈內(nèi)后繼點(diǎn)集的平均時(shí)間復(fù)雜度為O(s')，由vdel的鏈內(nèi)直接前驅(qū)點(diǎn)vq開始調(diào)用OB_STASCNNC_Search 算法生成部分近鄰鏈的時(shí)間復(fù)雜度為O(hlogn +ts);該算法總的時(shí)間復(fù)雜度為O((w+h)logn +(m+t)s)，其中，h 是vq之后需要確定的鏈內(nèi)數(shù)據(jù)點(diǎn)的個(gè)數(shù);t 是vq之后需要考慮的被障礙物阻斷的點(diǎn)對(duì)個(gè)數(shù)。該算法的效率與空間障礙物的數(shù)量、空間數(shù)據(jù)點(diǎn)的數(shù)量、數(shù)據(jù)鏈CL 中受vdel影響的數(shù)據(jù)點(diǎn)的數(shù)量之間的關(guān)系較大。

4 實(shí)驗(yàn)結(jié)果與分析

本文第3 節(jié)研究了障礙物環(huán)境下的動(dòng)態(tài)數(shù)據(jù)集的單純型連續(xù)近鄰鏈查詢方法。分別提出了OB_DYNSCNNC_ADD 算法和OB_DYNSCNNC_DET 算法。本節(jié)在Pentium4，3.2 GHz CPU、8 GB 內(nèi)存，Windows XP 環(huán)境下，利用C++builder 6.0 對(duì)所提出的算法進(jìn)行實(shí)驗(yàn)分析。實(shí)驗(yàn)數(shù)據(jù)是在二維空間中利用筆者開發(fā)的空間數(shù)據(jù)生成軟件GEDATA4.0 隨機(jī)生成的模擬數(shù)據(jù)。

設(shè)數(shù)據(jù)集包含的數(shù)據(jù)量為n，障礙線的個(gè)數(shù)為g，待查詢的單純型連續(xù)近鄰鏈所包含的數(shù)據(jù)點(diǎn)的數(shù)目為w。ζ 表示在不同條件下OB_DYNSCNNC_ADD算法和OB_DYNSCNNC_DET 算法相對(duì)于反復(fù)調(diào)用障礙物環(huán)境下的靜態(tài)數(shù)據(jù)集的單純型連續(xù)近鄰鏈查詢算法進(jìn)行計(jì)算的直接方法(即OB_ZJB_UPDATE方法)的計(jì)算效率的比率。圖2 主要展示了以下3種情況的實(shí)驗(yàn)結(jié)果:

情況1 OB_DYNSCNNC_ADD 算法相對(duì)于OB_ZJB_UPDATE 方法的計(jì)算效率的比較。條件為n 不同，g 和w 相同;(圖2(a)中，g=177，w=225，縱坐標(biāo)ζ 表示OB_DYNSCNNC _ADD 算法相對(duì)于OB_ZJB_UPDATE 方法的計(jì)算效率的比率;橫坐標(biāo)表示數(shù)據(jù)集中包含的數(shù)據(jù)量，單位為4K，K=1 024)。

情況2 OB_DYNSCNNC _ADD 算法相對(duì)于OB_ ZJB_UPDATE 方法的計(jì)算效率的比較。條件為w不同，n 和g 相同;(圖2(b)中，n=10K，g=175，縱坐標(biāo)ζ 表示OB_DYNSCNNC _ADD 算法相對(duì)于OB_ZJB_UPDATE 方法的計(jì)算效率的比率;橫坐標(biāo)表示所查詢的單純型連續(xù)近鄰鏈所包含的數(shù)據(jù)點(diǎn)的個(gè)數(shù)，單位為K/10，K=1 024)。

情況3 OB_DYNSCNNC_DET 算法相對(duì)于OB_ZJB_UPDATE 方法的比較。條件為n 不同，g 和w 相同;(圖2(c)中，g=126，w=210，縱坐標(biāo)ζ 表示OB_DYNSCNNC_DET 算法相對(duì)于OB_ZJB_UPDATE 方法的計(jì)算效率的比率;橫坐標(biāo)表示數(shù)據(jù)集中包含的數(shù)據(jù)量，單位為3K，K=1 024)。

由圖2(a)可知，當(dāng)障礙線的個(gè)數(shù)g，連續(xù)近鄰鏈所包含的數(shù)據(jù)點(diǎn)的數(shù)目w 一定時(shí)，隨著數(shù)據(jù)集包含的數(shù)據(jù)量增多，OB_DYNSCNNC_ADD 算法相對(duì)于OB_ZJB_UPDATE 方法的計(jì)算效率的比率將明顯增大。圖2(a)中，當(dāng)n 為12K 時(shí)，其計(jì)算效率的比率為2.2，當(dāng)n 增加到60K 時(shí)則提高到4.3。由圖2(b)可知，當(dāng)數(shù)據(jù)集包含的數(shù)據(jù)量n，空間障礙線的個(gè)數(shù)g 一定時(shí)，隨著連續(xù)近鄰鏈所包含的數(shù)據(jù)點(diǎn)的數(shù)目w的增多，OB_DYNSCNNC_ADD算法的計(jì)算效率將明顯優(yōu)于OB_ZJB_UPDATE 方法。在圖2(b)中，當(dāng)w 為0.2K 時(shí)，其計(jì)算效率的比率為2.0，當(dāng)w 增加到1.6K 時(shí)則提高到5.5。由圖2(c)可知，當(dāng)障礙線的個(gè)數(shù)g，連續(xù)近鄰鏈所包含的數(shù)據(jù)點(diǎn)的數(shù)目w 一定時(shí)，隨著數(shù)據(jù)集包含的數(shù)據(jù)量n 增多，OOB_DYNSCNNC_DET 算法的計(jì)算效率將優(yōu)于OB_ZJB_UPDATE 方法。在圖2(c)中，當(dāng)n 為3K時(shí)，其計(jì)算效率的比率為1.8，當(dāng)n 增加到57K 時(shí)則提高到4.0。

圖2 實(shí)驗(yàn)結(jié)果比較

由圖2 的實(shí)驗(yàn)比較可知，在數(shù)據(jù)集的數(shù)據(jù)量，待查鏈包含數(shù)據(jù)點(diǎn)的個(gè)數(shù)和障礙線的個(gè)數(shù)較多時(shí)，本文提出的算法的優(yōu)勢(shì)更為明顯。在查詢過程中，算法對(duì)大量的冗余的數(shù)據(jù)點(diǎn)進(jìn)行了預(yù)先判斷和過濾，減少了不必要的冗余計(jì)算，從而較大程度地提高了查詢效率。

5 結(jié)束語(yǔ)

為了處理障礙物環(huán)境下的動(dòng)態(tài)數(shù)據(jù)集中的單純型連續(xù)近鄰鏈查詢問題，本文對(duì)數(shù)據(jù)集動(dòng)態(tài)增大和數(shù)據(jù)集動(dòng)態(tài)減小2 種情況下的障礙物環(huán)境下的單純型連續(xù)近鄰鏈查詢問題進(jìn)行研究，分別提出了OB_DYNSCNNC_ADD 算法和OB_DYNSCNNC_DET 算法，并分3 種情況對(duì)所提算法進(jìn)行了實(shí)驗(yàn)比較和分析。理論研究與實(shí)驗(yàn)表明，當(dāng)數(shù)據(jù)集的數(shù)據(jù)量、待查鏈包含數(shù)據(jù)點(diǎn)的個(gè)數(shù)和障礙線的個(gè)數(shù)較多時(shí)，本文提出的算法的優(yōu)勢(shì)較為明顯。未來的研究工作主要集中在以下兩方面:(1)將本文的方法和區(qū)域關(guān)系(如Vague 區(qū)域關(guān)系［15］)結(jié)合處理受限區(qū)域中的復(fù)雜單純型連續(xù)近鄰鏈查詢問題。(2)障礙物環(huán)境下的不確定單純型連續(xù)近鄰鏈查詢問題。

［1］郝忠孝.時(shí)空數(shù)據(jù)庫(kù)查詢與推理［M］.北京:科學(xué)出版社，2010.

［2］Song Zhexuan，Roussopoulos N.K Nearest Neighbor Search for Moving Query Point［C］//Proc.of the 7th International Symposium on Advances in Spatial and Temporal Databases.Berlin，Germany:Springer-Verlag，2001:79-96.

［3］Mouratidis K，Yiu M L，Papadias D.Continuous Nearest Neighbor Monitoring in Road Networks［C］//Proc.of VLDB.Seoul，Korea:［s.n.］，2006.

［4］Hu Ling，Jing Yinan，Ku W S，et al.Enforcing k Nearest Neighbor Query Integrity on Road Networks［C］//Proc.of the 20th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems.Redondo Beach，USA:ACM Press:346-349.

［5］Elmongui H G，Mokbel M F，Aref W G.Continuous Aggregate Nearest Neighbor Queries［J］.Geo Informatica，2013，17(1):63-95.

［6］Cheng R，Chen J，Mokbel M F.Probabilistic Verifiers:Evalutaing Constrained Nearest-neighbor Queries over Uncertain Data［C］//Proc.of International Conference on Data Engineering.Chicago，USA:［s.n.］:2008:973-982.

［7］Nutanong S，Tanin E，Zhang Rui.Incremental Evaluation of Visible Nearest Neighbor Queries ［J］.IEEE Transactions on Knowledge Engineering，2010，22(7):665-681.

［8］Gao Yunjun，Zheng Baihua，Chen Gencai，et al.Visible Reverse k-Nearest Neighbor Query Processing in Spatial Databases［J］.IEEE Transactions on Knowledge and Data Engineering，2009，21(5):1314-1327.

［9］袁培森，沙朝鋒，王曉玲，等.一種基于學(xué)習(xí)的高維數(shù)據(jù)c-近似最近鄰查詢算法［J］.軟件學(xué)報(bào)，2012，23(8):2018-2031

［10］苗東菁，石勝飛，李建中.一種局部相關(guān)不確定數(shù)據(jù)庫(kù)快照集合上的概率頻繁最近鄰算法［J］.計(jì)算機(jī)研究與發(fā)展，2011，48(10):1812-1822.

［11］李 松，郝忠孝.基于Voronoi 圖的反向最近鄰查詢方法研究［J］.哈爾濱工程大學(xué)學(xué)報(bào)，2008，29(3):261-265.

［12］李 松，張麗平，蔡志濤，等.數(shù)據(jù)集中單純型連續(xù)近鄰鏈查詢方法［J］.計(jì)算機(jī)工程，2012，38(4):82-83，87.

［13］Zhang Liping，Li Song，Li Lin，et al.Simple Continues Near Neighbor Chain Query of the Datasets Based on the R Tree ［J］.Journal of Computational Information Systems，2012，8(22):9159-9160.

［14］張麗平，李 林，李 松，等.預(yù)定數(shù)據(jù)鏈規(guī)模的單純型連續(xù)近鄰鏈查詢［J］.計(jì)算機(jī)工程，2012，38(10):51-53.

［15］李 松，郝忠孝.立體空間中的含核Vague 區(qū)域系表示與分析［J］.高技術(shù)通訊，2011，21(2):157-161.