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

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

1 引 言

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

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

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

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

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

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

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

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

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

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

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

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

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

2 背景及相關工作

2.1 空間多關鍵詞Skyline查詢概述及定義

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

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

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

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

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

定義2.(基于多關鍵詞匹配的加權距離)對于給定的查詢點q以及其對應的查詢關鍵詞q.w,與空間上任意一個對象點oi,若關鍵詞相似度W(oi.w,q.w)=0,其加權距離為一個極大值;若W(oi.w,q.w)>0,其加權距離為歐式空間距離d(oi,q)除以兩點間的關鍵詞相似度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

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

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

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

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

1)遍歷對象點集O,篩選出滿足以下條件的所有對象點構(gòu)成候選集C,如果?oi∈O,d(oi,q)≤R且oi所包含的關鍵詞oi.w與查詢關鍵詞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)對候選集進行空間Skyline計算,所得到的結(jié)果集記為SKSP(Spatial Keywords Skyline Point),其中SSQ為空間Skyline查詢結(jié)果集,結(jié)果集記為SP.而對于空間多關鍵詞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 用戶與對象點空間位置分布Fig.1 Spatial distribution of objects and user points

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

2.2 相關工作

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

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

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

對于空間關鍵詞查詢,許多學者也做了許多相應的研究工作.最初為了解決空間最近鄰問題,學者提出了R-Tree索引結(jié)構(gòu)[11],該索引是一種高度平衡樹且利用MBR對空間進行有效的分割,保證了50%以上的空間利用率.學者們在R-Tree基礎上添加了位圖結(jié)構(gòu)以及倒排索引,通過將空間信息與文本信息相結(jié)合的方式,可以有效地解決空間關鍵詞查詢問題.上述索引結(jié)構(gòu)可以統(tǒng)稱為空間文本索引結(jié)構(gòu),按照空間與文本優(yōu)先關系,空間文本索引可以分為三類,基于空間優(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)有算法在解決空間多關鍵詞Skyline查詢上無法有效地解決用戶偏好問題,導致結(jié)果集質(zhì)量下降.部分算法在解決多關鍵詞匹配的問題上效率底下,對應的索引結(jié)構(gòu)易產(chǎn)生過多的數(shù)據(jù)冗余.為解決上述問題,本文提出了一種空間文本索引STR-Tree,基于該索引結(jié)構(gòu),提出了一種高效的空間多關鍵詞Skyline查詢算法SKS.

3 空間文本索引STR-Tree

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

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

圖2展示了基于R-Tree索引的對象劃分情況,對最小且不可再分的MBR按照空間從上至下,從左至右的規(guī)則進行順序編號.根據(jù)編號,我們對于空間文本對象id進行了重新編碼: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é)點存儲如下信息,info為一組空間坐標對,用來表示當前區(qū)域的空間位置信息,treept為指向下一個節(jié)點的指針,tag紀錄當前區(qū)域的簽名文件信息.葉子節(jié)點存儲如下信息,其中aid表示葉子節(jié)點即最小且不可再被劃分的區(qū)域編號,info表示當前區(qū)域的空間坐標信息,itpt為指向下層倒排索引的指針,num表示當前區(qū)域?qū)ο蟮目倲?shù),tag紀錄當前區(qū)域的簽名文件信息.

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

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

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

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

(4)

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

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

4 空間多關鍵詞Skyline查詢算法

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

算法1.空間多關鍵詞Skyline查詢算法 SKS

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

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

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

2.While!nodeStack.isEmpty()do

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

3.N←nodeStack.pop();

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

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

5.IfN.isLeaf()then

6.C←getCandidate(q.w);

//遍歷當前區(qū)域?qū)南聦拥古潘饕?/p>

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

7.ForeachcinCdo

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

9.Else

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

//若不為葉子節(jié)點,則將孩子節(jié)點進棧

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

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

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

證明:假設對象oi不屬于中間結(jié)果集SP,則SP中必定存在一個對象點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)成非空間支配,因此對查詢點q而言,q位于空間任意位置,o1,o2之間必定不能在文本屬性以及空間屬性上同時構(gòu)成支配,因此根據(jù)定義3,o1,o2必定不構(gòu)成空間文本支配.

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

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

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

(5)

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

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

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

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

1.sp← getHeapTop(SP);

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

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

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支配的點sp

12.Else

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

14. continue;

15.Elseifdt(sp,q)

//若c被SP中的某一點支配

16. break;

17.Ifsppoints to NULLthen

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

不存在控制關系

18. insertcintoSP;

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

5 實驗及分析

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

我們從兩方面驗證了SKS算法的有效性:首先,在小規(guī)模數(shù)據(jù)集上,算法計算結(jié)果與理論計算結(jié)果相同;其次,與INKS算法和ASTD算法的執(zhí)行結(jié)果進行對比,結(jié)果均保持一致,進一步證明算法的有效性.另外,為了更好地避免隨機性,算法查詢性能最終指標以相同環(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ù)據(jù)集進行測試,并在真實數(shù)據(jù)集上對SKS算法進一步驗證.其中,模擬數(shù)據(jù)集分為獨立數(shù)據(jù)集、相關數(shù)據(jù)集、反相關數(shù)據(jù)集三種,數(shù)據(jù)集中所有空間文本對象點均隨機生成,對象點對應的空間橫縱坐標均在[0,100]的數(shù)值范圍內(nèi)隨機取值.對于數(shù)值型文本屬性由文獻[1]提及的數(shù)據(jù)生成器產(chǎn)生,各維度數(shù)值為區(qū)間[0,100]上的隨機值,且規(guī)定數(shù)值越小即表示該維度上的屬性表現(xiàn)越優(yōu),同時與之對應的語義型文本屬性從既定的詞典中隨機選擇生成.真實數(shù)據(jù)集采用yelp商業(yè)點評網(wǎng)站的開源數(shù)據(jù)集,數(shù)據(jù)集中包含美國菲尼克斯等城市的85,883個商鋪的詳細信息,我們將數(shù)據(jù)集中的經(jīng)緯度作為空間位置信息,商鋪的分類信息作為語義型文本屬性,其余星級、瀏覽量等指標作為數(shù)值型文本屬性.

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

(6)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6 結(jié)束語

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

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