Top-k空間偏好查詢(xún)方法研究

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

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

0 引言

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

Top-k空間關(guān)鍵字偏好查詢(xún)是指在查詢(xún)中考慮查詢(xún)對(duì)象周?chē)目臻g屬性和文本屬性是否滿(mǎn)足用戶(hù)的查詢(xún)需求,返回前k個(gè)最優(yōu)的空間對(duì)象。例如,一位游客計(jì)劃在北京預(yù)訂一個(gè)周?chē)酗埖甑馁e館,希望獲得周?chē)?公里內(nèi)飯店評(píng)價(jià)等級(jí)最高的前k個(gè)賓館排名列表,并且這些飯店都能提供“西餐和停車(chē)場(chǎng)”,然后從中選擇自己滿(mǎn)意的賓館。而Top-k空間偏好查詢(xún)是根據(jù)空間對(duì)象周?chē)奶卣鲗?duì)空間對(duì)象進(jìn)行等級(jí)評(píng)價(jià),返回k個(gè)最佳對(duì)象的排序列表。例如,一位游客計(jì)劃在北京預(yù)訂一個(gè)周?chē)酗埖旰统械馁e館,希望獲得周?chē)?公里內(nèi)飯店和超市評(píng)價(jià)等級(jí)最高的前k個(gè)賓館排名列表,然后從中選擇自己滿(mǎn)意的賓館。在上述Top-k空間關(guān)鍵字偏好查詢(xún)和Top-k空間偏好查詢(xún)中,賓館是游客感興趣的設(shè)施,超市和飯店是游客關(guān)注的周邊設(shè)施,“周?chē)?公里”是游客提出的空間約束條件,“西餐和停車(chē)場(chǎng)”是飯店的文本約束條件。兩者最主要的區(qū)別在于Top-k空間偏好查詢(xún)不考慮空間對(duì)象中的文本屬性。

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

1 問(wèn)題描述

定義1 數(shù)據(jù)對(duì)象指用戶(hù)感興趣的設(shè)施類(lèi)型,例如上述查詢(xún)實(shí)例中的“賓館”。數(shù)據(jù)對(duì)象集用D表示,p表示數(shù)據(jù)對(duì)象集D中的一個(gè)對(duì)象點(diǎn)。

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

定義3 特征對(duì)象分?jǐn)?shù)指用戶(hù)對(duì)特征對(duì)象的評(píng)級(jí),用符號(hào)w(f)表示。每個(gè)特征對(duì)象的分?jǐn)?shù)被歸一化為[0,1]范圍內(nèi)的數(shù)值。

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

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

定義7 Top-k空間偏好查詢(xún)是指給定一個(gè)數(shù)據(jù)對(duì)象集D{p1,…,pn}和m個(gè)特征對(duì)象集F1,…,Fm,查詢(xún)Q(D,F,θ,k)就是根據(jù)數(shù)據(jù)對(duì)象周?chē)鷿M(mǎn)足約束條件的特征對(duì)象得分來(lái)計(jì)算數(shù)據(jù)對(duì)象點(diǎn)的得分,返回得分最高的k個(gè)數(shù)據(jù)對(duì)象點(diǎn),具體表示為:

(1)

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

(2)

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

(3)

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

(4)

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

對(duì)象點(diǎn)歐式空間分布如圖1所示,橫軸與縱軸刻度值表示距離。從圖1可讀取對(duì)象點(diǎn)的坐標(biāo),例如,p1的坐標(biāo)為(0.5,4)。假設(shè)用戶(hù)查詢(xún)?yōu)镼1(D,(F1,F2),θ,2),其中k=2,D={p1,p2,p3}。a、b表示兩類(lèi)不同的特征對(duì)象。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ù)對(duì)象集D={p1,p2,p3}代表“賓館”,用實(shí)心三角形表示;特征對(duì)象集F1={a1,a2,a3,a4,a5}代表“飯店”,用實(shí)心矩形表示;特征對(duì)象集F2={b1,b2,b3,b4}代表“超市”,用空心矩形表示。特征對(duì)象后邊的數(shù)字表示特征對(duì)象的等級(jí)分?jǐn)?shù),分?jǐn)?shù)一般來(lái)源于用戶(hù)的評(píng)級(jí),歸一化為[0,1]范圍內(nèi)的數(shù)值。

圖1 歐式空間查詢(xún)示例圖

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

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

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

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

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

2 歐式空間中的Top-k空間偏好查詢(xún)方法

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

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

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

2.1.1 SP算法

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

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

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

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

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

2.1.2 GP算法

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

2.1.3 BB算法

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

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

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

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

2.1.4 BB*算法

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

2.1.5 FJ算法

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

2.1.6 SFA算法

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

查詢(xún)實(shí)例1,Q1(D,(F1,F2),θ,2),SFA算法根據(jù)圖1中的對(duì)象點(diǎn),利用R-tree對(duì)Skyline集建立索引,如圖5所示。數(shù)據(jù)對(duì)象p1到特征對(duì)象集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,特征對(duì)象集F1中對(duì)象的分?jǐn)?shù)分別為w(a1)=0.7,w(a2)=0.8,w(a3)=0.5,w(a4)=0.3,w(a5)=0.7,所以數(shù)據(jù)對(duì)象p1與特征對(duì)象集F1映射到距離-分?jǐn)?shù)空間的坐標(biāo)分別為(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ù)對(duì)象和特征對(duì)象對(duì)的映射坐標(biāo)。根據(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算法可以擴(kuò)展到大規(guī)模數(shù)據(jù)集,算法的查詢(xún)效率比較穩(wěn)定。當(dāng)數(shù)據(jù)對(duì)象和特征對(duì)象規(guī)模增大時(shí),SFA算法效率明顯優(yōu)于上述其他算法,k增大時(shí)SFA算法的查詢(xún)效率基本不受影響。

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

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

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

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

TopRNG-G算法主要結(jié)合概念劃分的思想,利用網(wǎng)格到查詢(xún)對(duì)象點(diǎn)的距離進(jìn)行剪枝,當(dāng)該距離大于范圍距離r時(shí),對(duì)網(wǎng)格內(nèi)所有點(diǎn)進(jìn)行剪枝。TopNN-G算法定義一個(gè)距離的全局變量,存儲(chǔ)查詢(xún)點(diǎn)到已找到的最近鄰特征對(duì)象的最遠(yuǎn)距離,利用概念劃分思想將查詢(xún)點(diǎn)周?chē)膯卧窈喜⒊筛拍罹匦?然后根據(jù)查詢(xún)點(diǎn)到概念矩形的最小距離進(jìn)行剪枝,當(dāng)該距離大于當(dāng)前最佳距離時(shí),則對(duì)網(wǎng)格內(nèi)的所有點(diǎn)進(jìn)行剪枝。

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

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

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

表3 算法查詢(xún)效率分析表

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

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

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

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

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

查詢(xún)實(shí)例2為Q2(D,(F1,F2),θ,2),ALPS算法根據(jù)圖2中的對(duì)象點(diǎn),利用R-tree對(duì)Skyline集建立索引(圖7),構(gòu)造圖2中對(duì)象點(diǎn)的Skyline集。數(shù)據(jù)對(duì)象p1到特征對(duì)象集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,特征對(duì)象集F1中對(duì)象的分?jǐn)?shù)分別為w(a1)=0.7,w(a2)=0.8,w(a3)=0.5,w(a4)=0.3,w(a5)=0.7,所以數(shù)據(jù)對(duì)象p1與特征對(duì)象集F1映射到距離-分?jǐn)?shù)空間的坐標(biāo)為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ù)對(duì)象和特征對(duì)象對(duì)映射到距離-分?jǐn)?shù)的坐標(biāo)。根據(jù)數(shù)據(jù)段和特征對(duì)象對(duì)在距離-分?jǐn)?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空間偏好查詢(xún)方法

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

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

查詢(xún)實(shí)例3為Q2(D,(F1,F2),θ,2)。根據(jù)圖8中的對(duì)象點(diǎn),利用R-tree對(duì)Skyline集建立索引,如圖9所示。根據(jù)定義的靜態(tài)維度、靜態(tài)等式、靜態(tài)支配和完全支配,得到每個(gè)數(shù)據(jù)對(duì)象有用的特征對(duì)象:{(p1?a1),(p2?a1),(p3?a1)(p3?a2)(p3?a3)(p3?a5)}{(p1?b1)(p2?b1)(p2?b2)(p2?b3)},將數(shù)據(jù)對(duì)象和特征對(duì)象組映射到距離-分?jǐn)?shù)空間。根據(jù)數(shù)據(jù)對(duì)象和特征對(duì)象組對(duì)之間的支配關(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空間偏好查詢(xún)方法總結(jié)

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

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

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

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

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

4 結(jié)語(yǔ)

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