張素智, 趙亞楠, 楊 芮
(鄭州輕工業(yè)學院 計算機與通信工程學院, 鄭州 450002)
基于MPB-Tree索引的空間數(shù)據(jù)多關鍵詞模糊查詢算法研究
張素智*, 趙亞楠, 楊 芮
(鄭州輕工業(yè)學院 計算機與通信工程學院, 鄭州 450002)
隨著具有定位功能的智能設備的大量使用,產(chǎn)生出海量的空間數(shù)據(jù),每條數(shù)據(jù)中包含的信息越來越多,而以往的查詢算法多數(shù)僅對單個關鍵詞進行查詢,已難以滿足用戶更為個性化的需求.為此,本文提出一種多空間關鍵詞模糊查詢算法,在該算法中,將以往的兩維空間距離計算轉化為莫頓碼匹配提升查詢效率,且與模糊查詢算法融合支持查詢的容錯.實驗結果表明,該算法的效率及準確性較以往查詢算法有較大提高.
空間數(shù)據(jù); 多關鍵詞查詢; 莫頓碼; 模糊查詢
近年來,移動信息產(chǎn)業(yè)發(fā)展迅速,隨著移動終端設備的普及,產(chǎn)生出海量的數(shù)據(jù),而這些數(shù)據(jù)都具備地理位置信息和文本內(nèi)容雙重屬性,例如在QQ空間或微博中發(fā)布信息,都可以標注出用戶所處的地理位置,因此基于位置的服務(Location Based Service , LBS)得到人們的廣泛關注.
目前的LBS系統(tǒng)把關鍵詞查詢[1](Spatial Keyword Query)作為處理空間數(shù)據(jù)的主要方式之一,簡單的說,假定空間數(shù)據(jù)集中有多個興趣點(Points of Interest,POI),每一個POI點都包含兩種屬性的信息:文本信息和位置信息,用戶通過輸入關鍵詞將其作為查詢約束條件,從而檢索得到符合要求的POI點.這種處理方式也被各搜索引擎公司采用,但隨著空間數(shù)據(jù)量不斷增長、用戶需求更加個性、智能移動設備功能的更加齊全導致以往的查詢算法漸漸無法滿足用戶不斷提高的需求.
在實際使用中,用戶為了獲得更為豐富的信息,輸入多個關鍵詞作為查詢條件是經(jīng)常出現(xiàn)的,但一個POI點包含的信息有限,有很大幾率不能完全覆蓋用戶所輸入的全部文本內(nèi)容,例如,用戶輸入休閑、購物、飯店就可能需要多個POI點協(xié)作才能滿足用戶需求.而且現(xiàn)在用戶經(jīng)常用便攜的移動設備進行查詢,例如手機,其可操作面積較小,有較大幾率輸入不規(guī)范的查詢詞,例如將“星巴克”誤寫為“星吧克”,因此還需要查詢算法具備一定的容錯性.如何從海量的空間數(shù)據(jù)中快速高效地找出對應的信息已成為目前的研究熱點之一.
空間關鍵詞查詢目前還處于初步階段,經(jīng)過大量學者的研究仍取得一定成果:Yao[2]等人建立MHR-Tree索引結構,并提出一種近似匹配查詢算法,將編輯距離引入實現(xiàn)查詢的容錯,在MHR-Tree內(nèi)各子節(jié)點中增設簽名對查詢結果進行裁剪,但其質量無法保證,使得查詢效果并不理想;Yu[3]等人通過建立MRD-tree索引,允許數(shù)據(jù)入口放到中間節(jié)點處,減少I/O重復次數(shù)解放出大量計算資源;Wang[4]等人提出RB-Tree作為索引結構,加入位圖使查詢的穩(wěn)定性和準確性得到提高;Zhang[5]等人將模糊匹配融入到k近鄰查詢中,使得查詢結果更為符合需求;Yi[6]等人對Patricia樹索引進行改進,大幅度提高了查詢速度.
但以上都是以單關鍵詞為主進行研究,對多關鍵詞查詢關注較少.而且近似匹配查詢是用編輯距離[7]來衡量查詢詞與POI點的相關程度,通過閾值對POI點進行剪切,然而在實際使用中發(fā)現(xiàn)查詢詞的文本長度是變化的,長文本需要的閾值可能較大,短文本的則較小,閾值過大或過小都可能導致查詢結果質量不高,設置出合適閾值的難度很大;其次,隨著空間文本數(shù)據(jù)量的激增,傳統(tǒng)的歐式空間距離方法已難以滿足人們?nèi)找嫣岣叩男枨?,而且以往的空間數(shù)據(jù)關鍵詞查詢研究多數(shù)僅考慮空間信息的相關性,對文本相關考慮不夠深入.
對于以上提出的問題,本文設計出一種空間數(shù)據(jù)多關鍵詞模糊查詢算法SMFQ (Spatial Multi-Keyword Fuzzy Query),該算法綜合考慮文本相關性及空間相關性,融合近似匹配查詢方法,支持模糊查詢;不設置固定的編譯距離閾值,將其與排序算法相融合找出與查詢詞最相似的k個關鍵詞,支持容錯且使算法更為靈活.為滿足用戶日益提高的查詢要求,SMFQ算法需支持:
1) 該算法支持多關鍵詞的模糊查詢,查詢結果覆蓋用戶輸入的所有文本內(nèi)容,包含一些文本較長且較復雜的詞,比如Four Seasons Resort.
2) 得到的查詢結果應該是距離用戶最近的,且不過于分散.
3) 該算法對查詢結果排序,將最相關的信息優(yōu)先顯示給用戶.
為此,本文引入編輯距離、關鍵詞權重、莫頓碼[8]、空間和文本相關性[9]等概念,綜上本文的主要貢獻如下:
1) 基于RB-Tree與Patricia索引建立出支持多關鍵詞近似查詢的索引結構MPB-Tree.
2) 提出并設計了空間數(shù)據(jù)上多關鍵詞模糊查詢算法.
3) 使用真實數(shù)據(jù)進行仿真測試,用實驗結果證明SMFQ算法具有較高的可行性及查詢效率.
在給定的某個空間文本數(shù)據(jù)集中,設O表示一組POI點,即O={p1,p2,p3, …,pn},p={o,t}則有O={(o1,t1.1,t1.2,…,t1.w)……(on,tn.1,…,tn.w)}其中每個POI點對象p都包含有空間位置信息o和文本信息集合t,如圖1所示.
圖1 空間數(shù)據(jù)內(nèi)在分布關系Fig.1 Spatial distribution of spatial data
假定多空間關鍵詞查詢Q={ql,qT},ql表示空間位置,qT表示文本詞集合,那么可以存在,ti是用戶輸入的查詢詞,ki表示編輯距離上限,ql和ol均用二維空間數(shù)值{lon,lat}表示,其中l(wèi)on和lat分別代表經(jīng)度和緯度.
2.2.1 文本相關性 本文中SMFQ算法支持查詢?nèi)蒎e,即允許查詢關鍵詞qt與POI對象詞ot不完全相同,具體的說,本文計算衡量文本相關性主要依據(jù)兩個因素:關鍵詞權重和編輯距離.
首先,定義空間數(shù)據(jù)上的多關鍵詞查詢集(Spatial Multi-Keyword Set, SMKS),表示為:
{t1,t2,t3,…,tm},1≤|m|≤|qt|.
(1)
在實際生活中,不同的POI點擁有相同的詞匯描述的現(xiàn)象是肯定存在的,如圖1所示,有三個不同的POI點:p3、p5、p6,它們具有一個相同的文本描述詞“NewBalance”.另外,SMFQ是近鄰查詢,可能僅考量空間位置就可以滿足查詢要求,但是查詢結果的文本相關性無法保證,因而篩選出與查詢詞最相關的POI點,就需要通過使用權重值進行衡量,查詢關鍵詞qt對相應對象O的權重越大說明其文本越相關,需被優(yōu)先檢索.
本文計算權重的方法是在TF-IDF模型[10]基礎上優(yōu)化后得到的:
(2)
其中,tf(t,oT)表示關鍵詞t在oT中出現(xiàn)的次數(shù),次數(shù)與權重成正比,idf(t,P)表示在查詢范圍內(nèi)的POI點中包含有關鍵詞t的個數(shù)的倒數(shù).wmax表示全局最大的權重值,這樣可使權重處于0到1區(qū)間,便于計算.
查詢關鍵詞與相應對象詞的編輯距離表示為ed(qt,ot),即qt轉換成ot所需的最小操作數(shù),例如將“NowBalances”轉變?yōu)椤癗ewBalance”,把o換成e然后刪除s需兩步,即編輯距離為2.編輯距離越小說明兩者越相似,文本相關性也越高.
由此可以為關鍵詞文本相關性做出形式化定義,在該式中對編輯距離和權重值兩方面進行綜合考量,如下所示:
(3)
其中,t*表示與查詢關鍵詞編輯距離最小的文本詞,ed(qt*)表示該詞的編輯距離,w(ot*)表示相應權重值,m用來調(diào)整權重與編輯距離兩者之間的偏重比,試驗中初始化為2,以保證其文本相關性值是在0到1區(qū)間.
2.2.2 空間相關性 SMFQ是近鄰查詢算法,要求其查詢范圍內(nèi)檢索到的POI點應與ql位置相近.以往的研究多數(shù)使用歐幾里德距離[11]來表示查詢點ql與對象點ol之間的位置關系,但是隨著POI點數(shù)量的激增其計算花費的時間將成倍增加.
為解決這一問題,本文將二維的經(jīng)緯度信息轉化為一維的莫頓碼,具體的說,就是把空間位置從經(jīng)度和緯度兩個方向均轉化成二進制的編碼,如沿著緯線自西向東方向進行二分,處于上方區(qū)域的編碼為1,下方為0;類似地,沿著經(jīng)線自南向北進行二分,左側區(qū)域編碼為1,右側為0.假設經(jīng)度轉化后的的二進制編碼為0101,緯度的二進制碼為1101,把經(jīng)度二進制碼存到偶數(shù)位,緯度的放在奇數(shù)位,如圖2所示,則產(chǎn)生一組新的編碼10110011,即為莫頓碼.
圖2 莫頓碼格式Fig.2 Morton code format
根據(jù)不同的位置精度需求,可以設置出相應長度的二進制莫頓碼,距離越近其共同前綴碼的長度就越長,因而可以通過字符串匹配替換傳統(tǒng)的歐式距離計算節(jié)省大量的計算資源.其空間相關性公式可以形式化表示為:
(4)
其中,CPL(q,o)表示查詢點位置ql和相應對象ol共同前綴的長度,MCLmax是當前所采用的莫頓碼長度.
綜上,將文本相關性表達式(3)和空間相關性表達式(4)融合得到綜合相關表達式:
(cost)q,o=λ·QT(qt,ot)+(1-λ)·QL(qi,oi).
(5)
λ∈(0,1)用來調(diào)節(jié)文本和空間兩者相關性的偏重比,取值較大則更注重文本相關,反之則更注重空間相關.
本文把表示地理位置的經(jīng)緯度信息轉化為Morton碼,通過比較共同前綴碼的長度近似得到距離的遠近,從而避免歐式距離所需的巨大計算量.Patricia樹是一種前綴樹形結構索引,使其與Morton碼相結合,在該索引結構中,父節(jié)點中存儲的是其子節(jié)點的共同前綴編碼,按規(guī)則“左0右1”放入對應子節(jié)點,以此不斷劃分.因為精度的限制,每一個Morton編碼表示的并不是空間地理的某個具體的點,而是一片矩形區(qū)域,同時其共有前綴碼表示一個更大的區(qū)域.為使查詢結果的文本相關性更好,需對節(jié)點進行改進,在上述Patricia樹的基礎上引入長度位圖LB和相關權重位圖GB,將qt和ot關鍵詞相似計算簡化為位運算;同時節(jié)點內(nèi)還增加存儲該點的查詢范圍MBR;在每個節(jié)點添加倒排文件DI,方便計算關鍵詞的權重.結合圖3的位置關系MPB-tree結構如圖4所示.
表1 相關倒排文本
圖3 空間對應位置關系Fig.3 Spatial position relation
實驗發(fā)現(xiàn),在節(jié)點中存的信息稍多一些,其索引體積就呈倍數(shù)擴大,因此使用指針代替具體信息,每個非葉子節(jié)點存放內(nèi)容為{pos, mask, ptr_l, ptr_r},pos表示該節(jié)點對應編碼在整個編碼中的位置,mask是一組二進制編碼(8位),存儲用來比較的編碼的最高的不同位,ptr_l和ptr_r是兩個指針分別指其左右兩個子節(jié)點.其葉子節(jié)點中的信息為{maininfo, ptr},其中ptr 是指針,指向對應的Morton碼串;maininfo中存放POI點信息,該信息內(nèi)容包含{MBR,LB,GB,DI}.
圖4 MPB-tree索引結構Fig.4 MPB-tree index structure
該索引的建立借鑒二叉樹創(chuàng)建過程,基本思路如下:自根節(jié)點而下,判斷是否為空樹,如果為空,創(chuàng)建一個新節(jié)點;如果不為空,先查詢出適合插入的位置loc,然后計算config(pos,mask),判斷新插入節(jié)點的莫頓碼與loc中的有無差別,如果有,計算出新的pos和mask并重新設置;如果沒有,初始化一個新節(jié)點,新節(jié)點中包含pos、mask及兩個指針,并用相應指針指向下一個該創(chuàng)建的節(jié)點,以此類推構成MPB索引.
為使得到的查詢結果是空間位置上相近的,本文以查詢范圍遞增的方式對周邊區(qū)域進行檢索,與Top-k算法[12]結合檢索出一個初步結果集;之后在此基礎上進行文本相關性計算,最終找出N個最符合要求的結果.
由Morton碼的特點易知:兩個POI點距離越近其共有前綴碼越長,由此可以利用其前綴碼進行近鄰查詢.但是在實際情況中可能存在查詢點ql與對象點ol不完全對應的情況,為防止遺漏,在查詢時不僅使用ql對應的編碼進行檢索,還對編碼進行處理,使得其周圍的8個區(qū)域也能被檢索,算法每循環(huán)一次,都可以在上次的查詢范圍外再增加一層以目前節(jié)點莫頓碼長度表示的范圍,這樣可以充分利用之前的查詢結果,進而提高查詢速率.算法過程如下:
算法1: 獲取初始查詢集,以及對應的空間相關性值
輸入:查詢點ql(lon, lat);MPB結構指針MPBptr;查詢目標數(shù)Num;編碼匹配范圍Range
輸出:含有Num個目標的初始結果Res.queue;
1 Initialization sequence Res.queue;
2 Initialization res.vec,Res.temp;
3 Cente r=MortonEncode(lon, lat,Range);
4 SearchRange=GetOther(Center);
5 do {
6 Search.number=MPBptr.search
(SearchRange, Res.temp,Range);
7 if(Search.number < Num){
8 res.vec=append(Res.temp);
9 Num=Num-Search.number;
10 }
11 else {
12 res.vec=CompSpaSimilarity
(res.vec, Num, Search.number);
13 Res.queue=sort(res.vec, K);
14 break;
15 }
16 Update(SearchRange);
17 } While(i)
18 return Res.queue;
在算法1中,第1行和第2行初始化一個結果隊列及兩個數(shù)組,用來保存查詢結果.第3行到第17行先把經(jīng)緯度數(shù)值轉化成莫頓碼,獲取查詢中心區(qū)域,并獲取與中心查詢區(qū)域相鄰的查詢范圍.使用查詢函數(shù)循環(huán)檢索,得出一定數(shù)量的查詢結果,并將目標信息存入Res.temp.其中第12、13行對查詢到的點進行空間相似度比較,從而找出最接近的top-k個結果,然后存入到結果隊列Res.queue中.循環(huán)執(zhí)行,直至完成任務跳出循環(huán).
為了找出與用戶查詢詞內(nèi)容相關的POI點,需要對算法1中得到的檢索結果進行二次查詢.基本思路是:從編輯距離為0的項開始查詢,對SMKS內(nèi)的所有關鍵詞依次進行比較,統(tǒng)計出Res.queue內(nèi)對應POI點的文本相關值,并存入相應隊列內(nèi),循環(huán)查詢直至遇到以下兩種情形才結束:(1)在綜合評分集合內(nèi)已存在N個(N 算法2 :獲取空間和文本均相關的查詢結果集 輸入:查詢關鍵詞集 SMKS{t1, t2,…,tn}, Res.queue,查詢結果數(shù)N; 輸出 :查詢結果集Result 1 Initialization Search(); 2 Initialization sequence Result; 3 flag=true; ed=0; 4 while(flag){ 5 POIs=Search(ed,Res.queue, SMKS); 6 pre.queue=Process(POIs, pre.queue); 7 ed++; 8 if(ed > limit && pre.queue.size > N) 9 break; } 10 function Process(POIs, pre.queue){ 11 for each(POI in POIs ){ 12 for each(keyword in POI’s Inverted-file) { 13 score+=compere(keyword, POI); 14 pre.queue.append(score,POI) 15 if (pre.queue.size > N) 16 flag=false; 17 return pre.queue; 18 } } 19 } 20 Result=Compare(pre.queue, N); 21 return Result; 在算法2中,第4行到第9行從編輯距離為0的查詢詞開始進行處理,在第6行調(diào)用Process()方法對從算法(1)中得到的POI點逐個比較,第11行到第16行計算出相應查詢詞在其倒排文本中的文本相關程度,得出評分值,并將結果存入對應的位置,然后編輯距離加1進行循環(huán)計算,直至完成任務后跳出循環(huán).第20,21行對所有符合條件的POI點進行綜合相關性計算,返回最相關的結果集. 實驗環(huán)境為:WIN8操作系統(tǒng),CPU為Inter(R) Core(TM) i5 , 運行內(nèi)存為4G.數(shù)據(jù)集通過微博API抓取,每條微博都包含發(fā)布的內(nèi)容和發(fā)布時所處的位置,選取大約2萬條空間數(shù)據(jù),為能更順利地測試,對每條信息內(nèi)容進行過濾,刪除其中的不規(guī)范網(wǎng)絡詞匯及特殊符號等.查詢集由256個不同的關鍵詞構成,查詢地點和查詢詞都是隨機任意選擇,取多次試驗數(shù)據(jù)的平均值作為最終結果. 圖5 不同對象個數(shù)的存儲空間Fig.5 The storage space of the number of different objects 如圖5所示,莫頓碼越長所表示的位置精度越高,但若是莫頓碼過長會使得MPB-Tree索引中節(jié)點數(shù)增多,造成所需存儲空間激增,同時這也使檢索所花費的時間更長,影響查詢效率.然而莫頓碼太短又會使劃分的查詢區(qū)域過大,造成查詢位置失真.根據(jù)實際需要,本文在實驗時將莫頓碼設置為32位. 圖6表示查詢關鍵詞個數(shù)不同時SMFQ算法、精確查詢算法、近似算法之間運行時間的變化.可以看出,隨著查詢詞個數(shù)增加SMFQ算法明顯具有較大優(yōu)勢,因為該算法用字符串匹配的方法替代以往的歐式距離計算方法,檢索速度快,從而獲得較高的查詢效率. 圖6 不同個數(shù)查詢詞的運行時間Fig.6 The running time of different number of query words 圖7 不同查詢結果數(shù)的滿意度狀況Fig.7 Satisfaction degree of different query results 圖7表示用戶對不同查詢結果個數(shù)的滿意度,本文讓多名用戶隨機挑選3個查詢關鍵詞進行查詢,然后對得到的結果進行滿意度評分.首先把查詢結果數(shù)設為10,使用3種查詢算法進行查詢并讓用戶對查詢結果進行評分,可以看出,SMFQ算法獲取的查詢結果明顯評分較高;隨后將查詢結果數(shù)設置為20,SMFQ算法還具有優(yōu)勢但是差距有所降低,隨著查詢結果數(shù)再次增大3者表現(xiàn)基本持平,這是因為SMFQ算法查詢過程中已經(jīng)對檢索到的結果進行排序和剪枝,將最相關的結果優(yōu)先提供給用戶,所以在查詢結果數(shù)較低時表現(xiàn)優(yōu)異.但是當查詢結果數(shù)超過一定范圍后,一些相關性不高的信息也會被檢索到,從而影響評分,但是在相同條件下SMFQ算法滿意度評分仍較其他算法高,說明該算法在查詢準確度上較傳統(tǒng)算法有所提升,且將最相關結果優(yōu)先提供給用戶的方式也更符合用戶的查詢習慣. 本文在RB-Tree索引的基礎上構建出支持多關鍵詞模糊查詢的MPB-Tree索引,并基于該索引設計出一種空間數(shù)據(jù)上的多關鍵詞模糊查詢算法,通過引入莫頓碼、編輯距離,權重值等多種因子,給出相關查詢及剪枝方法,從而實現(xiàn)空間和文本兩方面的相關查詢.由于采用新型的字符匹配方法替代傳統(tǒng)的歐式距離計算來處理位置數(shù)據(jù),從而提高了查詢速度;同時在查詢時充分利用MPB-tree索引中的各種位圖信息,對初步結果集進行剪枝、排序,從而確保最終呈現(xiàn)給用戶的結果集是綜合相關度最高的集合.最后實驗數(shù)據(jù)證明,該算法的查詢效率及用戶滿意度上較其他算法有較大提升. [1] 劉喜平, 萬常選, 劉德喜,等. 空間關鍵詞搜索研究綜述[J]. 軟件學報, 2016,27(2):329-347. [2] YAO B, LI F F, Hadjieleftheriou M.Approximate string search in spatial databases[C]//Proc of the ICDE. Washington: IEEE, 2010: 545-556. [3] 余 艷, 林偉華, 談曉軍. 一種基于R-tree的空間索引方法[J]. 計算機工程, 2010,36(12):30-32. [4] 王金寶, 高 宏, 李建中, 等. RB樹:一種支持空間近似關鍵字查詢的外存索引[J]. 計算機研究與發(fā)展, 2012,49(10):2142-2152. [5] ZHANG D X , CHEN Y M, MONDAL A, et al . Keyword search in spatial databases: towards searching by document[C]//Proceeding of the 2009 IEEE international conference Data Engineering. Washington,DC:IEEE,Computer Society, 2009: 688-699. [6] 易顯天, 徐 展, 郭承軍, 等. 基于Patricia樹的空間索引結構[J]. 計算機工程.2015,41(12):68-74. [7] 徐 明. 基于節(jié)點分裂優(yōu)化的R-樹索引結構[J]. 計算機應用研究, 2016,33(12):3530-3534. [8] 張文勝, 解 騫, 鐘 瑾, 等. 基于八叉樹鄰域分析的光線跟蹤加速算法[J]. 圖學學報, 2015,36(3): 339-344. [9] 劉 義, 景 寧, 陳 犖, 等. Map Reduce框架下基于R-樹的k-近鄰連接算法[J]. 軟件學報,2013(8): 1836-1851. [10] LONG C, WONG R C,WANG K, et al. Collective spatial keyword queries: a distance owner-driven approach[C]//Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data. New York: ACM,2013: 689-700. [11] 李 丹, 朱玲玲, 胡迎松. 基于最小生成樹的多視圖特征點快速匹配算法[J]. 華中科技大學學報(自然科學版),2017,45(1):41-45. [12] 胡 俊, 范佳明. 空間數(shù)據(jù)上的Top-k模糊查詢研究[J].計算機學報, 2012,35(11):2237-2246. Researchonmulti-spatialkeywordFuzzyqueryalgorithmbasedonMPB-Tree ZHANG Suzhi, ZHAO Yanan,YANG Rui (School of Computer and Communication Engineering, Zhengzhou University of Light Industry, Computer Applications and Software, Zhengzhou 450002, China) With the extensive use of smart devices with location function, a large amount of spatial data is produced, and more and more textual information are included in each datum. However the previous algorithm is only a single text word query and difficult to meet the demands of users. To address the above problem, in this paper, a multi-keyword Fuzzy query algorithm is proposed. In this algorithm, the traditional two-dimensional spatial distance calculation is transformed into Morton code matching to speed up the query efficiency, and the fault-tolerant query is supported by combining the Fuzzy algorithm. Experimental results show that the algorithm has better efficiency and accuracy than the previous query algorithm. spatial data; multi-keyword query; Morton codes; Fuzzy query 2017-04-02. 國家自然科學基金項目(616772470);北京市重點實驗室開放課題(BKBD-20171408). *E-mail: 2680732805@qq.com. 10.19603/j.cnki.1000-1190.2017.06.007 1000-1190(2017)06-0765-07 TP392 A4 實驗及性能分析
5 結語