空間多關(guān)鍵詞Skyline查詢算法

李星羅,秦小麟,王 寧,周楊淏,鮑斌國

(南京航空航天大學(xué) 計算機(jī)技術(shù)與科學(xué)學(xué)院,南京 210016)E-mail:lxldblab@nuaa.edu.cn

1 引 言

隨著信息技術(shù)的高速發(fā)展,數(shù)據(jù)已經(jīng)成為了重要的戰(zhàn)略資源.如何從海量數(shù)據(jù)之中挖掘用戶最感興趣的信息,做出滿足用戶偏好的決策,這使得越來越多的研究者開始關(guān)注Skyline查詢.Borzoniy等人[1]在2001年提出了Skyline查詢,查詢結(jié)果為一組相對較優(yōu)的多維數(shù)據(jù)集合,該集合中的數(shù)據(jù)點(diǎn)均不被其余數(shù)據(jù)點(diǎn)所支配.Skyline查詢與現(xiàn)實生活緊密相關(guān),近年來被廣泛應(yīng)用于多目標(biāo)決策、分布式P2P網(wǎng)絡(luò)以及用戶偏好查詢等領(lǐng)域[2].為了更好地滿足用戶查詢偏好性需求,Choi等將Skyline查詢與關(guān)鍵詞匹配搜索相結(jié)合,以查詢關(guān)鍵詞作為用戶語義型偏好,提出了關(guān)鍵詞Skyline查詢[3].例如,用戶提出一個查詢:希望找到一家服務(wù)質(zhì)量高且價格低的海鮮餐廳,其中“海鮮”、“餐廳”即為查詢關(guān)鍵詞.

隨著移動終端設(shè)備的普及和移動應(yīng)用的快速發(fā)展,基于空間位置的服務(wù)獲得了越來越多人的關(guān)注.人們在日常生活中往往會提出如下查詢:

查詢1.查詢用戶周圍距離近、價格低、服務(wù)質(zhì)量高的旅店,最好擁有地下車庫.

查詢2.查詢學(xué)校周圍距離近、口味好、價格低的餐廳且用戶更偏愛于川菜.

查詢3.查詢城市周圍距離近、環(huán)境好、交通便利的風(fēng)景區(qū),最好景點(diǎn)內(nèi)部可以住宿.

上述查詢可以概括地表述關(guān)鍵詞空間Skyline查詢問題.在查詢的過程中,對象點(diǎn)與查詢點(diǎn)間的距離為一個相對的動態(tài)空間屬性,屬性值隨著發(fā)起查詢的位置變化而變化.目前已有的算法僅僅關(guān)注于靜態(tài)非空間屬性,不能直接用于解決上述查詢問題,需要重新考慮并建立一個基于空間文本對象的支配關(guān)系模型.

同時,現(xiàn)有的關(guān)鍵詞Skyline算法無法很好地解決用戶偏好性.INKS算法與KMS算法通過查詢關(guān)鍵詞與對象包含的關(guān)鍵詞進(jìn)行匹配,篩選出滿足查詢條件的候選對象集[3].而IPOT算法通過將關(guān)鍵詞按照用戶偏好進(jìn)行偏序化,每個查詢關(guān)鍵詞作為一個新的維度進(jìn)行Skyline計算[4],但是隨著查詢關(guān)鍵詞數(shù)量的增加,維度的變化將直接影響Skyline查詢的效率;查詢關(guān)鍵詞之間的權(quán)重關(guān)系,即用戶查詢語義,上述算法均沒有進(jìn)行定量計算.

此外,現(xiàn)有算法的剪枝優(yōu)化策略僅僅關(guān)注于關(guān)鍵詞信息,候選集中的對象還需根據(jù)查詢空間要求進(jìn)行二次過濾.所以造成了對象的重復(fù)遍歷與判定,使得算法查詢效率受到了一定影響.

基于上述問題,提出了一種基于加權(quán)距離的空間文本支配模型,并構(gòu)建了一個針對空間文本對象的索引結(jié)構(gòu),能夠有效處理空間多關(guān)鍵詞Skyline查詢.本文主要貢獻(xiàn)如下:

1)針對用戶多偏好需求問題,提出了一種基于加權(quán)距離的空間文本支配模型;提出了相應(yīng)的枝剪策略,減少了支配判定計算開銷,提高了算法的執(zhí)行效率.

2)提出了一種基于R-Tree的空間文本索引結(jié)構(gòu).并利用位圖結(jié)構(gòu),快速且準(zhǔn)確地定位滿足條件的空間文本對象,極大地提升了算法的查詢效率.

3)采用模擬數(shù)據(jù)集對SKS算法進(jìn)行了對比實驗,并在真實數(shù)據(jù)集上進(jìn)一步驗證了算法的有效性,實驗結(jié)果表明,SKS算法相較于現(xiàn)有算法更為高效.

本文結(jié)構(gòu)如下:第二節(jié)介紹空間多關(guān)鍵詞Skyline查詢的基礎(chǔ)知識和相關(guān)工作,并分析現(xiàn)有方法在解決多關(guān)鍵詞匹配問題和Skyline支配計算時的不足;第三節(jié)提出了空間文本索引STR-Tree,并對其進(jìn)行了詳細(xì)的說明;第四節(jié)基于索引提出了空間多關(guān)鍵詞Skyline查詢算法SKS;第五節(jié)對SKS算法進(jìn)行了實驗評估,并與現(xiàn)有算法進(jìn)行性能對比;最后對本文工作進(jìn)行了總結(jié)與展望.

2 背景及相關(guān)工作

2.1 空間多關(guān)鍵詞Skyline查詢概述及定義

在本小節(jié),我們針對歐式空間下關(guān)鍵詞Skyline查詢進(jìn)行了形式化描述,并進(jìn)一步討論其相關(guān)性質(zhì).

假定空間文本對象點(diǎn)集O是一組含有n維屬性的點(diǎn)集,對象點(diǎn)包含m維動態(tài)空間屬性,例如查詢點(diǎn)q至對象點(diǎn)o的距離值隨查詢點(diǎn)與對象點(diǎn)的位置變化而發(fā)生改變,屬于動態(tài)空間屬性.我們將查詢點(diǎn)q至對象點(diǎn)o的空間距離d(o,q)作為唯一的動態(tài)空間屬性考慮.其余n-m維屬性為靜態(tài)非空間屬性,亦稱文本屬性.我們將文本屬性進(jìn)行擴(kuò)展并劃分為兩類,如表1、表2所示:第一類為數(shù)值型文本屬性,例如價格、好評度等;第二類為語義型文本屬性,即對象描述性關(guān)鍵詞.

為了便于描述及后續(xù)支配計算,若存在某數(shù)值型屬性,其值越大表現(xiàn)越優(yōu),則對其進(jìn)行相應(yīng)的預(yù)處理操作:p(oi)=maxValuei-p(oi).其中,p(oi)表示對象點(diǎn)o在第i維的屬性值,maxValuei表示該維度上屬性值的最大取值.因此,對于下文中對象點(diǎn)所有數(shù)值型屬性,假設(shè)其值越小表現(xiàn)越優(yōu).

定義1.(非空間支配[1])對于任意兩個對象點(diǎn)oi,oj∈O,其中i≠j,且在所有非空間屬性上,oi均不弱于oj,且至少有一維,oi優(yōu)于oj.以上情形,我們稱之為oi在非空間屬性上支配oj,形式化地表述,oinsoj.而所有在非空間屬性上支配oj的興趣點(diǎn)集合我們稱之為oi的非空間屬性支配域,用符號Domns(oj)表示.

表1 餐廳數(shù)值型屬性信息Table 1 Restaurant numeric attribute informationt

定義2.(基于多關(guān)鍵詞匹配的加權(quán)距離)對于給定的查詢點(diǎn)q以及其對應(yīng)的查詢關(guān)鍵詞q.w,與空間上任意一個對象點(diǎn)oi,若關(guān)鍵詞相似度W(oi.w,q.w)=0,其加權(quán)距離為一個極大值;若W(oi.w,q.w)>0,其加權(quán)距離為歐式空間距離d(oi,q)除以兩點(diǎn)間的關(guān)鍵詞相似度W(oi.w,q.w),結(jié)果記為dt(oi,q),公式化抽象表示為:

dt(oi,q)=d(oi,q)/W(oi·w,q.w)

(1)

表2 餐廳語義型屬性信息Table 2 Restaurant semantic attribute informationn

其中,關(guān)鍵詞相似度W(oi.w,q.w)用來表示查詢關(guān)鍵詞與對象所包含的關(guān)鍵詞之間的相似程度.對于用戶給定的一組查詢關(guān)鍵詞,每個查詢關(guān)鍵詞都有與之相對應(yīng)的用戶偏好權(quán)重,該偏好權(quán)重可以由用戶直接給出或者為系統(tǒng)默認(rèn)值.假定查詢用戶q的查詢關(guān)鍵詞q.w={Seafood,Resturant},偏好權(quán)重分別為0.6、0.4.對于對象o4.w={Nightlife,Golf},由于無關(guān)鍵詞能與查詢關(guān)鍵詞匹配,因此其關(guān)鍵詞相似度W(o4.w,q.w)=0*0.6+0*0.4=0,根據(jù)加權(quán)距離定義,由于關(guān)鍵詞相似度為0,通過計算可得其加權(quán)距離為一個極大值;對于對象o1,o1.w={Seafood,Resturant},因而其關(guān)鍵詞相似度為W(o1.w,q.w)=1*0.6+1*0.4=1.因此,與查詢關(guān)鍵詞完全不匹配的無關(guān)對象點(diǎn),可以先行剪枝,減少相應(yīng)支配計算開銷,提高查詢效率.結(jié)合關(guān)鍵詞的加權(quán)距離,以下提出一種新的空間文本支配關(guān)系.

定義3.(空間文本支配)對于給定的查詢點(diǎn)q以及空間上任意兩個對象點(diǎn)oi,oj∈O,其中i≠j,若存在以下情況:若oinsoj,且dt(oi,q)

相比與傳統(tǒng)文本支配,空間文本支配相當(dāng)于在其基礎(chǔ)上人為地新增了一個維度.該維度對應(yīng)的屬性值隨查詢關(guān)鍵詞以及查詢點(diǎn)的空間位置的改變而改變,支配關(guān)系無法在查詢發(fā)起前先行計算,這樣查詢效率將受到很大的影響.

定義4.(空間多關(guān)鍵詞Skyline查詢(SKSQ))對于給定的查詢點(diǎn)q、查詢關(guān)鍵詞q.w、查詢空間范圍R以及空間對象點(diǎn)集O,該查詢過程分為以下兩步:

1)遍歷對象點(diǎn)集O,篩選出滿足以下條件的所有對象點(diǎn)構(gòu)成候選集C,如果?oi∈O,d(oi,q)≤R且oi所包含的關(guān)鍵詞oi.w與查詢關(guān)鍵詞q.w部分匹配,則oi∈C,即對象oi屬于候選對象集C,該過程記為:SKQ(O.w,q.w,R)={C|C?O∧oi∈C,oi.w∩q.w≠?,d(oi,q)≤R}.

2)對候選集進(jìn)行空間Skyline計算,所得到的結(jié)果集記為SKSP(Spatial Keywords Skyline Point),其中SSQ為空間Skyline查詢結(jié)果集,結(jié)果集記為SP.而對于空間多關(guān)鍵詞Skyline查詢過程,可以抽象表示為:

SSQ(Q,q)={SP|SP∈O∧o∈SP,Domst(o)=}

(2)

SKSP=SKSQ(Q,q,R)=SSQ(SKQ(O.w,q.w,R),q)

(3)

圖1 用戶與對象點(diǎn)空間位置分布Fig.1 Spatial distribution of objects and user points

以表1中的對象為例,查詢點(diǎn)與對象空間位置關(guān)系如圖1所示.若查詢關(guān)鍵詞為“Seafood”、“Restaurant”,且用戶偏好權(quán)重默認(rèn)相等,即均為0.5,則滿足查詢關(guān)鍵詞的對象候選集為{o1,o2,o6},根據(jù)定義4,空間多關(guān)鍵詞Skyline查詢結(jié)果為{o1,o2}.

2.2 相關(guān)工作

Borzsonyi[1]提出了兩個著名的Skyline算法:BNL與D&C并應(yīng)用于傳統(tǒng)的關(guān)系數(shù)據(jù)庫系統(tǒng)之中.雖然有很好的普適性,但是算法執(zhí)行效率較差.后續(xù)有學(xué)者陸續(xù)提出了基于R-Tree索引的Skyline查詢算法:NN[5]和BBS[6]算法,NN算法通過遞歸的方法搜索文本區(qū)域最近鄰點(diǎn),并通過相應(yīng)的剪枝策略刪除被該對象支配的所有對象;BBS算法與NN算法類似,同樣是采用了基于R-Tree索引的最近鄰搜索策略,該算法通過維護(hù)一個堆結(jié)構(gòu)來存儲必須被訪問的對象,并利用分支界限法篩選出符合條件的Skyline對象.

隨著Skyline應(yīng)用場景越來越多,語義型文本屬性開始進(jìn)入學(xué)者們的考慮范圍.Wong[4]將數(shù)值型屬性按照傳統(tǒng)的偏序關(guān)系進(jìn)行計算,而語義型屬性因為用戶偏好不同,偏序關(guān)系亦各不相同.因此該算法針對于語義型屬性通過用戶自我擬定的偏序關(guān)系進(jìn)行Skyline計算;Choi等[3]提出了關(guān)鍵詞Skyline查詢,并提出相應(yīng)的查詢算法:INKS與KMS算法.INKS算法通過使用倒排表的方法獲取滿足查詢關(guān)鍵詞的候選集,在其之上利用BNL算法計算得出最終結(jié)果集,該方法擁有良好的普適性但在多關(guān)鍵詞查詢過程中效率較低.而KMS有效地解決了這一問題,利用IR2-Tree樹,通過簽名文件之間高效的位運(yùn)算從而快速過濾與查詢不相關(guān)的文本對象,但由于IR2-Tree是一種基于空間R-Tree的信息檢索樹,在維度較低時效果較好,隨著查詢維度的增加,其效率將顯著下降.Shi[7]提出了一種面向多用戶的空間文本關(guān)系模型STD,并利用IR-Tree索引結(jié)構(gòu),給出了一種可以高效地解決多用戶查詢問題的空間文本Skyline查詢算法ASTD.

近年隨著基于位置服務(wù)的應(yīng)用高速發(fā)展,學(xué)者開始將Skyline查詢引入空間數(shù)據(jù)庫、時空數(shù)據(jù)庫等相關(guān)應(yīng)用的研究之中.Sharifzadeh等學(xué)者[8]提出了空間Skyline查詢:SSQ算法,其針對于多用戶環(huán)境,以各用戶距對象點(diǎn)的空間距離構(gòu)建各個標(biāo)準(zhǔn)維度,旨在選擇一組距離相對所有用戶最優(yōu)的對象.由于SSQ算法在實際生活中普適性較差,因此Son等學(xué)者[8]在SSQ算法的基礎(chǔ)上提出了基于曼哈頓距離空間Skyline的算法,Fu等學(xué)者[10]提出了一種基于道路網(wǎng)空間的連續(xù)范圍Skyline算法.

對于空間關(guān)鍵詞查詢,許多學(xué)者也做了許多相應(yīng)的研究工作.最初為了解決空間最近鄰問題,學(xué)者提出了R-Tree索引結(jié)構(gòu)[11],該索引是一種高度平衡樹且利用MBR對空間進(jìn)行有效的分割,保證了50%以上的空間利用率.學(xué)者們在R-Tree基礎(chǔ)上添加了位圖結(jié)構(gòu)以及倒排索引,通過將空間信息與文本信息相結(jié)合的方式,可以有效地解決空間關(guān)鍵詞查詢問題.上述索引結(jié)構(gòu)可以統(tǒng)稱為空間文本索引結(jié)構(gòu),按照空間與文本優(yōu)先關(guān)系,空間文本索引可以分為三類,基于空間優(yōu)先:R*-IF[12]、IR-Tree[13]、IR2-Tree[14]索引等;基于文本優(yōu)先:I3[15]、S2I[16]、IL-Quadtree[17]索引;松散組合:R-Tree+倒排索引[18,19]、SFC-QUAD[20].

綜上所述,現(xiàn)有算法在解決空間多關(guān)鍵詞Skyline查詢上無法有效地解決用戶偏好問題,導(dǎo)致結(jié)果集質(zhì)量下降.部分算法在解決多關(guān)鍵詞匹配的問題上效率底下,對應(yīng)的索引結(jié)構(gòu)易產(chǎn)生過多的數(shù)據(jù)冗余.為解決上述問題,本文提出了一種空間文本索引STR-Tree,基于該索引結(jié)構(gòu),提出了一種高效的空間多關(guān)鍵詞Skyline查詢算法SKS.

3 空間文本索引STR-Tree

基于上述概念,為解決空間多關(guān)鍵詞高效匹配問題,我們提出了一種混合索引結(jié)構(gòu)——空間文本索引STR-Tree.

該索引結(jié)構(gòu)從邏輯上分為兩層:上層索引對R-Tree索引結(jié)構(gòu)進(jìn)行了擴(kuò)展,在節(jié)點(diǎn)中增加了表示對象關(guān)鍵詞信息的簽名文件,用于描述對象所處區(qū)域的空間與關(guān)鍵詞信息間關(guān)系;下層索引為倒排表結(jié)構(gòu),用于描述關(guān)鍵詞信息與對象本體間對應(yīng)關(guān)系.

圖2展示了基于R-Tree索引的對象劃分情況,對最小且不可再分的MBR按照空間從上至下,從左至右的規(guī)則進(jìn)行順序編號.根據(jù)編號,我們對于空間文本對象id進(jìn)行了重新編碼:id=aid+wid.其中aid表示該區(qū)域的編號,wid表示對象在該區(qū)域的內(nèi)部編號,例如對象o2在區(qū)域的內(nèi)部編號為1.若假定區(qū)域容納空間文本對象的數(shù)量上限值為3,只需個位即能表示區(qū)域內(nèi)部所有對象,且對象所在區(qū)域的編號為2,編碼后對象o2的id為21.結(jié)合上述空間劃分及對象編碼情況,我們建立了如圖3所示的空間文本索引結(jié)構(gòu)——STR-Tree.

圖2 基于R-Tree空間對象劃分Fig.2 Partitioning spatial objects based on R-Tree

對于上層索引,中間節(jié)點(diǎn)存儲如下信息,info為一組空間坐標(biāo)對,用來表示當(dāng)前區(qū)域的空間位置信息,treept為指向下一個節(jié)點(diǎn)的指針,tag紀(jì)錄當(dāng)前區(qū)域的簽名文件信息.葉子節(jié)點(diǎn)存儲如下信息,其中aid表示葉子節(jié)點(diǎn)即最小且不可再被劃分的區(qū)域編號,info表示當(dāng)前區(qū)域的空間坐標(biāo)信息,itpt為指向下層倒排索引的指針,num表示當(dāng)前區(qū)域?qū)ο蟮目倲?shù),tag紀(jì)錄當(dāng)前區(qū)域的簽名文件信息.

圖3 STR-Tree索引結(jié)構(gòu)示意圖Fig.3 STR-Tree index structure diagram

其中簽名文件為一串定長的二進(jìn)制碼(此例中假定二進(jìn)制碼的長度為8),我們通過一個既定的hash函數(shù)將關(guān)鍵詞映射至二進(jìn)制碼中對應(yīng)的bit位,即將該位的0修改至1.但是對于定長的二進(jìn)制碼,若關(guān)鍵詞的數(shù)量過多,必定會出現(xiàn)不同的關(guān)鍵詞通過hash函數(shù)映射至相同的bit位,即位沖突,還需進(jìn)行后續(xù)準(zhǔn)確地關(guān)鍵詞比較操作,這樣大大影響了查詢效率.對此,我們將關(guān)鍵詞分為兩類:第一類關(guān)鍵詞為描述對象本身性質(zhì)的關(guān)鍵詞,如:Golf、Restaurant、Bars等;第二類為描述對象特征的關(guān)鍵詞,如Seafood、Nightlife等.前者類型的關(guān)鍵詞數(shù)量遠(yuǎn)遠(yuǎn)小于后者,且查詢關(guān)鍵詞中必定包含第一類關(guān)鍵詞.我們對此類關(guān)鍵詞構(gòu)建簽名文件,一方面降低位沖突發(fā)生的概率;另一方面,通過簽名文件,在查詢過程中可以先行過濾與查詢關(guān)鍵詞無關(guān)的空間區(qū)域,并剪枝大量的無關(guān)對象點(diǎn).

例如,編號為2的葉子節(jié)點(diǎn),對應(yīng)空間區(qū)域包含的第一類關(guān)鍵詞為:Restaurant、Bars,其中,Restaurant通過hash函數(shù)生成的結(jié)果為0000001,同理,Bars對應(yīng)為00000010.我們通過對上述兩段二進(jìn)制碼進(jìn)行OR操作,生成簽名為00000110,通過該簽名即可同時表示Restaurant、Bars兩種不同的一級關(guān)鍵詞信息.查詢關(guān)鍵詞依舊可以遵循上述過程生成一個新的簽名S,將該簽名S與查詢區(qū)域所對應(yīng)的簽名Si執(zhí)行AND操作,若SAndSi=S則表示該區(qū)域內(nèi)的關(guān)鍵詞包含查詢關(guān)鍵詞,反之,則不包含.因此通過該操作可以避免繼續(xù)訪問不包含查詢關(guān)鍵詞的下級節(jié)點(diǎn),有效地提高了搜索效率.

n.tag=c1.tag∨…∨ci.tag

(4)

其中n.tag為父節(jié)點(diǎn)的簽名信息,c1.tag至ci.tag為父節(jié)點(diǎn)n對應(yīng)的所有子節(jié)點(diǎn)的簽名信息.

對于下層倒排索引,如圖3所示,索引中每個節(jié)點(diǎn)存儲如下信息,kw_info表示該字段存儲的關(guān)鍵詞信息,而wid_flag為一組位向量,位向量每一位對應(yīng)一個對象在該區(qū)域內(nèi)部的wid.假設(shè)若對象oi包含該關(guān)鍵詞,且對象oi的內(nèi)部wid為j,則對應(yīng)位向量第j位置為1,反之保持為0.其中,位向量長度即為區(qū)域上限值k,若k=200,僅需要25bytes的存儲空間,因為往往一個空間文本對象具有多組關(guān)鍵詞,在倒排表的相應(yīng)數(shù)據(jù)元組索引存儲上,造成過多的數(shù)據(jù)冗余,因此相比于傳統(tǒng)倒排表的形式,該方法大大降低了在大數(shù)據(jù)量情況下索引對于存儲空間容量的依賴性.以例詳細(xì)說明,如對于對象o4、o5、o6,區(qū)域內(nèi)部id分別為1、2、3,區(qū)域上限值k=3,以關(guān)鍵詞Nightlife為例,位向量表示為101.執(zhí)行多關(guān)鍵詞查詢時,只需對相應(yīng)的位向量組進(jìn)行位運(yùn)算.例如,查詢關(guān)鍵詞為Nightlife、Resturant以上兩組關(guān)鍵詞所對應(yīng)的位向量分別為101、100,則101 OR 100 =101,結(jié)果101表示區(qū)域內(nèi)部編號為1、3的對象含有上述關(guān)鍵詞.

4 空間多關(guān)鍵詞Skyline查詢算法

基于上述索引結(jié)構(gòu),在本小節(jié)我們提出了SKS算法來解決空間多關(guān)鍵詞Skyline查詢問題.算法SKS在遍歷STR-Tree索引的過程中,在將上層索引節(jié)點(diǎn)對應(yīng)的區(qū)域位置信息與查詢區(qū)域信息進(jìn)行相交區(qū)域判定的同時,通過節(jié)點(diǎn)對應(yīng)一級關(guān)鍵詞的位圖信息與查詢關(guān)鍵詞間的比較,算法從空間與文本兩方面對空間文本對象集過濾.而當(dāng)算法遍歷至葉子節(jié)點(diǎn)時,則通過下層倒排索引,利用bit間的快速位運(yùn)算,獲取滿足所有查詢關(guān)鍵詞的對象,即該子區(qū)域內(nèi)的候選集.基于STR-Tree索引的空間多關(guān)鍵詞Skyline查詢算法如下所示:

算法1.空間多關(guān)鍵詞Skyline查詢算法 SKS

輸入:查詢點(diǎn)q,查詢關(guān)鍵詞q.w,查詢范圍R,空間文本對象點(diǎn)集O,STR-Tree索引

輸出:空間多關(guān)鍵詞Skyline結(jié)果集 SKSP

1.SP← {};C←{};

2.While!nodeStack.isEmpty()do

//以深度優(yōu)先搜索的方式遍歷索引

3.N←nodeStack.pop();

4.IfN.isInRange(q.w,R)then

//若當(dāng)前區(qū)域滿足查詢關(guān)鍵詞q.w與查詢范圍R

5.IfN.isLeaf()then

6.C←getCandidate(q.w);

//遍歷當(dāng)前區(qū)域?qū)?yīng)的下層倒排索引

//計算當(dāng)前區(qū)域內(nèi)滿足查詢關(guān)鍵詞的候選集C

7.ForeachcinCdo

8.SP←calculateSkyline(SP,c,q.w,R);

9.Else

10.nodeStack.push(N.getChildNode());

//若不為葉子節(jié)點(diǎn),則將孩子節(jié)點(diǎn)進(jìn)棧

對于算法1,第2至3行,以棧的方式維護(hù)尚未訪問的STR-Tree上層索引節(jié)點(diǎn);第4至6行對訪問區(qū)域進(jìn)行判斷,若為葉子節(jié)點(diǎn)則通過下層倒排索引計算出滿足查詢條件的候選集C;第7至9行,循環(huán)調(diào)用calculateSkyline方法,進(jìn)行空間文本支配判定并生成新的中間結(jié)果集SP.

由于候選對象與中間結(jié)果集間復(fù)雜的空間文本支配計算,導(dǎo)致算法1中calculateSkyline方法是該算法中最耗時且最頻繁的操作.為此,需要通過優(yōu)化空間文本支配計算過程來提高查詢效率.

定理1.若存在某個空間文本對象oi∈C,其加權(quán)距離小于中間結(jié)果集中距查詢點(diǎn)最近的對象點(diǎn),則該對象oi一定屬于中間結(jié)果集SP.

證明:假設(shè)對象oi不屬于中間結(jié)果集SP,則SP中必定存在一個對象點(diǎn)sp∈SP,使得sp空間文本支配oi.根據(jù)定義3,則spnsoi,且dt(sp,q)

定理2.對任意的空間文本對象o1,o2∈O,若o1,o2之間不構(gòu)成文本支配,則o1,o2必定不構(gòu)成空間文本支配.

證明:由于對象o1,o2之間不構(gòu)成非空間支配,因此對查詢點(diǎn)q而言,q位于空間任意位置,o1,o2之間必定不能在文本屬性以及空間屬性上同時構(gòu)成支配,因此根據(jù)定義3,o1,o2必定不構(gòu)成空間文本支配.

基于上述定理1和定理2,我們采用了如下過濾策略:

1)最小值過濾法:通過一個小頂堆結(jié)構(gòu)對中間結(jié)果集SP進(jìn)行維護(hù),其中堆頂對象sp即為SP中距查詢點(diǎn)p加權(quán)距離最近的點(diǎn).若存在候選對象c的加權(quán)距離小于sp,根據(jù)定理1,對象c一定屬于中間結(jié)果集SP.因為SP中對象均在空間屬性上弱于c,所以后續(xù)只需要進(jìn)行文本支配判定,并直接刪除SP中所有被c文本支配的點(diǎn).

2)求和過濾法:考慮對象在數(shù)值型文本屬性上所有屬性,我們將其值的和作為該過濾策略判定的依據(jù).對于任意一個對象點(diǎn)o,其在屬性維度NS的過濾公式設(shè)計如下:

(5)

上述公式表示對象點(diǎn)o在屬性維度NS上的過濾值S(o),而該過濾值即為點(diǎn)o的非空間屬性值之和.由于該過濾方法時間復(fù)雜度為O(1),相比于時間復(fù)雜度為O(d)(其中d為數(shù)值型文本屬性的維度值)的文本支配判定,可以簡單地先行判定兩個對象點(diǎn)之間的支配關(guān)系.對于任意兩個對象點(diǎn)o1和o2,若S(o1)S(o2),即表明對象o2在屬性維度NS上不可能文本支配對象o1,因為至少有一個維度上o2的值大于o1.因此,通過補(bǔ)充判定對象o1是否文本支配o2,若雙方無文本支配關(guān)系,結(jié)合定理2,可以發(fā)現(xiàn)o1和o2間不存在空間文本支配關(guān)系,則不必繼續(xù)計算,直接進(jìn)行剪枝,從而提高了算法的執(zhí)行效率.

算法2.空間文本支配判定算法 calculateSkyline

輸入:查詢中間結(jié)果集SP,候選對象c,查詢關(guān)鍵詞q.w,查詢范圍R

輸出:查詢中間結(jié)果集SP

1.sp← getHeapTop(SP);

2.Ifdt(c,q)< dt(sp,q)then

3. textualDetele(SP,c);//刪除SP中所有被c文本支配的點(diǎn)

4. insertcintoSP;

5.Else

6. For eachspinSPfrom the Heapdo//遍歷堆中所有對象

7. IfS(c)≤S(sp)then

8. Ifc?Domns(sp) then//不構(gòu)成文本支配

9. continue;

10.Elseifdt(c,q)

11. deletespfromSP;//刪除SP中被c支配的點(diǎn)sp

12.Else

13. Ifsp?Domns(c)then//不構(gòu)成文本支配

14. continue;

15.Elseifdt(sp,q)

//若c被SP中的某一點(diǎn)支配

16. break;

17.Ifsppoints to NULLthen

//指向堆末,表明遍歷完所有對象,即當(dāng)前堆中對象c

不存在控制關(guān)系

18. insertcintoSP;

對于算法2,其中第1至4行通過最小值過濾法對于候選集進(jìn)行枝剪;第6至9行通過求和過濾法進(jìn)行先行支配判定;第10至11行,刪除SP中被支配的對象;第15至16行,若候選對象被支配,則跳出循環(huán).

5 實驗及分析

為驗證SKS算法的性能及其有效性,我們設(shè)計了多組實驗對SKS算法進(jìn)行測試.由于現(xiàn)有的工作中沒有用于專門解決空間多關(guān)鍵詞Skyline查詢的方法,因此將SKS算法與可以解決該問題的INKS算法和ASTD算法進(jìn)行比較.INKS算法基于倒排索引,快速檢索出滿足查詢條件的空間文本對象,并計算出Skyline結(jié)果集;ASTD則利用IR-Tree對無關(guān)對象點(diǎn)進(jìn)行過濾.

我們從兩方面驗證了SKS算法的有效性:首先,在小規(guī)模數(shù)據(jù)集上,算法計算結(jié)果與理論計算結(jié)果相同;其次,與INKS算法和ASTD算法的執(zhí)行結(jié)果進(jìn)行對比,結(jié)果均保持一致,進(jìn)一步證明算法的有效性.另外,為了更好地避免隨機(jī)性,算法查詢性能最終指標(biāo)以相同環(huán)境下10次測試,并除去最大最小值后剩余8次測試值的平均值作為依據(jù).

實驗環(huán)境為:Windows10操作系統(tǒng),Intel Core i7處理器,主頻3.30GHz,內(nèi)存4GB.上述算法均用Java語言實現(xiàn),編譯器為IntelliJ IDEA.

5.1 數(shù)據(jù)集設(shè)置

實驗采用模擬數(shù)據(jù)集進(jìn)行測試,并在真實數(shù)據(jù)集上對SKS算法進(jìn)一步驗證.其中,模擬數(shù)據(jù)集分為獨(dú)立數(shù)據(jù)集、相關(guān)數(shù)據(jù)集、反相關(guān)數(shù)據(jù)集三種,數(shù)據(jù)集中所有空間文本對象點(diǎn)均隨機(jī)生成,對象點(diǎn)對應(yīng)的空間橫縱坐標(biāo)均在[0,100]的數(shù)值范圍內(nèi)隨機(jī)取值.對于數(shù)值型文本屬性由文獻(xiàn)[1]提及的數(shù)據(jù)生成器產(chǎn)生,各維度數(shù)值為區(qū)間[0,100]上的隨機(jī)值,且規(guī)定數(shù)值越小即表示該維度上的屬性表現(xiàn)越優(yōu),同時與之對應(yīng)的語義型文本屬性從既定的詞典中隨機(jī)選擇生成.真實數(shù)據(jù)集采用yelp商業(yè)點(diǎn)評網(wǎng)站的開源數(shù)據(jù)集,數(shù)據(jù)集中包含美國菲尼克斯等城市的85,883個商鋪的詳細(xì)信息,我們將數(shù)據(jù)集中的經(jīng)緯度作為空間位置信息,商鋪的分類信息作為語義型文本屬性,其余星級、瀏覽量等指標(biāo)作為數(shù)值型文本屬性.

為了便于與模擬數(shù)據(jù)集之間進(jìn)行比較,我們對真實數(shù)據(jù)集上數(shù)值型屬性進(jìn)行了處理,使全體數(shù)據(jù)能夠映射到區(qū)間[0,100],數(shù)值轉(zhuǎn)換函數(shù)如下:

(6)

其中p(oi)表示空間文本對象o在維度i上的取值,minValuei與maxValuei表示所有對象在維度i上的最小取值與最大取值.

5.2 數(shù)據(jù)量對算法性能的影響

為了分析與驗證不同數(shù)據(jù)量下對于算法的影響,我們采用了獨(dú)立數(shù)據(jù)集,相關(guān)數(shù)據(jù)集,非相關(guān)數(shù)據(jù)集三種模擬器數(shù)據(jù)集進(jìn)行實驗.其中空間文本對象個數(shù)n由100K到500K變化,數(shù)據(jù)集中數(shù)值型數(shù)據(jù)維度為5維.查詢點(diǎn)q的空間位置坐標(biāo)為隨機(jī)產(chǎn)生,其包含的查詢關(guān)鍵詞數(shù)量為3,查詢半徑為30單位長度.本次實驗以查詢開始至查詢結(jié)束的CPU時間作為查詢算法性能的評價指標(biāo).

圖4 數(shù)據(jù)量對算法性能的影響Fig.4 Performances with scalability of dataset

圖4為不同數(shù)據(jù)量下對應(yīng)三種不同數(shù)據(jù)分布情況的三個算法性能測試結(jié)果.通過對比分析可以得出,隨著數(shù)據(jù)量的上升,三種算法的執(zhí)行計算時間均有所提高.同時可以明顯得出,在數(shù)據(jù)量為100K時,三種數(shù)據(jù)分布下INKS算法查詢計算所用的時間約為SKS算法的2倍以上.且隨著數(shù)據(jù)規(guī)模的逐漸增大,SKS算法相較于其他兩個算法優(yōu)勢越發(fā)凸顯.主要是因為SKS算法在計算過程中,利用STR-Tree快速檢索出滿足查詢條件的有笑點(diǎn),并利用剪枝策略對支配判定過程進(jìn)行優(yōu)化,從而大大減少了訪問無效對象點(diǎn)的次數(shù)和支配計算開銷.

另外,從數(shù)據(jù)分布的角度來看,由于相關(guān)數(shù)據(jù)集、獨(dú)立數(shù)據(jù)集與反相關(guān)數(shù)據(jù)集的Skyline結(jié)果數(shù)依次遞增,因此對象間支配判定計算的次數(shù)也依次遞增.INKS算法與ASTD算法對于數(shù)據(jù)分布的敏感度不高,尤其是在反相關(guān)分布的情況下,上述兩種算法的效率有了明顯的下降.但SKS算法在支配計算的過程中,基于空間文本支配關(guān)系提出了兩種相應(yīng)的過濾策略,使得在數(shù)據(jù)分布發(fā)生變化時,查詢效率沒有受到過多的影響.

5.3 查詢關(guān)鍵詞數(shù)量對算法性能的影響

實驗旨在驗證查詢關(guān)鍵詞數(shù)量的變化對于算法性能的影響程度.因此,考慮在數(shù)據(jù)分布為獨(dú)立分布的情況下,測試數(shù)據(jù)集中空間文本對象為200K個,數(shù)值型屬性維度為5.在查詢點(diǎn)q空間坐標(biāo)保持不變的情況下,查詢關(guān)鍵詞數(shù)量由1到10進(jìn)行變化,查詢半徑為30單位長度.

圖5 查詢關(guān)鍵詞數(shù)量對算法性能的影響Fig.5 Performances with the number of query keywords

如圖5所示,為不同數(shù)量的查詢關(guān)鍵詞在獨(dú)立數(shù)據(jù)集下對于三種查詢算法性能測試結(jié)果.在查詢關(guān)鍵詞數(shù)量較低的情況下,INKS算法效率較好,由于該算法利用倒排索引結(jié)構(gòu),可以直接檢索出滿足查詢條件的有效對象點(diǎn).隨著關(guān)鍵詞數(shù)量的增加,因為倒排索引無法高效地解決冗余數(shù)據(jù)的判重問題,因此INKS算法效率逐漸降低.而SKS算法針對多關(guān)鍵詞匹配問題利用簽名文件,將對象id映射至對應(yīng)的bit位上,并利用基于位圖匹配的倒排索引結(jié)構(gòu),實現(xiàn)了快速的有效對象點(diǎn)檢索.在關(guān)鍵詞數(shù)量較高時,SKS算法的優(yōu)勢越發(fā)明顯,關(guān)鍵詞數(shù)量為7時,相比于ASTD算法查詢性能提高了近90%.

5.4 數(shù)值型屬性維度對算法性能的影響

Skyline查詢計算過程中,空間文本支配關(guān)系的計算次數(shù)隨著數(shù)值型文本屬性的維數(shù)增加而增加,并且直接影響到查詢效率的高低.因此,以下討論數(shù)值型屬性維度的變化對于算法性能的影響.實驗采用獨(dú)立數(shù)據(jù)集,其中空間文本對象個數(shù)為200K個,數(shù)值型屬性維度為2至8維進(jìn)行變化.查詢點(diǎn)q的空間位置坐標(biāo)隨機(jī)產(chǎn)生,查詢關(guān)鍵詞數(shù)量為3,查詢半徑為30單位長度.

圖6為不同維度下三種算法的查詢性能測試結(jié)果.由上圖可以得出,ASTD算法在數(shù)據(jù)維度較小時表現(xiàn)較優(yōu),但是隨著維度的升高,算法的性能逐漸降低,尤其到了維數(shù)為6的時候,性能下降程度明顯.而SKS算法在低維度的時候算法性能與ITS算法不相上下,主要是此時遍歷索引的時間耗費(fèi)成為了制約因素;而隨著數(shù)據(jù)維度的升高,SKS算法通過采用了相應(yīng)的剪枝機(jī)制,有效地減少了無關(guān)對象點(diǎn)間數(shù)值型屬性間支配關(guān)系計算開銷,維度為8時,ASTD算法計算所用時間約為SKS算法的3倍.

圖6 數(shù)值型屬性維度對算法性能的影響Fig.6 Performances with numeric attribute dimension

5.5 真實數(shù)據(jù)集下的算法性能

實驗采用了yelp點(diǎn)評網(wǎng)站上的開源數(shù)據(jù)集對于算法性能進(jìn)行了進(jìn)一步驗證,數(shù)據(jù)集中包含來自美國菲尼克斯等11個城市85883個商鋪信息,每個商鋪對應(yīng)的數(shù)值型文本屬性維度為3,查詢點(diǎn)q隨機(jī)產(chǎn)生,查詢關(guān)鍵詞數(shù)量為3,查詢半徑由10度到50度(經(jīng)緯度)之間變化.

圖7 真實數(shù)據(jù)集下的算法性能Fig.7 Performances with real-life dataset

圖7展示了在真實數(shù)據(jù)集下查詢范圍變化與算法執(zhí)行效率的關(guān)系.由圖可以分析得出,隨著查詢經(jīng)緯度的范圍擴(kuò)大,被查詢點(diǎn)數(shù)量也隨之增加,查詢算法的效率均有所降低.在真實數(shù)據(jù)集下,SKS算法相較于其余兩種算法具有較高的查詢效率,與模擬數(shù)據(jù)集下的實驗測試結(jié)果保持一致,進(jìn)一步證明了SKS算法的高效性.

6 結(jié)束語

本文從用戶提出多角度偏好的需求出發(fā),針對空間位置動態(tài)變化問題進(jìn)行深入研究,提出了一種空間多關(guān)鍵詞Skyline查詢解決方案.為了快速處理空間多關(guān)鍵詞匹配并有效地剪枝無關(guān)空間區(qū)域,提出了一種空間文本索引結(jié)構(gòu)STR-Tree;在該索引結(jié)構(gòu)基礎(chǔ)上,提出了一種高效的空間多關(guān)鍵詞Skyline查詢的算法SKS.最后,在模擬數(shù)據(jù)集與真實數(shù)據(jù)集上進(jìn)行實驗,結(jié)果表明本文提出的方法能夠有效地解決空間多關(guān)鍵詞Skyline查詢問題,且擁有更為優(yōu)良的查詢性能.

上述工作可以很容易地擴(kuò)展至道路網(wǎng)環(huán)境.另外,未來研究工作將重點(diǎn)關(guān)注如何解決多用戶環(huán)境下的空間關(guān)鍵詞Skyline查詢,引入交互式查詢思想,以解決用戶偏好不一致問題.