田 春,鮑金玲,張志威,劉 剛

(1.吉林化工學(xué)院信息與控制工程學(xué)院,吉林省 吉林市 132000;2.白城師范學(xué)院計算機科學(xué)學(xué)院,吉林 白城 137000)

0 引言

隨著無線通信技術(shù)的快速發(fā)展和移動通信設(shè)備的不斷普及,基于位置服務(wù)的應(yīng)用越來越廣泛,查詢要求也越來越復(fù)雜,比如Top-k空間關(guān)鍵字偏好查詢[1-5]和Top-k空間偏好查詢[6-13]。

Top-k空間關(guān)鍵字偏好查詢是指在查詢中考慮查詢對象周圍的空間屬性和文本屬性是否滿足用戶的查詢需求,返回前k個最優(yōu)的空間對象。例如,一位游客計劃在北京預(yù)訂一個周圍有飯店的賓館,希望獲得周圍1公里內(nèi)飯店評價等級最高的前k個賓館排名列表,并且這些飯店都能提供“西餐和停車場”,然后從中選擇自己滿意的賓館。而Top-k空間偏好查詢是根據(jù)空間對象周圍的特征對空間對象進行等級評價,返回k個最佳對象的排序列表。例如,一位游客計劃在北京預(yù)訂一個周圍有飯店和超市的賓館,希望獲得周圍1公里內(nèi)飯店和超市評價等級最高的前k個賓館排名列表,然后從中選擇自己滿意的賓館。在上述Top-k空間關(guān)鍵字偏好查詢和Top-k空間偏好查詢中,賓館是游客感興趣的設(shè)施,超市和飯店是游客關(guān)注的周邊設(shè)施,“周圍1公里”是游客提出的空間約束條件,“西餐和停車場”是飯店的文本約束條件。兩者最主要的區(qū)別在于Top-k空間偏好查詢不考慮空間對象中的文本屬性。

在實際生活中,Top-k空間偏好查詢的應(yīng)用很廣泛,可以應(yīng)用在地理信息系統(tǒng)、城市建設(shè)規(guī)劃、資源調(diào)度與分配、旅游規(guī)劃等領(lǐng)域。近年來,國內(nèi)外很多大學(xué)和研究機構(gòu)對Top-k空間偏好查詢展開了深入研究,并取得了許多有價值的研究成果。本文對歐式空間和路網(wǎng)環(huán)境下的Top-k空間偏好查詢方法進行研究,分析和總結(jié)現(xiàn)有方法的優(yōu)點和不足。

1 問題描述

定義1 數(shù)據(jù)對象指用戶感興趣的設(shè)施類型,例如上述查詢實例中的“賓館”。數(shù)據(jù)對象集用D表示,p表示數(shù)據(jù)對象集D中的一個對象點。

定義 2 特征對象指用戶關(guān)注的周邊設(shè)施類型,例如上述查詢實例中的“超市和飯店”。特征對象集用F表示,f表示特征對象集中的一個對象。

定義3 特征對象分數(shù)指用戶對特征對象的評級,用符號w(f)表示。每個特征對象的分數(shù)被歸一化為[0,1]范圍內(nèi)的數(shù)值。

定義5 將路網(wǎng)結(jié)構(gòu)表示為一個圖結(jié)構(gòu)G=(V,E,W),其中V表示路網(wǎng)路段中的交叉節(jié)點集合,E表示路網(wǎng)中路段集合,每條邊分配一個有向或無向的方向,W表示路段對應(yīng)的權(quán)重,這里表示該路段的長度。

定義6 路網(wǎng)距離指從查詢點到查詢對象的最短路徑長度,用l(ni,nj)表示,其中ni表示起點,nj表示終點。

定義7 Top-k空間偏好查詢是指給定一個數(shù)據(jù)對象集D{p1,…,pn}和m個特征對象集F1,…,Fm,查詢Q(D,F,θ,k)就是根據(jù)數(shù)據(jù)對象周圍滿足約束條件的特征對象得分來計算數(shù)據(jù)對象點的得分,返回得分最高的k個數(shù)據(jù)對象點,具體表示為:

(1)

當(dāng)θ表示范圍約束時,Top-k空間偏好范圍約束查詢是指在數(shù)據(jù)對象集D中,查找r范圍內(nèi)各類特征對象集Fi分數(shù)和最高的前k個數(shù)據(jù)對象點。對于每一類特征對象集,數(shù)據(jù)對象p的第i個分量范圍得分是指r范圍內(nèi)特征對象f∈Fi的最高得分,具體表示為:

(2)

當(dāng)θ表示最近鄰約束時,Top-k空間偏好最近鄰約束查詢是指在數(shù)據(jù)對象集D中,查找最近的各類特征對象集Fi分數(shù)和最高的前k個數(shù)據(jù)對象點。對于每一類特征對象集,數(shù)據(jù)對象p的第i個分量最近鄰得分是指最近特征對象f∈Fi的最高得分,具體表示為:

(3)

當(dāng)θ表示為影響力約束時,Top-k空間偏好影響力約束查詢是指在數(shù)據(jù)對象集D中,查找各類特征對象集Fi中對象的分數(shù)與權(quán)重的乘積,以及其和最大的前k個數(shù)據(jù)對象點。r是用戶指定的空間范圍,數(shù)據(jù)對象集D與特征對象f之間的距離越近,特征對象f的影響力分數(shù)越高。數(shù)據(jù)對象p的第i個分量影響力約束得分具體表示為:

(4)

在歐式空間中,r指的是歐式距離,d(p,f)表示數(shù)據(jù)對象p與特征對象f的直線距離;路網(wǎng)環(huán)境中r指的是路網(wǎng)距離,l(p,f)表示數(shù)據(jù)對象點p與特征對象f的路網(wǎng)距離。

對象點歐式空間分布如圖1所示,橫軸與縱軸刻度值表示距離。從圖1可讀取對象點的坐標,例如,p1的坐標為(0.5,4)。假設(shè)用戶查詢?yōu)镼1(D,(F1,F2),θ,2),其中k=2,D={p1,p2,p3}。a、b表示兩類不同的特征對象。F1={〈a1,0.7〉〈a2,0.8〉〈a3,0.5〉〈a4,0.3〉〈a5,0.7〉},F2={〈b1,0.8〉〈b2,0.6〉〈b3,0.6〉〈b4,0.4〉}。數(shù)據(jù)對象集D={p1,p2,p3}代表“賓館”,用實心三角形表示;特征對象集F1={a1,a2,a3,a4,a5}代表“飯店”,用實心矩形表示;特征對象集F2={b1,b2,b3,b4}代表“超市”,用空心矩形表示。特征對象后邊的數(shù)字表示特征對象的等級分數(shù),分數(shù)一般來源于用戶的評級,歸一化為[0,1]范圍內(nèi)的數(shù)值。

圖1 歐式空間查詢示例圖

表1 數(shù)據(jù)對象p1,p2,p3得分

將圖1按照路網(wǎng)中的狀態(tài)抽象為圖結(jié)構(gòu)G=(V,E,W),如圖2所示,V表示路網(wǎng)中的交叉節(jié)點集合v1,…,v9;E表示路網(wǎng)中的相連節(jié)點的邊集合;W表示邊的權(quán)重,在此表示節(jié)點之間的路網(wǎng)距離,表示邊上的數(shù)字,例如l(v1,p1)=0.5,l(p1,a1)=1數(shù)據(jù)對象集D={p1,p2,p3}代表“賓館”,用實心三角形表示;a和b表示兩類不同的特征對象,特征對象集F1={a1,a2,a3,a4,a5}代表“飯店”,用實心矩形表示;特征對象集F2={b1,b2,b3,b4}代表“超市”,用空心矩形表示,括號中的數(shù)值表示特征對象的分數(shù)。

圖2 無向路網(wǎng)環(huán)境查詢實例圖

根據(jù)圖2,在路網(wǎng)環(huán)境中,用戶查詢?yōu)镼2(D,(F1,F2),θ,2),分別處理范圍約束、最近鄰約束和影響力約束下的Top-k空間偏好查詢。這與歐式空間查詢要求相近,不同之處是所有距離均為路網(wǎng)距離。根據(jù)三種約束查詢的要求,可得出數(shù)據(jù)對象p1,p2,p3的得分表,如表2所示,其中數(shù)據(jù)對象p1,p2為查詢結(jié)果。

表2 數(shù)據(jù)對象p1,p2,p3得分表

2 歐式空間中的Top-k空間偏好查詢方法

根據(jù)空間索引結(jié)構(gòu),本文將查詢方法劃分為兩類:基于R-tree索引結(jié)構(gòu)的查詢方法[6-8]和基于網(wǎng)格索引結(jié)構(gòu)的查詢方法[9-10]。

2.1 基于R-tree索引結(jié)構(gòu)的Top-k空間偏好查詢方法

R-tree是Guttman在1984年提出的一種動態(tài)空間索引結(jié)構(gòu),用來訪問二維或者更高維區(qū)域?qū)ο蠼M成的空間數(shù)據(jù)?；赗-tree索引,YIU等[6]提出了SP算法、GP算法、BB算法和FJ算法,解決范圍與最近鄰約束下的Top-k空間偏好查詢。在上述工作基礎(chǔ)上,YIU等[7]將算法擴展到影響力約束下的Top-k空間偏好查詢,并對BB算法做出改進,提出了BB*算法。ROCHA等[8]基于R-tree索引提出了SFA算法,解決范圍約束、最近鄰約束和影響力約束下的Top-k空間偏好查詢。

2.1.1 SP算法

SP算法采用R-tree索引數(shù)據(jù)對象點和MAX aR-tree索引特征對象點。以查詢Q1(D,(F1,F2),θ,2)為例,首先,利用R-tree對圖1中數(shù)據(jù)對象點構(gòu)建索引,如圖3所示,假定每個節(jié)點限定子節(jié)點個數(shù)為3,位置上相鄰的結(jié)點盡量在樹中聚集為一個父結(jié)點,葉子節(jié)點e2中存儲包含數(shù)據(jù)對象p1,p2最小外接矩形的坐標和數(shù)據(jù)對象p1,p2的唯一標識符,e3中存儲數(shù)據(jù)對象p3的最小外接矩形的坐標和數(shù)據(jù)對象p3的唯一標識符,根節(jié)點e1中存儲能夠覆蓋子節(jié)點e2,e3區(qū)域的最小外接矩形和指向子節(jié)點e2,e3的指針。然后,利用MAX aR-tree索引特征對象點,如圖4所示,葉子節(jié)點中存儲包含特征對象最小外接矩形的坐標以及特征對象的唯一標識符,非葉節(jié)點中存儲覆蓋所有子節(jié)點區(qū)域最小外接矩形坐標、子結(jié)點中特征對象分數(shù)的最大值以及指向子節(jié)點的指針。

(a)空間區(qū)域劃分 (b)R-tree示例圖

(c)F2中對象點的區(qū)域劃分 (d)R-tree示例圖

SP算法的基本思想是通過計算每個數(shù)據(jù)對象點的得分來檢索查詢結(jié)果。為了提高算法效率,通過數(shù)據(jù)對象的得分上界進行剪枝。在SP算法中使用兩個全局變量wk和γ,其中wk存儲得分最高的k個數(shù)據(jù)對象點的信息,γ是wk中的最低分,τ+(p)是數(shù)據(jù)對象得分的上界。在遍歷一個特征對象樹時,得到當(dāng)前已知數(shù)據(jù)對象的分量得分τc(p),其余沒有遍歷的特征對象樹,對應(yīng)的數(shù)據(jù)對象的得分上界設(shè)置為1。此時可以得出數(shù)據(jù)對象得分的上界τ+(p)為已知的分量分數(shù)之和。當(dāng)一個數(shù)據(jù)對象上限分數(shù)不大于γ時,該數(shù)據(jù)對象被剪枝;而數(shù)據(jù)對象點的實際分數(shù)大于γ時,更新wk和γ。

由SP算法的基本思想可知,當(dāng)數(shù)據(jù)對象規(guī)模增大時,SP算法效率會明顯降低,而k增大時,SP算法的查詢效率基本不受影響。

2.1.2 GP算法

為了提高Top-k空間偏好查詢的效率,文獻[6-7]在SP算法的基礎(chǔ)上提出了GP算法。GP算法與SP算法不同的是,當(dāng)訪問數(shù)據(jù)對象樹的一個葉子節(jié)點時,將葉子節(jié)點中所有對象節(jié)點存儲在一個集合中,然后在遍歷特征對象樹的過程中同時計算它們的分數(shù)。GP算法的查詢效率略高于SP算法,k增大時,GP算法的查詢基本不受影響。

2.1.3 BB算法

BB算法是在GP算法剪枝策略的基礎(chǔ)上,利用數(shù)據(jù)對象樹中所有非葉項的上界T+(e)對數(shù)據(jù)對象點進行剪枝。在滿足空間約束的特征對象樹中,最低級別的非葉項e存儲子樹中特征分數(shù)的最大值,由此可以計算出目前已知的數(shù)據(jù)對象樹中非葉項的分量分數(shù)Tc(e),而未知的數(shù)據(jù)對象樹中非葉項的上界設(shè)置為1。

此時上界T+(e)為已知的分量分數(shù)之和。如果數(shù)據(jù)對象樹中非葉項的上界T+(e)<γ,對該非葉項的子樹中包含的數(shù)據(jù)對象點進行剪枝。當(dāng)數(shù)據(jù)對象樹中的非葉項的上界T+(e)≥γ時,展開非葉項的子樹,求所包含的數(shù)據(jù)對象點的得分。

(a)F1中對象點的空間區(qū)域劃分 (b)R-tree示例圖

運用BB算法計算數(shù)據(jù)對象樹中非葉項的上界,對無效數(shù)據(jù)對象點進行剪枝。當(dāng)數(shù)據(jù)對象和特征對象規(guī)模增大時,BB算法效率明顯優(yōu)于GP算法和SP算法,而k增大時,BB算法的查詢效率基本不受影響。

2.1.4 BB*算法

BB算法中,當(dāng)數(shù)據(jù)對象和數(shù)據(jù)對象樹非葉項的分量分數(shù)為未知的情況時,數(shù)據(jù)對象得分的上界τ+(p) 和數(shù)據(jù)對象樹中非葉項的上界T+(e)都設(shè)置為分量得分的最大取值1,兩個上界均不夠緊致,所以剪枝效果不理想。為了增強以上兩個上界的緊致性,加強剪枝效果,BB*算法[7]利用一個大頂堆按照特征對象樹中的特征分數(shù)降序遍歷每類特征樹中的數(shù)據(jù)項,通過從堆中彈出來的特征對象分數(shù)來計算數(shù)據(jù)對象的得分。數(shù)據(jù)對象的分量得分τc(p)為當(dāng)前訪問的特征對象樹對應(yīng)的大頂堆彈出的得分,該數(shù)據(jù)對象其余分量的得分上界不會大于從對應(yīng)的特征對象大頂堆中最后彈出的分數(shù),這使得上界τc(p)更加緊致。計算數(shù)據(jù)對象樹非葉項的上界T+(e)時,逐一訪問特征對象樹中最低級別的非葉項e,獲取每個非葉項子樹中特征分數(shù)的最大值,得到更加緊致數(shù)據(jù)對象樹非葉項的上界T+(e)。當(dāng)數(shù)據(jù)對象規(guī)模和特征對象規(guī)模增大時,BB*算法的效率明顯優(yōu)于前面的三個算法,而k增大時,BB*算法的查詢效率同樣不受影響。

2.1.5 FJ算法

FJ算法[6-7]的主要思想是對特征對象樹進行多路空間連接,逐一檢索數(shù)據(jù)對象點附近滿足空間約束的特征對象組合,并將特征對象組合按照總分數(shù)進行降序排序,然后按照排序順序檢索數(shù)據(jù)對象點。FJ算法結(jié)合了特征樹的非葉項,對那些總分數(shù)小于已查詢到的第k個數(shù)據(jù)對象點的分數(shù)的特征對象組合,以及不能滿足空間約束的特征對象組合進行剪枝。如果得分最高的特征對象組合的所有項都是葉子節(jié)點,則檢索其空間鄰域中的數(shù)據(jù)對象點,否則展開得分最高的非葉項。FJ算法受特征對象種類的數(shù)目影響最大,當(dāng)特征對象的類別較少時,FJ算法的性能要優(yōu)于SP、GP、BB和BB*算法,在特征對象類別為2的情況下,效率最佳;而特征對象種類增多時,需要檢索的特征組合數(shù)目呈指數(shù)級增長,查詢效率明顯降低。當(dāng)k增大時,FJ算法的剪枝能力減弱,查詢效率明顯降低。

2.1.6 SFA算法

SFA算法[8]將數(shù)據(jù)對象和特征對象映射到距離-分數(shù)空間,在距離-分數(shù)空間中橫坐標表示距離,縱坐標表示等級分數(shù)。算法根據(jù)距離-分數(shù)支配關(guān)系過濾無效的映射對,得到不同約束下Top-k空間偏好查詢所需要的Skyline集,然后利用R-tree索引Skyline集,聚合從每個R-tree中檢索到的數(shù)據(jù)對象的分量分數(shù),最終返回前k個Top-k空間偏好查詢的結(jié)果。

查詢實例1,Q1(D,(F1,F2),θ,2),SFA算法根據(jù)圖1中的對象點,利用R-tree對Skyline集建立索引,如圖5所示。數(shù)據(jù)對象p1到特征對象集F1={a1,a2,a3,a4,a5}的距離分別為d(p1,a1)=1,d(p1,a2)=3.20,d(p1,a3)=4.123,d(p1,a4)=3.35,特征對象集F1中對象的分數(shù)分別為w(a1)=0.7,w(a2)=0.8,w(a3)=0.5,w(a4)=0.3,w(a5)=0.7,所以數(shù)據(jù)對象p1與特征對象集F1映射到距離-分數(shù)空間的坐標分別為(p1,a1)=(1,0.7),(p1,a2)=(3.2,0.7),(p1,a3)=(4.123,0.5),(p1,a4)=(3.35,0.3),(p1,a5)=(4.47,0.7)。同理可得到其余的數(shù)據(jù)對象和特征對象對的映射坐標。根據(jù)支配關(guān)系得到Skyline集,利用R-tree索引Skyline集,Skyline集為S1{(p1,a1),(p2,a2),(p1,a2),(p3,a2)(p3,a3),(p3,a5)(p2,b3),},S2{(p1,b1),(p2,b1),(p3,b1), (p3,b2),(p3,b4)}。

(a)根據(jù)S1建立的R-tree (b)根據(jù)S2建立的R-tree

SFA算法可以擴展到大規(guī)模數(shù)據(jù)集,算法的查詢效率比較穩(wěn)定。當(dāng)數(shù)據(jù)對象和特征對象規(guī)模增大時,SFA算法效率明顯優(yōu)于上述其他算法,k增大時SFA算法的查詢效率基本不受影響。

2.2 基于網(wǎng)格索引結(jié)構(gòu)的Top-k空間偏好查詢方法

網(wǎng)格索引通過對地理空間進行網(wǎng)格劃分,將查詢區(qū)域劃分成大小相等或不等的網(wǎng)格,建立一個倒排文件——柵格索引,每一個網(wǎng)格在柵格索引中有一個索引記錄,在這個記錄中標記所有位于或穿過該網(wǎng)格的對象。孫煥良[9]和劉俊嶺[10]采用網(wǎng)格索引結(jié)構(gòu)解決Top-k空間偏好查詢。

文獻[9-10]利用網(wǎng)格索引二維空間的數(shù)據(jù),結(jié)合概念劃分的剪枝策略,分別針對范圍約束和最近鄰約束下的Top-k空間偏好查詢提出了TopRNG-G算法和TopNN-G算法。根據(jù)圖1中的對象點創(chuàng)建網(wǎng)格索引,如圖6所示,每個網(wǎng)格對應(yīng)著一塊存儲空間,存儲對象點的信息。

(a)歐式空間查詢示例圖 (b)網(wǎng)格劃分

TopRNG-G算法主要結(jié)合概念劃分的思想,利用網(wǎng)格到查詢對象點的距離進行剪枝,當(dāng)該距離大于范圍距離r時,對網(wǎng)格內(nèi)所有點進行剪枝。TopNN-G算法定義一個距離的全局變量,存儲查詢點到已找到的最近鄰特征對象的最遠距離,利用概念劃分思想將查詢點周圍的單元格合并成概念矩形,然后根據(jù)查詢點到概念矩形的最小距離進行剪枝,當(dāng)該距離大于當(dāng)前最佳距離時,則對網(wǎng)格內(nèi)的所有點進行剪枝。

當(dāng)特征對象規(guī)模增大和特征對象種類增多時,TopNN-G算法和TopRNG-G算法查詢效率優(yōu)于FJ算法,當(dāng)k增大時,利用網(wǎng)格索引的算法與利用R-tree索引的算法基本都不受影響。

2.3 歐式空間Top-k空間偏好查詢方法總結(jié)

基于R-tree索引的SP、GP、BB、BB*、FJ和SFA六種算法均支持范圍約束、最近鄰約束和影響力約束的Top-k空間偏好查詢,基于網(wǎng)格索引的TopNN-G算法和TopRNG-G算法分別支持最近鄰約束和范圍約束下的Top-k空間偏好查詢。綜合現(xiàn)有研究,對以上八種算法查詢性能進行比較與分析,SFA算法的查詢效率明顯優(yōu)于其他算法。具體情況如表3所示,分別考慮數(shù)據(jù)對象規(guī)模、特征對象規(guī)模、查詢的特征對象種類和k的變化情況對算法性能的影響,可知,當(dāng)數(shù)據(jù)對象規(guī)模增大時,FJ算法查詢效率所受影響最小,GP算法所受影響最大,查詢效率明顯降低;當(dāng)特征對象規(guī)模增大時,SFA算法的查詢效率所受影響最小,GP算法的查詢效率所受影響最大;當(dāng)查詢的特征對象種類增多時,FJ算法的查詢效率所受影響最大,SFA算法的查詢效率所受影響最小;當(dāng)k增大時,FJ算法的查詢效率所受影響最大,SFA算法的查詢效率所受影響最小,而BB*、TopNN-G和TopRNG-G算法對于上述參數(shù)變化,查詢效率所受影響較小。

表3 算法查詢效率分析表

3 路網(wǎng)環(huán)境下Top-k空間偏好查詢方法

路網(wǎng)環(huán)境下Top-k空間偏好查詢更貼近日常生活,目前也取得一定的研究進展。根據(jù)路網(wǎng)特征,本文將查詢方法劃分為無向路網(wǎng)和有向路網(wǎng)兩類,即無向路網(wǎng)環(huán)境下Top-k空間偏好查詢方法[11]和有向路網(wǎng)環(huán)境下Top-k空間偏好查詢方法[12-13]。

PAPADIAS等[14]提出了INE算法和RNE算法,實現(xiàn)路網(wǎng)環(huán)境下的k近鄰查詢。通過對INE算法的改進,可以解決有向與無向路網(wǎng)環(huán)境下最近鄰和影響力約束的Top-k空間偏好查詢。通過對RNE算法進行改進,可以解決有向與無向路網(wǎng)環(huán)境的范圍約束下的Top-k空間偏好查詢。

3.1 無向路網(wǎng)環(huán)境Top-k空間偏好查詢方法

CHO等[11]針對無向路網(wǎng)環(huán)境下Top-k空間偏好查詢提出了ALPS算法。該算法預(yù)計算路網(wǎng)中所有交叉節(jié)點的最短路徑表,然后將任意兩個交叉節(jié)點之間包含的數(shù)據(jù)對象提前劃分成數(shù)據(jù)段,計算每個數(shù)據(jù)段到每個特征對象點最大和最小距離,再將數(shù)據(jù)段與每個特征對象點映射到距離-分數(shù)空間,其中橫坐標表示距離,縱坐標表示等級分數(shù),根據(jù)Skyline方法確定數(shù)據(jù)段和特征對象組對之間的支配關(guān)系,過濾掉被支配的數(shù)據(jù)段或者數(shù)據(jù)對象點,然后使用一個大頂堆按照數(shù)據(jù)對象的分量分數(shù)降序遍歷每個Skyline集,最后基于NRA算法[15]思想將各個堆中彈出的數(shù)據(jù)對象的分量分數(shù)相加,返回得分最高的數(shù)據(jù)對象。

查詢實例2為Q2(D,(F1,F2),θ,2),ALPS算法根據(jù)圖2中的對象點,利用R-tree對Skyline集建立索引(圖7),構(gòu)造圖2中對象點的Skyline集。數(shù)據(jù)對象p1到特征對象集F1的路網(wǎng)距離分別為l(p1,a1)=1,l(p1,a2)=4.5,l(p1,a3)=5,l(p1,a4)=4.5,l(p1,a5)=6,特征對象集F1中對象的分數(shù)分別為w(a1)=0.7,w(a2)=0.8,w(a3)=0.5,w(a4)=0.3,w(a5)=0.7,所以數(shù)據(jù)對象p1與特征對象集F1映射到距離-分數(shù)空間的坐標為p1?a1=([1,1],0.7),p1?a2=([4.5,4.5],0.8),(p1?a3)=([5,5],0.5),(p1?a4)=([4.5,4.5],0.3),(p1?a5)=([1,1],0.7)。同理可得,其余數(shù)據(jù)對象和特征對象對映射到距離-分數(shù)的坐標。根據(jù)數(shù)據(jù)段和特征對象對在距離-分數(shù)空間的支配關(guān)系得到Skyline集:S1{(p1?a1),(p1?a2),(p2?a2),(p3?a2),(p3?a3),(p3?a5)},S2{(p1?b1),(p2?b1),(p2?b3)(p3?b1),(p3?b2),(p3?b4)}。

(a)根據(jù)S1建立的R-tree (b)根據(jù)S2建立的R-tree

3.2 有向路網(wǎng)Top-k空間偏好查詢方法

在無向路網(wǎng)環(huán)境抽象后的圖2中,設(shè)置路段方向后,得到有向路網(wǎng)的抽象圖,結(jié)構(gòu)如圖8所示。ATTIOUE等[12-13]將Top-k空間偏好查詢擴展到有向路網(wǎng),并提出了TOPS算法。TOPS算法的基本思想是預(yù)處理節(jié)點之間的距離,定義了靜態(tài)維度、靜態(tài)等式、靜態(tài)支配和完全支配,并根據(jù)上述特征過濾特征對象。每個特征對象都與一個軸節(jié)點相關(guān)聯(lián),因此將共享同一軸節(jié)點的特征對象組合在一起。計算數(shù)據(jù)對象到特征對象組最大距離和最小距離,將數(shù)據(jù)對象和特征對象組對映射到距離-分數(shù)的二維空間,利用Skyline方法過濾掉被支配的數(shù)據(jù)對象和特征對象,利用R-tree索引過濾后的Skyline集,使用一個大頂堆按照數(shù)據(jù)對象的分量分數(shù)降序遍歷每個Skyline集,然后基于NRA算法[15]思想將各個堆中彈出的數(shù)據(jù)對象的分量分數(shù)相加,返回得分最高的數(shù)據(jù)對象。

圖8 有向路網(wǎng)環(huán)境查詢實例圖

查詢實例3為Q2(D,(F1,F2),θ,2)。根據(jù)圖8中的對象點,利用R-tree對Skyline集建立索引,如圖9所示。根據(jù)定義的靜態(tài)維度、靜態(tài)等式、靜態(tài)支配和完全支配,得到每個數(shù)據(jù)對象有用的特征對象:{(p1?a1),(p2?a1),(p3?a1)(p3?a2)(p3?a3)(p3?a5)}{(p1?b1)(p2?b1)(p2?b2)(p2?b3)},將數(shù)據(jù)對象和特征對象組映射到距離-分數(shù)空間。根據(jù)數(shù)據(jù)對象和特征對象組對之間的支配關(guān)系得到Skyline集:S1{(p1?a1),(p1?a2),(p2?a1)(p2?a2),(p3?a3),(p3?a5)},S2{(p1?b1),(p2?b1),(p2?b3)(p3?b1)(p3?b2),(p3?b4)}。

(a)根據(jù)S1建立的R-tree (b)根據(jù)S2建立的R-tree

3.3 路網(wǎng)環(huán)境下Top-k空間偏好查詢方法總結(jié)

綜合現(xiàn)有研究,對無向路網(wǎng)環(huán)境和有向路網(wǎng)環(huán)境下的Top-k空間偏好查詢算法性能進行比較與分析,無向路網(wǎng)環(huán)境下,ALPS算法的查詢效率明顯優(yōu)于改進的INE算法和改進的RNE算法;有向路網(wǎng)環(huán)境下,TOPS算法的查詢效率明顯優(yōu)于改進的INE算法和改進的RNE算法。

在無向路網(wǎng)環(huán)境下,分別考慮數(shù)據(jù)對象規(guī)模、特征對象規(guī)模、查詢的特征對象種類和k的變化情況對算法性能的影響,具體情況如表4所示,當(dāng)數(shù)據(jù)對象規(guī)模和特征對象規(guī)模增大時,ALPS算法的查詢效率所受影響較小,改進的INE算法和改進的RNE算法的查詢效率所受影響較大,查詢效率明顯降低;當(dāng)特征對象種類增多時,改進的INE算法和改進的RNE算法查詢效率所受影響較小,ALPS算法的查詢效率所受影響較大;當(dāng)k值增大時,改進的INE算法、改進的RNE算法和ALPS算法查詢效率所受影響較小。

表4 無向路網(wǎng)環(huán)境下R-tree索引各算法查詢效率分析表

在有向路網(wǎng)環(huán)境下,分別考慮數(shù)據(jù)對象規(guī)模、特征對象規(guī)模、查詢的特征對象種類和k的變化情況對算法性能的影響,具體情況如表5所示,數(shù)據(jù)對象規(guī)模和特征對象規(guī)模增大時,TOPS算法的查詢效率所受影響較小,改進的INE算法和改進的RNE算法的查詢效率所受影響較大,查詢效率明顯降低;當(dāng)查詢特征對象種類增多時,TOPS算法的查詢效率所受影響較小,改進的INE算法和改進的RNE算法查詢效率所受影響較大,查詢效率明顯降低;當(dāng)k值增大時,改進的INE算法和改進的RNE算法查詢效率所受影響較小,TOPS算法的查詢效率所受影響較大。

表5 有向路網(wǎng)環(huán)境下R-tree索引各算法查詢效率分析表

4 結(jié)語

綜上所述,本文對歐式空間和路網(wǎng)環(huán)境Top-k空間偏好查詢算法進行了分析和總結(jié)。在歐氏空間中,SFA算法的查詢效率明顯優(yōu)于其他算法。在無向路網(wǎng)環(huán)境中, ALPS的查詢效率明顯優(yōu)于改進的INE算法和改進的RNE算法。在有向路網(wǎng)環(huán)境中,TOPS的查詢效率明顯優(yōu)于改進的INE算法和改進的RNE算法。