蔣祎瑩，張麗平，金飛虎，郝曉紅

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

隨著基于位置服務(wù)的不斷發(fā)展，空間數(shù)據(jù)庫在交通路網(wǎng)系統(tǒng)、地理信息系統(tǒng)、決策支持系統(tǒng)等領(lǐng)域具有重要意義。近鄰查詢問題是當(dāng)今數(shù)據(jù)庫技術(shù)的熱點(diǎn)，查詢的結(jié)果通常是滿足查詢要求的空間數(shù)據(jù)或數(shù)據(jù)集合。最近鄰查詢是空間數(shù)據(jù)庫查詢領(lǐng)域的基礎(chǔ)，由于查詢需求的不斷變化，產(chǎn)生了許多變體。如近鄰查詢、方向最近鄰查詢、聚集最近鄰查詢、組最近鄰查詢、約束最近鄰查詢、隱私保護(hù)最近鄰查詢等。組最近鄰查詢是最近鄰查詢的變體之一，最早由Papadias 等人在文獻(xiàn)[11]中提出，并提出了三種基于R 樹的組最近鄰查詢方法。文獻(xiàn)[12]提出了空間數(shù)據(jù)庫中基于Voronoi 圖的線段組最近鄰查詢算法，該算法能夠有效處理空間數(shù)據(jù)庫中基于線段的組最近鄰查詢問題，彌補(bǔ)了現(xiàn)有的研究成果無法有效處理基于線段的組最近鄰查詢問題的不足。文獻(xiàn)[18]考慮到現(xiàn)實(shí)生活中許多大型空間對(duì)象不適合抽象為點(diǎn)，提出了障礙環(huán)境中線段組最近鄰查詢研究。

以上都是將數(shù)據(jù)對(duì)象抽象為點(diǎn)或線段進(jìn)行研究。在對(duì)現(xiàn)實(shí)中的對(duì)象進(jìn)行研究時(shí)，查詢對(duì)象集和目標(biāo)對(duì)象集的數(shù)據(jù)對(duì)象類型往往不是單一的，還要根據(jù)實(shí)際情況將空間對(duì)象抽象為包含點(diǎn)與線段的混合數(shù)據(jù)。例如，當(dāng)游客去一個(gè)城市旅行時(shí)，期望的住宿地點(diǎn)要離自己所規(guī)劃的景點(diǎn)、商業(yè)街、飯店、電影院以及車站等距離之和最小。其中飯店、電影院以及公交站點(diǎn)需要抽象為點(diǎn)，而旅游景點(diǎn)和商業(yè)街需要抽象為線段。這些需求涉及的往往是點(diǎn)與線段的混合數(shù)據(jù)，但是僅僅將數(shù)據(jù)對(duì)象抽象為單一的點(diǎn)或線段往往會(huì)影響其精確度及查詢效率，所得到的結(jié)果可能會(huì)有很大的誤差。如圖1，給定混合查詢對(duì)象集={,,}和混合數(shù)據(jù)對(duì)象集={,,…,p,,,…,pl}。如果基于傳統(tǒng)的組最近鄰查詢，線段要先抽象為點(diǎn)，得到抽象后的查詢對(duì)象集′={,,′}，數(shù)據(jù)對(duì)象集′={,,…,p,′,′,…,p′}。與′的距離(,′)=(,)+(,)+(,′)=11.5，而′與′的距 離為(′,′)=(′,)+(′,)+(′,′)=13.5。此 時(shí)距離′內(nèi)各個(gè)查詢對(duì)象距離之和最小的數(shù)據(jù)對(duì)象為。而實(shí)際與的據(jù)離為(,)=(,)+(,)+(,)=11,與的距離為(,)=(,)+(,)+(,)=8.2，可得(,)＞(,)，因此實(shí)際到內(nèi)各個(gè)查詢對(duì)象距離之和最小的數(shù)據(jù)對(duì)象為，此時(shí)用傳統(tǒng)的組最近鄰查詢方法解決該問題存在較大誤差。

圖1 混合數(shù)據(jù)組最近鄰Fig.1 Group nearest neighbor for mixed data

為了提高查詢的精確度和查詢效率，本文針對(duì)混合數(shù)據(jù)提出了混合數(shù)據(jù)組最近鄰查詢方法。本文的主要貢獻(xiàn)有以下四方面:

（1）現(xiàn)實(shí)生活中的一些數(shù)據(jù)集不能簡單地抽象為點(diǎn)集或線段集，有時(shí)還要根據(jù)實(shí)際情況將其抽象為包含點(diǎn)與線段的混合數(shù)據(jù)集。為解決此問題，本文提出了混合數(shù)據(jù)組最近鄰查詢問題，并給出了混合數(shù)據(jù)組最近鄰查詢的定義。

（2）針對(duì)數(shù)據(jù)集中數(shù)據(jù)對(duì)象為混合數(shù)據(jù)的情況，本文提出了混合Voronoi 的概念并給出了混合Voronoi的構(gòu)建方法。

（3）根據(jù)混合Voronoi 圖的性質(zhì)，提出了剪枝算法。所提算法能過濾掉大量的冗余數(shù)據(jù)并準(zhǔn)確、有效地得到混合數(shù)據(jù)組最近鄰的候選集合。

（4）本文提出精煉算法，根據(jù)不同對(duì)象之間的距離計(jì)算方法，對(duì)剪枝階段得到的候選集進(jìn)行進(jìn)一步的篩選，從而得到混合數(shù)據(jù)組最近鄰查詢結(jié)果。

1 定義與性質(zhì)

根據(jù)已有的組最近鄰和Voronoi 圖的定義，本文提出混合數(shù)據(jù)組最近鄰和混合Voronoi圖的概念。

（混合數(shù)據(jù)Voronoi 圖（mixed data Voronoi diagram，MDV））給定一組混合數(shù)據(jù)集={，,…,p,,,…,pl}。并給出混合數(shù)據(jù)集中每個(gè)線段的端點(diǎn)，其中2 ＜＜∞，且當(dāng)≠時(shí)，p≠p，其中,∈I={1,2,…,};2 ＜＜∞，且當(dāng)≠時(shí)，pl≠pl，其中,∈I={1,2,…,}?；旌蟅oronoi 圖將平面分成若干個(gè)相連區(qū)域，稱為Voronoi單元，令∈,每個(gè)數(shù)據(jù)對(duì)象mp所生成的Voronoi單元可定義為(mp)，由()={(),(),…,(mp)} 所定義的圖形稱為混合Voronoi圖。

基于混合Voronoi 圖的構(gòu)建原理，得到混合Voronoi圖的性質(zhì)如下：

Voronoi 邊上的點(diǎn)到這條Voronoi 邊所在Voronoi多邊形的生成對(duì)象的距離相等。

如果空間中某一對(duì)象在混合Voronoi 圖的某個(gè)Voronoi 單元內(nèi)，該對(duì)象的最近鄰為其所在Voronoi單元的生成對(duì)象。

2 混合數(shù)據(jù)Voronoi圖的構(gòu)建

與構(gòu)建傳統(tǒng)Voronoi圖相比，構(gòu)建混合Voronoi圖需要判斷生成對(duì)象的類型和位置關(guān)系，還要考慮不同類型的對(duì)象之間的距離計(jì)算方式。

點(diǎn)與點(diǎn)之間的距離平分線為兩點(diǎn)所連線段的垂直平分線，因此兩點(diǎn)之間的Voronoi 邊由兩點(diǎn)連線的垂直平分線構(gòu)成。點(diǎn)與線段之間距離平分線分兩部分構(gòu)建：在線段直接影響區(qū)域內(nèi)，點(diǎn)與線段的距離平分線為以點(diǎn)為焦點(diǎn)，以線段為準(zhǔn)線的拋物線；在線段直接影響區(qū)域外，點(diǎn)與線段的距離平分線為點(diǎn)與線段的端點(diǎn)連線的垂直平分線。當(dāng)點(diǎn)在線段的直接影響區(qū)域內(nèi)時(shí)如圖2，給定點(diǎn)與線段，構(gòu)建()，點(diǎn)與線段在()內(nèi)的距離平分線為以點(diǎn)為焦點(diǎn)，線段為準(zhǔn)線的拋物線；點(diǎn)與線段在()外的距離平分線為線段、的垂直平分線、。當(dāng)點(diǎn)在線段的直接影響區(qū)域外時(shí)，如圖2 中點(diǎn)與線段。

圖2 點(diǎn)與線段距離平分線的構(gòu)建Fig.2 Construction of bisector of distance between point and line segment

線段與線段的距離平分線分三部分構(gòu)建，在兩條線段共同的直接影響區(qū)域內(nèi)，根據(jù)角平分線性質(zhì)，兩條線段的距離平分線為兩線段延長線相交構(gòu)成的角度的角平分線；在一條線段()的直接影響區(qū)域內(nèi)一條線段()的直接影響區(qū)域外，兩線段的距離平分線為以的一端點(diǎn)為焦點(diǎn)，以為準(zhǔn)線的拋物線；在兩條線段直接影響區(qū)域外，兩條線段的距離平分線為兩條線段端點(diǎn)連線的垂直平分線。如圖3，在()與()內(nèi)，、的距離平分線為；在()外()內(nèi)，線段、的距離平分線為以的端點(diǎn)為焦點(diǎn)，為準(zhǔn)線構(gòu)成的拋物線；同理可得，()內(nèi)()外的區(qū)域，為線段、的距離平分線；在()外()外的區(qū)域，線段、的距離平分線分別為線段、的垂直平分線、。、在各個(gè)區(qū)域內(nèi)的距離平分線相交所構(gòu)成的分界線為兩條線段的距離平分線。

圖3 線段與線段距離平分線的構(gòu)建Fig.3 Construction of bisector of distance between line segments

本文采用增量法構(gòu)建混合Voronoi圖。與構(gòu)建傳統(tǒng)Voronoi圖相比，構(gòu)建混合Voronoi圖要先確定生成對(duì)象的數(shù)據(jù)類型以及它們之間的位置關(guān)系，并根據(jù)不同的數(shù)據(jù)類型分別構(gòu)建Voronoi 邊，該過程的執(zhí)行次數(shù)為有限次，因此根據(jù)增量法構(gòu)建混合Voronoi 圖的時(shí)間復(fù)雜度與傳統(tǒng)Voronoi相同，均為(lb)。

3 混合數(shù)據(jù)組最近鄰查詢

本文提出的混合數(shù)據(jù)組最近鄰查詢方法分為3個(gè)階段：構(gòu)建混合Voronoi圖；對(duì)數(shù)據(jù)集進(jìn)行剪枝得到候選集；對(duì)候選集進(jìn)行精煉得到混合數(shù)據(jù)組最近鄰查詢結(jié)果。對(duì)查詢對(duì)象進(jìn)行剪枝處理時(shí)，需要構(gòu)建基于混合數(shù)據(jù)的查詢凸包，本文稱混合凸包。

定義3（混合凸包（mixed data convex hull，MDCH））將混合查詢對(duì)象集中的查詢對(duì)象相互連接構(gòu)成一個(gè)凸多邊形，使得所有查詢對(duì)象均在此區(qū)域內(nèi)，所圍成的區(qū)域?yàn)榛旌贤拱Ｅc混合凸包相交的Voronoi單元的外邊界構(gòu)成的區(qū)域?yàn)榛旌喜樵儗?duì)象集的影響區(qū)域，本文用()表示。

3.1 剪枝階段

當(dāng)查詢對(duì)象為單個(gè)時(shí)，混合數(shù)據(jù)組最近鄰查詢即為混合數(shù)據(jù)最近鄰查詢，需要對(duì)查詢對(duì)象為點(diǎn)和查詢對(duì)象為線段分別進(jìn)行處理。

當(dāng)查詢對(duì)象為點(diǎn)時(shí)，該點(diǎn)所在Voronoi單元的生成對(duì)象為此時(shí)的最近鄰查詢結(jié)果。

當(dāng)查詢對(duì)象為線段時(shí)，與線段相交的Voronoi單元的生成對(duì)象可能為最近鄰查詢結(jié)果。

如果查詢對(duì)象為點(diǎn)，該點(diǎn)所在Voronoi 單元的生成對(duì)象為混合數(shù)據(jù)最近鄰查詢結(jié)果。

根據(jù)混合Voronoi 圖的最近鄰特性，查詢點(diǎn)與其所在的Voronoi單元的生成對(duì)象的距離小于查詢點(diǎn)與其他數(shù)據(jù)對(duì)象的距離。因此查詢點(diǎn)所在的Voronoi單元的生成對(duì)象為最近鄰查詢結(jié)果。證畢。

如果查詢對(duì)象為線段，與該查詢對(duì)象相交的Voronoi單元的生成對(duì)象可能為混合數(shù)據(jù)最近鄰查詢結(jié)果。

查詢線段被Voronoi 單元切分為不同的部分，根據(jù)混合Voronoi圖的最近鄰特性，各個(gè)部分與其所在的Voronoi單元的生成對(duì)象的距離小于到其他任意一個(gè)數(shù)據(jù)對(duì)象的距離。因此混合數(shù)據(jù)最近鄰一定在與查詢線段相交的Voronoi單元的生成對(duì)象中。證畢。

基于以上討論，本文給出單個(gè)查詢對(duì)象的組最近鄰查詢過濾算法。

MDNN_FILTER()

輸入：查詢對(duì)象集，混合數(shù)據(jù)對(duì)象集。

輸出：最近鄰查詢結(jié)果候選集。

1.←?；

2.Create_MDV()；

3.if 查詢對(duì)象為點(diǎn)

4.for=1 to.

5. if∩(mp)≠?

6.←mp；

7. else 對(duì)mp進(jìn)行剪枝；

8.if 查詢對(duì)象為線段

9.for=1 to.

10.if∩(mp)≠?

11.←mp；

12.else 對(duì)mp進(jìn)行剪枝；

13.return.

算法1 先構(gòu)建混合Voronoi 圖，判斷查詢對(duì)象的類型。如果查詢對(duì)象為點(diǎn)，將該點(diǎn)所在的Voronoi 單元生成對(duì)象加入候選集；如果查詢對(duì)象為線段，將與該線段相交的Voronoi單元生成對(duì)象加入候選集。該算法利用for 語句進(jìn)行循環(huán)，設(shè)數(shù)據(jù)集對(duì)象共有個(gè)，for 循環(huán)語句的執(zhí)行次數(shù)為次，因此該算法的時(shí)間復(fù)雜度為()。

當(dāng)混合查詢對(duì)象集中查詢對(duì)象個(gè)數(shù)大于1 時(shí)，首先判斷查詢對(duì)象是否能夠構(gòu)成凸包，然后根據(jù)Voronoi 的特性以及查詢對(duì)象的影響區(qū)域，分別給出查詢對(duì)象能構(gòu)成凸包和查詢對(duì)象不能構(gòu)成凸包的過濾算法，得到混合數(shù)據(jù)組最近鄰查詢候選集。

當(dāng)各個(gè)查詢對(duì)象首尾相連在一條線段上時(shí)，不能構(gòu)成查詢凸包。

當(dāng)查詢對(duì)象不能構(gòu)成凸包時(shí)，對(duì)于任意一個(gè)不與該線段相交的Voronoi 單元的生成對(duì)象，在與該線段相交的Voronoi單元的生成對(duì)象中一定存在一個(gè)數(shù)據(jù)對(duì)象′，使得′到各個(gè)查詢對(duì)象的距離之和小于到查詢對(duì)象的距離之和。

如圖4，任取兩個(gè)數(shù)據(jù)對(duì)象構(gòu)成混合查詢對(duì)象集={,},為查詢線段，為查詢點(diǎn)，′與、、所在的Voronoi 單元相交。任取一個(gè)不與相交的Voronoi單元的生成點(diǎn)，例如。為的一個(gè)端點(diǎn)，為的一個(gè)端點(diǎn)，為線段與Voronoi邊的交點(diǎn)。到各個(gè)查詢對(duì)象的距離之 和(,)=()+()=||+||。到各個(gè)查詢對(duì)象的距離之和(,)=()+()=||+||+||，根據(jù)Voronoi圖性質(zhì)可知||=||，因此||=||+||。由三角形三邊關(guān)系可得||+||＞||。因此||＞||。同理可證||＜||，因此到各個(gè)查詢對(duì)象的距離之和大于到各個(gè)查詢對(duì)象的距離之和。同理可得，對(duì)于任意一個(gè)不與查詢對(duì)象相交Voronoi單元的生成對(duì)象，在與查詢對(duì)象相交的Voronoi 單元的生成對(duì)象集中一定存在一個(gè)數(shù)據(jù)對(duì)象，到各個(gè)查詢對(duì)象的距離之和小于到各個(gè)查詢對(duì)象的距離之和。證畢。

圖4 查詢對(duì)象的剪枝Fig.4 Pruning of query objects

當(dāng)查詢對(duì)象集能構(gòu)成凸包時(shí)，構(gòu)建()和()。

對(duì)于任意一個(gè)()外的對(duì)象，在()內(nèi)，一定存在一個(gè)對(duì)象到各個(gè)查詢對(duì)象的距離之和小于到各個(gè)查詢對(duì)象的距離之和。

如圖4，任取數(shù)據(jù)對(duì)象、、構(gòu)成混合查詢對(duì)象集={,,},為()內(nèi)一數(shù)據(jù)對(duì)象，為()外的一個(gè)數(shù)據(jù)對(duì)象，到查詢各個(gè)對(duì)象的距離之和為(,)=(,)+(，)+(,)，到查詢各個(gè)對(duì)象的距離之和為(,)=(,)+(,)+(,)。連接與Voronoi 邊的交點(diǎn)為的中點(diǎn)。做的垂直平分線，因此||＞||,||＞||,||＞||,(,)＞(,)?？勺C得如果查詢對(duì)象能夠構(gòu)成凸包，()內(nèi)的生成對(duì)象到各個(gè)查詢對(duì)象的距離之和一定小于()外的對(duì)象到各個(gè)查詢對(duì)象的距離之和。同理，對(duì)于任意一個(gè)()外的數(shù)據(jù)對(duì)象，在()內(nèi)一定存在一個(gè)數(shù)據(jù)對(duì)象到各個(gè)查詢對(duì)象的距離之和小于到各個(gè)查詢對(duì)象的距離之和。

如果查詢對(duì)象集中所有查詢對(duì)象均與同一個(gè)Voronoi多邊形相交，那么該Voronoi多邊形的生成對(duì)象一定是混合數(shù)據(jù)組最近鄰查詢結(jié)果。

根據(jù)Voronoi圖的最近鄰特性可知，查詢對(duì)象集中所有查詢對(duì)象與同一Voronoi 多邊形相交，那么每個(gè)查詢對(duì)象的最近鄰均為該Voronoi單元的生成對(duì)象。因此該生成對(duì)象到各個(gè)查詢對(duì)象的距離之和小于任意其他對(duì)象到各個(gè)查詢對(duì)象的距離之和，那么該Voronoi單元的生成對(duì)象一定是混合數(shù)據(jù)組最近鄰查詢結(jié)果。如圖4，混合查詢對(duì)象集={,，}都在數(shù)據(jù)對(duì)象的Voronoi 單元中，因此為的組最近鄰查詢結(jié)果。

當(dāng)查詢對(duì)象集中的查詢對(duì)象數(shù)量不為1 時(shí)，分為查詢對(duì)象能夠構(gòu)成凸包和查詢對(duì)象不能構(gòu)成凸包兩種情況，可得剪枝規(guī)則3～5。

當(dāng)所有查詢對(duì)象不能構(gòu)成凸包時(shí)，即所有查詢對(duì)象首尾相連在一條線段上時(shí)，對(duì)不與該線段相交的Voronoi單元的生成對(duì)象進(jìn)行剪枝。

當(dāng)所有查詢對(duì)象能夠構(gòu)成凸包時(shí)，如果一個(gè)數(shù)據(jù)對(duì)象生成的Voronoi 單元不在()內(nèi)，那么這個(gè)數(shù)據(jù)對(duì)象一定不是混合數(shù)據(jù)組最近鄰查詢結(jié)果。

如果所有查詢對(duì)象與同一個(gè)Voronoi單元相交，那么該Voronoi 單元生成對(duì)象為組最近鄰查詢結(jié)果。

多個(gè)查詢對(duì)象的組最近鄰過濾算法如下。

MDGNN_FILTER()

輸入：混合查詢對(duì)象集，混合數(shù)據(jù)對(duì)象集。

輸出：最近鄰候選集，MDGNN()。

1.Create_MDV()；

2.if 所有的查詢對(duì)象與同一個(gè)Voronoi單元相交

3.return 該Voronoi 單元生成對(duì)象為

4.if 查詢對(duì)象不能構(gòu)成凸包

5.將查詢對(duì)象依次連接構(gòu)成新的查詢線段

6.for=1 to.

7.if∩(pl)≠?

8.←pl；

9.else if 查詢對(duì)象能構(gòu)成凸包

10.for=1 to.

11.創(chuàng)建()；

12.for=1 to.

13. if()∩(pl)≠?

14.←pl；

15.return.

算法2 首先構(gòu)建混合Voronoi 圖，如果所有查詢對(duì)象均與同一個(gè)Voronoi單元相交，則該Voronoi單元的生成對(duì)象為混合數(shù)據(jù)組最近鄰的查詢結(jié)果。接著根據(jù)查詢對(duì)象集是否能構(gòu)成凸包，分別對(duì)數(shù)據(jù)對(duì)象進(jìn)行剪枝，得到混合數(shù)據(jù)組最近鄰查詢的候選集。設(shè)數(shù)據(jù)集中數(shù)據(jù)對(duì)象的個(gè)數(shù)為，查詢對(duì)象的個(gè)數(shù)為，執(zhí)行的次數(shù)最多為×次，則時(shí)間復(fù)雜度為()，構(gòu)建凸包的時(shí)間復(fù)雜度為()，因此算法2 的時(shí)間復(fù)雜度為()。

3.2 精煉階段

精煉階段主要是根據(jù)剪枝階段得到的候選集，對(duì)數(shù)據(jù)進(jìn)行進(jìn)一步篩選，最后得到混合數(shù)據(jù)的組最近鄰查詢結(jié)果。

查詢對(duì)象與數(shù)據(jù)對(duì)象之間的距離計(jì)算分為點(diǎn)與點(diǎn)、點(diǎn)與線段、線段與線段之間距離的計(jì)算。

（1）點(diǎn)與點(diǎn)之間的距離：點(diǎn)與點(diǎn)之間的距離為兩點(diǎn)之間的歐式距離。

（2）點(diǎn)與線段之間的距離：點(diǎn)與線段的距離分為兩種情況進(jìn)行計(jì)算。當(dāng)在()外時(shí)，點(diǎn)與線段的距離為與兩端點(diǎn)距離的最小值。當(dāng)點(diǎn)在()內(nèi)時(shí)，過點(diǎn)作線段的垂線段，點(diǎn)與垂足的距離就為此時(shí)點(diǎn)與線段的最短距離。

（3）線段與線段之間的距離：計(jì)算線段與線段的距離需要先確定兩條線段的位置關(guān)系。

線段與線段的位置關(guān)系，需要借助內(nèi)傾端點(diǎn)與外傾端點(diǎn)來判斷。如圖5，給定線段、、,設(shè)點(diǎn)∈,∈。、在線段的直接影響區(qū)域內(nèi)，過點(diǎn)、做的平行線段、，線段與線段在的兩側(cè)，稱為線段相對(duì)于線段的外傾端點(diǎn)；線段與線段在的同一側(cè)，因此稱為線段相對(duì)于線段的內(nèi)傾端點(diǎn)。

（1）線段與線段的位置關(guān)系1：一條線段的兩個(gè)端點(diǎn)都在線段直接影響區(qū)域內(nèi)，則該線段的兩個(gè)端點(diǎn)到的最小距離為兩條線段的最小距離。

如圖5，給定線段、,令,∈()，為相對(duì)于的外傾端點(diǎn)，(,)＞(,)。則與的最短距離為點(diǎn)到的距離。

（2）線段與線段的位置關(guān)系2：兩條直線各有一個(gè)點(diǎn)在另一條線段的直接影響區(qū)域中。當(dāng)一個(gè)點(diǎn)為內(nèi)傾端點(diǎn)，一個(gè)點(diǎn)為外傾端點(diǎn)時(shí)，外傾端點(diǎn)到另一條線段的距離為兩條線段的最小距離。當(dāng)兩個(gè)點(diǎn)都為內(nèi)傾端點(diǎn)時(shí)，則兩條線段的另外兩個(gè)端點(diǎn)之間的距離為兩條線段的最小距離。

如圖5，給定線段、、，點(diǎn)∈() 且為相對(duì)于的外傾端點(diǎn)；點(diǎn)∈()且為相對(duì)于的內(nèi)傾端點(diǎn)，則(,)=(,)?！?)。點(diǎn)∈()且為相對(duì)于的內(nèi)傾端點(diǎn)，當(dāng)點(diǎn)∈()且為相對(duì)于的內(nèi)傾端點(diǎn)，則(,)=(,)。

（3）線段與線段的位置關(guān)系3：只有一條線段的一個(gè)端點(diǎn)在另一條線段的直接影響區(qū)域內(nèi)時(shí)，如果這個(gè)端點(diǎn)為外傾端點(diǎn)，則這個(gè)端點(diǎn)到線段的最小距離為兩條線段的最小距離。如果這個(gè)端點(diǎn)為內(nèi)傾端點(diǎn)，則這個(gè)端點(diǎn)所在線段的另一個(gè)端點(diǎn)與另一條線段兩個(gè)端點(diǎn)的最小距離為兩條線段的最小距離。

如圖5，給定線段、、，點(diǎn)∈()且為相對(duì)于的外傾端點(diǎn)，則(,)=(,)。同理(,)=(,)。

圖5 線段與線段位置關(guān)系Fig.5 Position relationship between line segments

（4）線段與線段的位置關(guān)系4：兩條線段的兩個(gè)端點(diǎn)均不在另一條線段的影響區(qū)域中，兩條線段的最近距離為兩條線段的端點(diǎn)之間的距離的最小值。

基于以上討論，下面給出計(jì)算最短距離的算法。

(，)

輸入：空間對(duì)象，。

輸出：(，)。

1.if，均為點(diǎn)；

2.(，)=(，)；

3.if，一個(gè)為點(diǎn)，一個(gè)為線段，令為點(diǎn)，為線段，的左右端點(diǎn)為，；

4.Create()；

5.if在()內(nèi)

6.(，)為點(diǎn)到線段垂線段的距離；

7.else在()外

8(，)=min{(，)，(，)}；

9.if，均為線段

10.令為且端點(diǎn)為，，令為且端點(diǎn)為，；

11.Create()，()；

12.if，滿足位置關(guān)系1

13.if，in()

14. 令∈(，)為外傾端點(diǎn)，

15.(，)=(，)；

16.else if，in()

17. if∈(，)為外傾端點(diǎn)

18.(，)=(，)；

19.if，滿足位置關(guān)系2

20.令為在()內(nèi)的端點(diǎn)，為在()內(nèi)的端點(diǎn)；

21.if為的內(nèi)傾端點(diǎn)且為的外傾端點(diǎn)

22.(，)=(，)；

23.if為的外傾端點(diǎn)且為的內(nèi)傾端點(diǎn)

24.(，)=(，)；

25.if為的內(nèi)傾端點(diǎn)且為的內(nèi)傾端點(diǎn)

26.′在()外，′在()外；

27.(，)=(′,′)；

28.if，滿足位置關(guān)系3

29. if為在()內(nèi)的端點(diǎn)

30. if為的外傾端點(diǎn)

31.(，)=(，)；

32. else if為的內(nèi)傾端點(diǎn)

33. 令′為在()外的端點(diǎn)；

34.(，)=(′，)；

35. if∈{，}andin()

36. if為的外傾端點(diǎn)

37.(，)=(，)；

38. else if為的內(nèi)傾端點(diǎn)

39. 令′為在()外的端點(diǎn)；

40.(，)=(，)；

41.if，滿足位置關(guān)系4

42.(，)=min((，)，(，)，(，)，(，))；

43.return(，).

算法3 首先判斷傳入的兩個(gè)對(duì)象是點(diǎn)還是線段，如果均為點(diǎn)，可直接計(jì)算兩點(diǎn)間的距離(1～2 行)；如果一個(gè)為點(diǎn)，一個(gè)為線段，根據(jù)點(diǎn)與線段的位置關(guān)系計(jì)算點(diǎn)與線段的最短距離(3～8 行)；如果兩個(gè)數(shù)據(jù)對(duì)象均為線段，根據(jù)兩條線段的直接影響區(qū)域判斷兩條線段的位置關(guān)系，分段計(jì)算兩個(gè)對(duì)象之間的最短距離(9～42行)。其中候選集中的數(shù)據(jù)對(duì)象的數(shù)量與查詢對(duì)象的數(shù)量均為常數(shù)，因此判斷對(duì)象的類型、構(gòu)建線段直接影響區(qū)域、計(jì)算兩個(gè)數(shù)據(jù)對(duì)象的最短距離的執(zhí)行次數(shù)均為有限次，最終算法3 的時(shí)間復(fù)雜度為()。

得到混合數(shù)據(jù)組最近鄰查詢結(jié)果需要對(duì)過濾階段得到的候選集合進(jìn)行進(jìn)一步篩選，根據(jù)不同數(shù)據(jù)類型之間的距離計(jì)算方式，本小節(jié)給出精煉算法。

MDGNN_REFINE(，)

輸入：候選集，混合查詢對(duì)象集。

輸出：′。

1.for mpin

2.(mp，)=0；

3.for mqin

4.(mp，)+=(mp，mq)；

5.if＞(mp，)

6.=(mp，)，′←mp;

7.return′.

算法4 首先判斷候選集中數(shù)據(jù)對(duì)象個(gè)數(shù)是否為1，如果中數(shù)據(jù)對(duì)象個(gè)數(shù)為1，可直接得到組最近鄰查詢結(jié)果()。如果中數(shù)據(jù)對(duì)象個(gè)數(shù)大于1，根據(jù)點(diǎn)與點(diǎn)、點(diǎn)與線段、線段與線段的距離計(jì)算方法計(jì)算每個(gè)數(shù)據(jù)對(duì)象到各個(gè)查詢對(duì)象的距離之和(mp,)。通過比較(PL,)的大小最終得到組最近鄰查詢結(jié)果。

MDGNN_Query(，)

輸入：混合查詢對(duì)象集，混合數(shù)據(jù)對(duì)象集。輸出：查詢對(duì)象的組最近鄰。

1.Create_MDV()；

2.if的數(shù)量為1

3.CS←MDGNN_FILTER()；

4.if的數(shù)量大于1

5.CS←MDGNN_FILTER()；

6.MDGNN←MDGNN_REFINE(，)；

7.return MDGNN.

設(shè)的數(shù)量為，首先對(duì)構(gòu)建混合Voronoi圖，時(shí)間復(fù)雜度為(lb)；然后判斷內(nèi)查詢對(duì)象的數(shù)量，調(diào)用MDGNN_FILTER()算法或MDGNN_FILTER()算法得到候選集；接著調(diào)用MDGNN_REFINE(,)進(jìn)一步對(duì)進(jìn)行篩選。最終混合數(shù)據(jù)組最近鄰查詢的時(shí)間復(fù)雜度為(lb)。

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

本章使用兩種對(duì)比算法與本文算法進(jìn)行實(shí)驗(yàn)比較，分別測(cè)試數(shù)據(jù)對(duì)象的數(shù)量與查詢對(duì)象的數(shù)量對(duì)運(yùn)行時(shí)間的影響，數(shù)據(jù)對(duì)象的密度對(duì)候選點(diǎn)數(shù)量的影響，查詢次數(shù)對(duì)算法準(zhǔn)確率的影響。本文研究對(duì)象為混合數(shù)據(jù)集，但是目前已有成果中并沒有直接解決這種復(fù)雜混合數(shù)據(jù)的組最近鄰查詢方法，因此無法和已有方法直接進(jìn)行實(shí)驗(yàn)比較，現(xiàn)將已有的算法進(jìn)行適當(dāng)調(diào)整，得到兩個(gè)對(duì)比算法。

本文第1 個(gè)對(duì)比算法MDGNN_Basic1 為在已有算法基礎(chǔ)上進(jìn)行綜合調(diào)整得出的，MDGNN_Basic1主要調(diào)用文獻(xiàn)[12]中提出的基于Voronoi 圖的線段組最近鄰查詢算法（line segment group nearest neighbor，LGNN）和文獻(xiàn)[13]中提出的基于Voronoi圖的組最近鄰查詢算法（group nearest neighbor，GNN）兩個(gè)已有的算法共同完成混合數(shù)據(jù)組最近鄰查詢?nèi)蝿?wù)。主要思想是將混合查詢數(shù)據(jù)集中的查詢點(diǎn)和查詢線段分開處理，所有的查詢點(diǎn)組成新的查詢點(diǎn)集為，調(diào)用文獻(xiàn)[13]中的GNN 得到查詢點(diǎn)集的組最近鄰查詢結(jié)果候選集；所有的查詢線段組成新的查詢線段集，調(diào)用文獻(xiàn)[12]中的LGNN 得到查詢線段集的組最近鄰查詢結(jié)果候選集，將兩次調(diào)用的結(jié)果進(jìn)行組合，通過計(jì)算比較得到混合數(shù)據(jù)組最近鄰結(jié)果。本文的第2 個(gè)對(duì)比算法為MDGNN_Basic2，利用文獻(xiàn)[2]中提出的基于SI-樹的LNN 算法和文獻(xiàn)[4]中所提出的KNNSearch(,)算法，令為1，KNNSearch(,)算法即為查找的最近鄰NNSearch()，找到查詢對(duì)象集中每個(gè)點(diǎn)和每條線段的最近鄰，然后將它們進(jìn)行合并處理后進(jìn)行計(jì)算比較，從而實(shí)現(xiàn)混合數(shù)據(jù)組最近鄰查詢。

本文通過實(shí)驗(yàn)對(duì)所提算法的性能進(jìn)行分析。實(shí)驗(yàn)環(huán)境為：2.50 GHz CPU，8 GB 內(nèi)存，500 GB 硬盤，用Microsoft Visual Studio.NET2003 編程實(shí)現(xiàn)，Windows10系統(tǒng)。實(shí)驗(yàn)使用的數(shù)據(jù)集由真實(shí)數(shù)據(jù)集和人工合成數(shù)據(jù)集兩部分組成，在實(shí)驗(yàn)中對(duì)數(shù)據(jù)集進(jìn)行了適當(dāng)?shù)恼{(diào)整和優(yōu)化。真實(shí)數(shù)據(jù)集是圣華金縣（TG）道路網(wǎng)絡(luò)，共有18 263 個(gè)節(jié)點(diǎn)，數(shù)據(jù)集包括節(jié)點(diǎn)ID、標(biāo)準(zhǔn)化坐標(biāo)、標(biāo)準(zhǔn)化坐標(biāo)(http://www.cs.utah.edu/～lifeifei/research/tpq/TG.cnode)。人工合成數(shù)據(jù)集主要是取部分真實(shí)數(shù)據(jù)集中的點(diǎn)兩兩連接，連接成線段。所有的點(diǎn)均不在線段上，所有的線段均互不相交。執(zhí)行100 次查詢?nèi)∑骄?，然后?duì)比3 種算法的測(cè)試結(jié)果。

首先分析數(shù)據(jù)集中數(shù)據(jù)對(duì)象的數(shù)量對(duì)運(yùn)行時(shí)間的影響。隨機(jī)選取真實(shí)對(duì)象集中的節(jié)點(diǎn)，并隨機(jī)選取真實(shí)對(duì)象集中的節(jié)點(diǎn)兩兩連接生成線段，構(gòu)成包含混合數(shù)據(jù)的數(shù)據(jù)對(duì)象集與包含混合數(shù)據(jù)的查詢對(duì)象集。數(shù)據(jù)對(duì)象的數(shù)量分別為1 000、2 000、3 000、4 000、5 000、6 000、7 000。如圖6，在數(shù)據(jù)集的數(shù)量逐漸增多的情況下，MDGNN_Query 算法平均執(zhí)行時(shí)間分別為0.099 s、0.260 s、0.462 s、0.601 s、0.747 s、0.839 s、1.001 s；MDGNN_Basic1 算法平均執(zhí)行時(shí)間分別為0.167 s、0.378 s、0.581 s、0.800 s、0.962 s、1.121 s、1.261 s；MDGNN_Basic2 算法平均執(zhí)行時(shí)間分別為0.322 s、0.580 s、0.798 s、1.112 s、1.208 s、1.400 s、1.552 s，本文算法相對(duì)于其他兩種算法平均分別提升了23.8%、42.4%。

圖6 數(shù)據(jù)對(duì)象的數(shù)量變化對(duì)運(yùn)行時(shí)間的影響Fig.6 Impact of changes in the number of data objects on running time

實(shí)驗(yàn)條件不變，進(jìn)一步分析數(shù)據(jù)集中數(shù)量變化對(duì)算法I/O 代價(jià)的影響，如圖7 所示。在數(shù)據(jù)集的數(shù)量逐漸增多的情況下，MDGNN_Query 算法的I/O 代價(jià)分別為100、150、197、255；MDGNN_Basic1 算法的I/O 代價(jià)分別為135、181、235、315；MDGNN_Basic2算法執(zhí)行的I/O 代價(jià)分別為224、266、464、237，本文算法相對(duì)于其他兩種算法平均分別提升了18.9%、41.0%。

圖7 數(shù)據(jù)對(duì)象的數(shù)量變化對(duì)I/O 代價(jià)的影響Fig.7 Impact of changes in the number of data objects on I/O cost

圖8 給出了數(shù)據(jù)對(duì)象的密度對(duì)候選對(duì)象數(shù)量的影響。隨機(jī)選取真實(shí)對(duì)象集中的節(jié)點(diǎn)，再隨機(jī)選取真實(shí)對(duì)象集中的節(jié)點(diǎn)兩兩連接生成線段，構(gòu)成包含混合數(shù)據(jù)的數(shù)據(jù)對(duì)象集與包含混合數(shù)據(jù)的查詢對(duì)象集。每單位面積數(shù)據(jù)對(duì)象的個(gè)數(shù)分別為15、30、45、60、75、90。從圖中可以看出隨著單位面積內(nèi)數(shù)據(jù)對(duì)象數(shù)量不斷增加，本文算法相對(duì)于其他兩組算法平均分別提升了17.9%、35.1%。

圖8 數(shù)據(jù)對(duì)象的密度對(duì)候選對(duì)象數(shù)量的影響Fig.8 Impact of density of data objects on the number of candidate objects

接著分析查詢對(duì)象集的數(shù)量變化對(duì)運(yùn)行時(shí)間的影響。隨機(jī)選取真實(shí)對(duì)象集中的節(jié)點(diǎn)，并隨機(jī)選取真實(shí)對(duì)象集中的節(jié)點(diǎn)兩兩連接生成線段，構(gòu)成包含混合數(shù)據(jù)的數(shù)據(jù)對(duì)象集與包含混合數(shù)據(jù)的查詢對(duì)象集。查詢對(duì)象的數(shù)量為2、4、6、8、10、16、24、32。測(cè)試不同數(shù)量的查詢對(duì)象對(duì)算法CPU 時(shí)間的影響。如圖9，查詢對(duì)象的數(shù)量逐漸增多時(shí)，MDGNN_Query算法執(zhí)行的平均時(shí)間分別為0.322 s、0.401 s、0.523 s、0.606 s、0.712 s、0.823 s、0.920 s；MDGNN_Basic1 算法執(zhí)行的平均時(shí)間分別為0.404 s、0.582 s、0.717 s、0.830 s、0.997 s、1.093 s、1.117 s；MDGNN_Basic2 算法執(zhí)行的平均時(shí)間分別為0.500 s、0.720 s、0.997 s、1.107 s、1.110 s、1.350 s、1.471 s。本文算法相對(duì)于其他兩種算法平均提升了18.7%、39.1%。

圖9 查詢對(duì)象的數(shù)量變化對(duì)運(yùn)行時(shí)間的影響Fig.9 Impact of the number of query objects on running time

進(jìn)一步分析不同數(shù)量的查詢對(duì)象對(duì)I/O 代價(jià)的影響。如圖10 所示，在查詢對(duì)象的數(shù)量逐漸增多的情況下，MDGNN_Query 算法的I/O 代價(jià)分別為102、117、157、221；MDGNN_Basic1 算法執(zhí)行的I/O 代價(jià)分別為135、149、216、284；MDGNN_Basic2 算法執(zhí)行的I/O 代價(jià)分別為180、223、319、379。本文算法相對(duì)于其他兩種算法平均分別提升了11.1%、36.7%。

圖10 查詢對(duì)象的數(shù)量變化對(duì)I/O 代價(jià)的影響Fig.10 Impact of the number of query objects on I/O cost

最后對(duì)算法的準(zhǔn)確率進(jìn)行測(cè)試，隨機(jī)選取真實(shí)對(duì)象集中的節(jié)點(diǎn)，并隨機(jī)選取真實(shí)對(duì)象集中的節(jié)點(diǎn)兩兩連接組成數(shù)據(jù)線段集，構(gòu)成數(shù)據(jù)對(duì)象集與查詢對(duì)象集。在實(shí)驗(yàn)中其他條件均一致時(shí)，分別測(cè)試查詢次數(shù)為20、40、60、80、100、120、140 時(shí)三組算法的準(zhǔn)確率，最終結(jié)果取其平均值。如圖11，在查詢次數(shù)逐漸增多時(shí)，本文算法相對(duì)于其他兩種算法在準(zhǔn)確率上平均分別提升了7.9%、13.5%。

圖11 查詢次數(shù)對(duì)算法準(zhǔn)確率的影響Fig.11 Impact of the number of query objects on accuracy of algorithm

由實(shí)驗(yàn)分析可得，在處理混合數(shù)據(jù)組最近鄰查詢問題時(shí)，本文提出的MDGNN_Query 算法在運(yùn)行時(shí)間、I/O 代價(jià)、算法準(zhǔn)確率等方面均優(yōu)于其他兩組對(duì)比算法，且具有更高的查詢效率和準(zhǔn)確度。因?yàn)镸DGNN_Basic1 算法需要對(duì)查詢點(diǎn)集和查詢線段集分別構(gòu)建基于點(diǎn)的Voronoi 圖和基于線段的Voronoi圖，將點(diǎn)和線段分開處理，會(huì)造成搜索區(qū)域相重合，會(huì)對(duì)查詢時(shí)間和I/O 代價(jià)造成影響。MDGNN_Basic2算法需要計(jì)算每一個(gè)查詢對(duì)象的最近鄰，再對(duì)每次查詢的結(jié)果進(jìn)行處理，搜索區(qū)域相重合的現(xiàn)象更為嚴(yán)重，降低了算法性能，增加了運(yùn)行時(shí)間以及I/O 代價(jià)。而本文所提MDGNN_Query 算法直接針對(duì)混合數(shù)據(jù)集進(jìn)行剪枝，精煉且不需要對(duì)結(jié)果集進(jìn)行額外的處理，直接得到組最近鄰查詢結(jié)果，因此MDGNN_Query 算法的運(yùn)行時(shí)間最短，I/O 代價(jià)相對(duì)最低，查詢效率相對(duì)最高。在查詢的準(zhǔn)確率方面，其他兩種對(duì)比算法是對(duì)點(diǎn)和線段分別進(jìn)行查詢，然后對(duì)結(jié)果集進(jìn)行組合處理得到查詢結(jié)果，查詢效率低并且查詢結(jié)果往往會(huì)有一定的誤差；而本文算法是在混合數(shù)據(jù)集的基礎(chǔ)上進(jìn)行的組最近鄰查詢，準(zhǔn)確率較高，并且在查詢過程中能夠更快地達(dá)到較高的準(zhǔn)確率。

5 結(jié)束語

本文研究了混合數(shù)據(jù)的組最近鄰查詢問題，提出了點(diǎn)和線段混合的組最近鄰查詢的概念，將查詢過程分為剪枝和精煉兩個(gè)過程。剪枝階段根據(jù)查詢對(duì)象的數(shù)量和分布情況以及Voronoi圖的性質(zhì)進(jìn)行篩選得到滿足查詢條件的候選結(jié)果集，然后在精煉階段再次對(duì)候選結(jié)果進(jìn)行篩選，得到最終結(jié)果。由于本文直接對(duì)混合數(shù)據(jù)進(jìn)行處理，在查詢效率及準(zhǔn)確度等方面都更優(yōu)。理論和實(shí)驗(yàn)研究表明，所提算法能夠較好地解決點(diǎn)和線段混合數(shù)據(jù)的組最近鄰問題。盡管本文在多方面的性能較優(yōu)，但是本文算法也存在不足，因?yàn)楸疚南葮?gòu)建查詢凸包，通過構(gòu)建查詢對(duì)象的影響區(qū)域來對(duì)數(shù)據(jù)對(duì)象進(jìn)行剪枝，在查詢對(duì)象距離過于分散時(shí)，查詢對(duì)象的影響區(qū)域范圍過大，剪枝效果會(huì)受到較大程度的影響。未來的研究重點(diǎn)是主要集中處理不確定數(shù)據(jù)的混合組最近鄰查詢問題并對(duì)本文算法進(jìn)行改進(jìn)。