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

李星羅,秦小麟,王 寧,周楊淏,鮑斌國(guó)

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

1 引 言

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

隨著移動(dòng)終端設(shè)備的普及和移動(dòng)應(yīng)用的快速發(fā)展,基于空間位置的服務(wù)獲得了越來(lái)越多人的關(guān)注.人們?cè)谌粘Ｉ钪型鶗?huì)提出如下查詢(xún):

查詢(xún)1.查詢(xún)用戶(hù)周?chē)嚯x近、價(jià)格低、服務(wù)質(zhì)量高的旅店,最好擁有地下車(chē)庫(kù).

查詢(xún)2.查詢(xún)學(xué)校周?chē)嚯x近、口味好、價(jià)格低的餐廳且用戶(hù)更偏愛(ài)于川菜.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

定義2.(基于多關(guān)鍵詞匹配的加權(quán)距離)對(duì)于給定的查詢(xún)點(diǎn)q以及其對(duì)應(yīng)的查詢(xún)關(guān)鍵詞q.w,與空間上任意一個(gè)對(duì)象點(diǎn)oi,若關(guān)鍵詞相似度W(oi.w,q.w)=0,其加權(quán)距離為一個(gè)極大值;若W(oi.w,q.w)>0,其加權(quán)距離為歐式空間距離d(oi,q)除以?xún)牲c(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 餐廳語(yǔ)義型屬性信息Table 2 Restaurant semantic attribute informationn

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

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

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

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

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

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

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 用戶(hù)與對(duì)象點(diǎn)空間位置分布Fig.1 Spatial distribution of objects and user points

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

2.2 相關(guān)工作

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

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

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

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

3 空間文本索引STR-Tree

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

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

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

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

對(duì)于上層索引,中間節(jié)點(diǎn)存儲(chǔ)如下信息,info為一組空間坐標(biāo)對(duì),用來(lái)表示當(dāng)前區(qū)域的空間位置信息,treept為指向下一個(gè)節(jié)點(diǎn)的指針,tag紀(jì)錄當(dāng)前區(qū)域的簽名文件信息.葉子節(jié)點(diǎn)存儲(chǔ)如下信息,其中aid表示葉子節(jié)點(diǎn)即最小且不可再被劃分的區(qū)域編號(hào),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

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

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

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

(4)

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

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

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

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

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

輸入:查詢(xún)點(diǎn)q,查詢(xún)關(guān)鍵詞q.w,查詢(xún)范圍R,空間文本對(duì)象點(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ū)域滿(mǎn)足查詢(xún)關(guān)鍵詞q.w與查詢(xún)范圍R

5.IfN.isLeaf()then

6.C←getCandidate(q.w);

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

//計(jì)算當(dāng)前區(qū)域內(nèi)滿(mǎn)足查詢(xún)關(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)棧

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

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

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

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

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

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

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

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

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

(5)

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

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

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

輸出:查詢(xún)中間結(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//遍歷堆中所有對(duì)象

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

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

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

18. insertcintoSP;

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

5 實(shí)驗(yàn)及分析

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

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

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

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

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

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

(6)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6 結(jié)束語(yǔ)

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

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