基于位置的發(fā)布/訂閱索引結(jié)構(gòu)

羅昌銀,唐玉茹,李子蹊,李艷紅,但唐朋

(1 華中師范大學 計算機學院,武漢 430079；2法國國立應用科學學院 機械系,里昂；3中南民族大學 計算機科學學院,武漢 430074)

隨著互聯(lián)網(wǎng)技術(shù)的發(fā)展和移動智能終端設(shè)備的普及,空間文本數(shù)據(jù)量以前所未有的速度增長.針對空間文本數(shù)據(jù)的研究已經(jīng)成為數(shù)據(jù)庫領(lǐng)域中的一個熱門話題[1].傳統(tǒng)的發(fā)布/訂閱方法在處理空間文本數(shù)據(jù)時效率不高,本文將研究面向空間文本數(shù)據(jù)的發(fā)布/訂閱技術(shù),為用戶提供更加靈活、高效的訂閱方法.

在發(fā)布/訂閱系統(tǒng)中存在兩個主體：發(fā)布者與訂閱者.發(fā)布者發(fā)布新消息,訂閱者(用戶)訂閱他們感興趣的消息[2].當新消息到來時立刻執(zhí)行消息與訂閱的匹配工作.如果兩者完全匹配,則消息被發(fā)送給訂閱者[3].基于位置的發(fā)布/訂閱在現(xiàn)實生活中有很多的應用,比如武漢萬達電影院發(fā)布的信息{(電影名：忠犬八公),(票價：31元),(地點：武漢萬達影院)},人們可以根據(jù)空間與文本信息選擇電影院.Flickr上的照片除了有空間信息和文本信息,每一張照片還有視圖數(shù)量、評論數(shù)等數(shù)字屬性,人們可根據(jù)空間和文本信息來選擇他們所需的照片.

由于移動設(shè)備產(chǎn)生的數(shù)據(jù)具有各式各樣的大量屬性,為了更好地處理空間文本數(shù)據(jù),本文使用布爾表達式表示空間文本對象的文本屬性.相比于空間關(guān)鍵詞,布爾表達式能夠表達豐富的空間文本信息及其屬性范圍,還能更加靈活地表達用戶的查詢[4].空間文本對象中的文本由多個謂詞表示,其中每個謂詞都包括屬性名、關(guān)系操作符和屬性值,而消息由屬性值對組成.只有消息中所有屬性都出現(xiàn)在訂閱中且各個屬性值都在訂閱相應屬性值的范圍內(nèi),消息與訂閱才完全匹配.此時可以將消息發(fā)送給訂閱者.

1 相關(guān)定義與問題分析

基于位置的發(fā)布/訂閱中,訂閱者使用布爾表達式表示自己的興趣偏好,發(fā)布者發(fā)布的消息也以布爾表達式的形式表示.基于位置的發(fā)布/訂閱不僅能夠匹配消息與訂閱的空間信息,還能夠匹配文本信息,從而得到符合用戶需求的消息[5].以下面是文中使用的相關(guān)定義.

定義1謂詞.謂詞是一個三元組,定義為P=(A,oper,value),其中A表示屬性名,oper表示操作符,可以是>,<,= 等.value表示屬性值. 為了評判x值是否滿足謂詞約束,可以通過下式進行判定[6].如果給定的值在謂詞要求的范圍內(nèi),則返回1,否則返回0.

P(A,oper,value)(x)→{0,1}.

例如 謂詞P=(price,>,80)表示的意思是price>80,則P(90)=1,P(70)=0.

定義2訂閱.訂閱由多個謂詞與一個最小邊界矩形表示,即S={P1,…,Pn；R},其中P1,…,Pn是訂閱S中的謂詞列表,表示用戶的興趣偏好.R表示最小邊界矩形,表示用戶感興趣的位置范圍.

例如 訂閱{(price,>,100),(price,<,400), (name,=,bicycle)；R1}的具體含義是在R1范圍內(nèi)找到價格在100～400元之間的自行車.

定義3消息.消息由多個謂詞與邊界矩形表示,即E={P1,…,Pn；R},其中各個符號的含義與訂閱中符號的含義相同.

例如 消息{(price,=,350),(name,=,bicycle)；R2}的含義是消息在R2位置內(nèi)并且具有的文本屬性是價格等于350元的自行車.

定義4匹配.基于位置的發(fā)布/訂閱進行消息與訂閱的匹配時,需要滿足空間約束與文本約束.

空間約束；消息E與訂閱S具有重疊的空間,即S.R∩E.R?.

文本約束；消息E中的謂詞屬性全部出現(xiàn)在訂閱S中,即 ?p?q(p∈S∧q∈E→p.A=q.A∧p(q.oper) = 1 ).

圖1 訂閱集合Fig.1 Collection of subscriptions

由以上定義可知,消息E的最小邊界矩形與S的最小邊界矩形重疊,則E與S空間信息匹配.消息E的屬性滿足訂閱S的屬性,則文本信息匹配.只有同時滿足空間約束與文本約束才可以判定消息E與訂閱S匹配.此時,消息E作為匹配結(jié)果發(fā)送給訂閱S.

圖1中包含的訂閱與消息如下：

S1={(A,=,3),(B,=,3),(C,≥,2);R1},

S2={(A,≥,9),(C,≤,2),(E,≤,9);R2},

S3={(B,≤,2),(E,=,2);R3},

S4={(B,=,3),(E,≥,4);R4},

S5={(C,=,4),(D,=,2),(E,≤,9);R5},

S6={(A,≤,2),(C,≥,2);R6},

S7={(B∈(2,3,5)),(C,=,4);R7},

S8={(B,=,3),(C,≥,2);R8},

E1={(A,=,3),(B,=,3),(C,=,5);P1},

E2={(B,=,3),(C,=,4);P2}.

消息E1與訂閱S1,S2重疊,則S1與S2滿足空間約束.但是E1中沒有屬性E,且屬性C與屬性A不滿足S2對應屬性值的范圍,即E1與S2匹配時不能滿足文本約束,因此消息E1不能夠與訂閱S2匹配.而E1中的屬性全部滿足S1,且E1中每個屬性的屬性值都在S1相應屬性值的范圍內(nèi),則E1與S1匹配.

2 索引結(jié)構(gòu)介紹

由于空間文本對象具有空間屬性與文本屬性,在進行消息與訂閱的匹配時,不僅要進行空間修剪,還要進行文本修剪[7].但是由于訂閱的數(shù)量較多并且消息到來的頻率較高,這對基于位置的發(fā)布/訂閱來說是一個巨大的挑戰(zhàn)[8].為了減少消息與訂閱匹配過程中產(chǎn)生過多的候選節(jié)點,更好地滿足用戶的需求,避免用戶淹沒在大量的匹配結(jié)果中,本文使用空間約束與文本約束以得到最符合訂閱的消息.TR-tree索引結(jié)構(gòu)首先使用空間約束得到一定數(shù)量的候選訂閱,再使用文本約束進行匹配,最后得到結(jié)果,不僅減少了需要匹配的訂閱的數(shù)量,還高效地進行了匹配工作.

2.1 選擇關(guān)鍵屬性

隨著網(wǎng)上購物的流行,出現(xiàn)了各種各樣的商品,且商品具備的屬性各不相同,以傳統(tǒng)關(guān)鍵詞的方式表示文本屬性已不能滿足需求[9].布爾表達式能夠表示結(jié)構(gòu)化、半結(jié)構(gòu)化與非結(jié)構(gòu)化的屬性,這樣的表示方式比關(guān)鍵詞更加靈活,因此本文使用布爾表達式表示消息與訂閱的屬性.

為了更好地對訂閱分組,減少匹配過程中候選訂閱的數(shù)量,提升消息與訂閱的匹配速度,TR-tree索引使用了關(guān)鍵屬性.關(guān)鍵屬性的選擇有以下幾種方式:

1)隨機選擇關(guān)鍵屬性.根據(jù)訂閱中已有的屬性值,隨機選擇多個能夠表示全部訂閱的屬性值作為關(guān)鍵屬性.關(guān)鍵屬性能夠減少候選訂閱的數(shù)量以加快匹配速度.但是隨機選擇關(guān)鍵屬性存在的缺點是：隨機產(chǎn)生的關(guān)鍵屬性不能夠表示全部訂閱；

2)選擇出現(xiàn)頻率較小的屬性作為關(guān)鍵屬性.這種方式得到的關(guān)鍵屬性可以最大限度地減少候選訂閱的數(shù)量,但是其缺點與隨機選擇關(guān)鍵屬性一樣；

3)選擇出現(xiàn)頻率較大的屬性作為關(guān)鍵屬性.這種方式得到的關(guān)鍵屬性可以最大程度地保證每個訂閱都可以以關(guān)鍵屬性的形式表示.因此,本文使用這種方式選擇關(guān)鍵屬性.例如,根據(jù)圖1訂閱中出現(xiàn)的屬性,得到高頻率的屬性B與C,則每個訂閱的關(guān)鍵屬性如表1所示.

表1 關(guān)鍵屬性Tab.1 Key attributes

2.2 文本索引

文本索引主要分為訂閱分組與謂詞分組兩部分.首先,將所有的訂閱根據(jù)其包含的謂詞數(shù)量進行分組得到L(count).然后,根據(jù)關(guān)鍵屬性A對L(count)再次分組以得到文本索引L(A).文本索引還使用操作符列表存儲謂詞,為了避免重復存儲相同的謂詞,文本索引中每個訂閱都有一個指向訂閱包含的謂詞的指針.圖1中的訂閱包含的謂詞數(shù)量如表2所示.

表2 謂詞數(shù)量Tab.2 Number of predicates

根據(jù)訂閱中包含謂詞數(shù)量的不同,將所有的訂閱分組之后如圖2所示.

圖2 訂閱分組Fig.2 Subscription group

訂閱分組之后,再對其進行謂詞分組.由表 1 可得訂閱的關(guān)鍵屬性為C、B.得到的謂詞分組如圖3所示.

圖3 謂詞分組Fig.3 Predicates group

2.3 索引結(jié)構(gòu)

CHEN Z等人[10]提出的kdt-tree使用空間關(guān)鍵詞表示訂閱者的興趣偏好.但是隨著智能手機的廣泛使用,消息與訂閱中包含的文本信息的種類越來越多,并且各種信息的屬性值也有顯著的差異,使用關(guān)鍵詞的形式表示文本信息已不能滿足用戶對發(fā)布/訂閱的需求,人們期待使用更加高效與靈活的方式表示自身的興趣偏好.為了滿足用戶對基于位置的發(fā)布/訂閱的新需求,TR-tree的文本索引結(jié)構(gòu)使用布爾表達式表示用戶興趣偏好.布爾表達式不僅能表示各種類型的信息,還能夠更加靈活地展示文本屬性. ZHANG D等人[11]研究的索引結(jié)構(gòu)OPindex,構(gòu)建時間較短并且使用了布爾表達式表示謂詞.雖然此索引結(jié)構(gòu)具有高效的文本修剪能力,但是卻沒有使用空間約束,無法進行空間修剪,更無法對消息與訂閱進行空間匹配.為了避免OPindex存在的不足,TR-tree使用了過濾驗證的方式實現(xiàn)空間修剪與文本修剪,進而為訂閱者篩選出滿足空間約束與文本約束的消息.傳統(tǒng)的R-tree是針對所有訂閱而構(gòu)建的,當新消息到來時,需要判斷所有的節(jié)點是否與消息存在空間上的重疊.當新消息到來的頻率較快時,消息與訂閱的匹配次數(shù)顯著增加,此時R-tree的空間修剪能力將會顯著下降.為了更好地進行消息與訂閱的空間匹配,需要對R-tree進行改進,這樣才能夠較好地展現(xiàn)其空間修剪能力.TR-tree主要包括以布爾表達式表示的文本結(jié)構(gòu)和根據(jù)關(guān)鍵謂詞與謂詞數(shù)量構(gòu)建的空間結(jié)構(gòu)R-tree.文本結(jié)構(gòu)以布爾表達式的形式表示謂詞,實現(xiàn)了消息與訂閱的文本修剪.為了避免重復存儲謂詞,文本結(jié)構(gòu)使用操作符列表存儲不同的屬性值對.R-tree根據(jù)消息中關(guān)鍵謂詞與謂詞的數(shù)量進行消息與訂閱的空間修剪.

為了更好地展現(xiàn)訂閱者的興趣偏好,并且執(zhí)行消息與訂閱的高效匹配,TR-tree索引結(jié)構(gòu)使用了空間索引與文本索引.其中空間索引R-tree對空間文本對象進行空間修剪.為了減少中間結(jié)果的數(shù)量,提升匹配效率,R-tree是根據(jù)謂詞數(shù)量與關(guān)鍵謂詞構(gòu)建的.當新消息到來時,根據(jù)消息中的關(guān)鍵謂詞與謂詞數(shù)量找到匹配的R-tree以修剪不滿足空間約束的訂閱.經(jīng)過空間約束而得到的訂閱作為候選訂閱再進行文本匹配,在文本匹配的過程中會修剪不滿足文本約束的訂閱,從而得到匹配結(jié)果.文本索引是根據(jù)謂詞數(shù)量與關(guān)鍵謂詞對訂閱分組的,不僅能加快消息與訂閱的匹配,并且為了避免存儲重復的謂詞,文本索引根據(jù)謂詞中的操作符建立了不同的列表,從而減少內(nèi)存空間的使用.

TR-tree索引結(jié)構(gòu)如圖4所示,圖中L(2)與L(3)是文本索引.R-tree(2,C),R-tree(2,B)與R-tree(3,C)是根據(jù)謂詞數(shù)量與關(guān)鍵謂詞建立的空間索引,其結(jié)構(gòu)如圖5所示. 而“=”,“≤”,“≥”的列表是存儲謂詞,這樣可以避免重復存儲謂詞,減少內(nèi)存的使用.

圖4 TR-tree結(jié)構(gòu)Fig.4 The structure of TR-tree

圖5 R-treeFig.5 R-tree

本文的匹配算法步驟如下：

步驟1 輸入消息E,初始化結(jié)果集R、候選結(jié)果集C；

步驟2 獲得消息E的謂詞數(shù)量m與E中包含的關(guān)鍵謂詞keyArr；

步驟3 根據(jù)m與keyArr找到空間索引中滿足謂詞數(shù)量為m、關(guān)鍵謂詞為keyArr的空間索引結(jié)構(gòu)R-tree(m,keyArr)；

步驟4 遍歷R-tree(m,keyArr)進行空間修剪,如果滿足空間約束,則作為候選節(jié)點并加入候選結(jié)果集C中；否則訂閱被修剪,不再進行文本匹配；

步驟5 逐一對候選結(jié)果集C中的訂閱進行謂詞匹配,找到滿足謂詞約束的訂閱并將其加入結(jié)果集R中,否則修剪；

步驟6 得到滿足空間約束與文本約束的訂閱集R,遍歷其中的訂閱,將消息E發(fā)送給相應的訂閱者.

3 實驗

3.1 實驗環(huán)境

實驗環(huán)境設(shè)置為：CPU為Intel Core i5 4200H,內(nèi)存為 4GB,機械磁盤為1T,操作系統(tǒng)為Windows 10,集成開發(fā)環(huán)境為Eclipse：Lunna Service Release.

實驗的測試數(shù)據(jù)集有GeneDS與 RealDS,其中GeneDS是通過程序隨機產(chǎn)生的數(shù)據(jù)集,屬性與屬性值分別使用26個字母與隨機數(shù)隨機生成,位置信息使用4個隨機數(shù),這4個隨機數(shù)分別代表最小邊界矩形的4個頂點.RealDS是真實數(shù)據(jù)集,即基于淘寶的商家信息、Twitter 與 Wikipedia的空間文本數(shù)據(jù).其中,每條數(shù)據(jù)都包括謂詞、經(jīng)度、緯度等信息.從中隨機選擇5%作為初始化訂閱集合,并對相應的屬性值加上對應的操作符.

3.2 實驗結(jié)果

OPindex沒有空間索引,不具備空間修剪的性能.TR-tree與OPindex進行了文本索引對比.由圖6可知,數(shù)據(jù)規(guī)模較小時,TR-tree的文本索引結(jié)構(gòu)與OPindex的文本修剪能力相差不大甚至相同；但隨著數(shù)據(jù)規(guī)模的增加,TR-tree索引結(jié)構(gòu)具備較強的文本修剪能力,能夠更好地進行文本匹配.

圖6 數(shù)據(jù)規(guī)模對處理時間的影響Fig.6 Impact of data-size on processing time

圖7 對比了RP-trees[12]與TR-tree的內(nèi)存消耗.RP-trees與TR-tree都是在內(nèi)存中進行匹配操作,屬于內(nèi)存駐留索引結(jié)構(gòu).通過兩種索引結(jié)構(gòu)的內(nèi)存消耗對比可知隨著訂閱數(shù)量的增加,RP-trees的內(nèi)存消耗顯著增加. TR-tree索引結(jié)構(gòu)使用操作符列表實現(xiàn)謂詞屬性的索引,避免了重復存儲謂詞,因此內(nèi)存的消耗比RP-trees少.

圖7 內(nèi)存消耗Fig.7 Memory consumption

圖8 對比了TR-tree與RP-trees的消息與訂閱的匹配速度. TR-tree可以實現(xiàn)消息與訂閱的高效匹配,即使訂閱的數(shù)量逐漸增加,其匹配能力遠遠超過PR-trees. PR-trees之所以需要耗費大量的時間是因為在消息與訂閱匹配的過程中需要不斷地更新計數(shù)數(shù)組,而在更新計數(shù)數(shù)組時需要隨機訪問整個數(shù)組,因此耗費的時間較多.

圖9對比了TR-tree與RP-trees隨著屬性值的增加而產(chǎn)生的內(nèi)存消耗.兩種索引結(jié)構(gòu)都是使用關(guān)鍵謂詞對訂閱分組.但是隨著謂詞屬性數(shù)量的增加,兩種索引結(jié)構(gòu)的內(nèi)存消耗有著顯著的差別.隨著屬性值種類的增加, PR-trees會不斷地重復存儲謂詞包含的屬性值,需要消耗較多的內(nèi)存；而TR-tree使用了操作符列表,避免了重復存儲謂詞,因此屬性的增加并不會對內(nèi)存產(chǎn)生過多影響.

圖8 匹配時間Fig.8 Matching time

圖9 屬性值的內(nèi)存消耗Fig.9 Memory consumption of attribute values

4 結(jié)論

通過對空間文本數(shù)據(jù)的研究,本文針對基于位置的發(fā)布/訂閱提出具有空間約束與文本約束的索引結(jié)構(gòu)TR-tree.TR-tree包括文本索引與空間索引.文本索引以關(guān)鍵謂詞與謂詞數(shù)量實現(xiàn)訂閱的有效分組,并且使用操作符列表存儲謂詞,減少重復存儲謂詞的次數(shù),將內(nèi)存的使用控制在合理的范圍內(nèi).空間索引根據(jù)關(guān)鍵謂詞與謂詞數(shù)量構(gòu)建不同的R-tree,增強了空間索引的空間修剪能力.實驗表明TR-tree索引結(jié)構(gòu)具有較強的匹配能力,并且隨著數(shù)據(jù)量的增加并沒有消耗過多的內(nèi)存.