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

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

0 引言

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

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

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

1 問題描述

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

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

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

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

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

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

(1)

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

(2)

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

(3)

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

(4)

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

對象點歐式空間分布如圖1所示,橫軸與縱軸刻度值表示距離。從圖1可讀取對象點的坐標,例如,p1的坐標為(0.5,4)。假設用戶查詢?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〉}。數據對象集D={p1,p2,p3}代表“賓館”,用實心三角形表示;特征對象集F1={a1,a2,a3,a4,a5}代表“飯店”,用實心矩形表示;特征對象集F2={b1,b2,b3,b4}代表“超市”,用空心矩形表示。特征對象后邊的數字表示特征對象的等級分數,分數一般來源于用戶的評級,歸一化為[0,1]范圍內的數值。

圖1 歐式空間查詢示例圖

表1 數據對象p1,p2,p3得分

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

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

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

表2 數據對象p1,p2,p3得分表

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

根據空間索引結構,本文將查詢方法劃分為兩類:基于R-tree索引結構的查詢方法[6-8]和基于網格索引結構的查詢方法[9-10]。

2.1 基于R-tree索引結構的Top-k空間偏好查詢方法

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

2.1.1 SP算法

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

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

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

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

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

2.1.2 GP算法

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

2.1.3 BB算法

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

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

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

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

2.1.4 BB*算法

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

2.1.5 FJ算法

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

2.1.6 SFA算法

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

查詢實例1,Q1(D,(F1,F2),θ,2),SFA算法根據圖1中的對象點,利用R-tree對Skyline集建立索引,如圖5所示。數據對象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中對象的分數分別為w(a1)=0.7,w(a2)=0.8,w(a3)=0.5,w(a4)=0.3,w(a5)=0.7,所以數據對象p1與特征對象集F1映射到距離-分數空間的坐標分別為(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)。同理可得到其余的數據對象和特征對象對的映射坐標。根據支配關系得到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)根據S1建立的R-tree (b)根據S2建立的R-tree

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

2.2 基于網格索引結構的Top-k空間偏好查詢方法

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

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

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

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

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

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

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

表3 算法查詢效率分析表

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

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

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

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

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

查詢實例2為Q2(D,(F1,F2),θ,2),ALPS算法根據圖2中的對象點,利用R-tree對Skyline集建立索引(圖7),構造圖2中對象點的Skyline集。數據對象p1到特征對象集F1的路網距離分別為l(p1,a1)=1,l(p1,a2)=4.5,l(p1,a3)=5,l(p1,a4)=4.5,l(p1,a5)=6,特征對象集F1中對象的分數分別為w(a1)=0.7,w(a2)=0.8,w(a3)=0.5,w(a4)=0.3,w(a5)=0.7,所以數據對象p1與特征對象集F1映射到距離-分數空間的坐標為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)。同理可得,其余數據對象和特征對象對映射到距離-分數的坐標。根據數據段和特征對象對在距離-分數空間的支配關系得到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)根據S1建立的R-tree (b)根據S2建立的R-tree

3.2 有向路網Top-k空間偏好查詢方法

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

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

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

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

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

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

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

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

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

4 結語

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