張素智， 趙亞楠， 楊 芮

(鄭州輕工業(yè)學(xué)院 計(jì)算機(jī)與通信工程學(xué)院， 鄭州 450002)

基于MPB-Tree索引的空間數(shù)據(jù)多關(guān)鍵詞模糊查詢算法研究

張素智*， 趙亞楠， 楊 芮

(鄭州輕工業(yè)學(xué)院 計(jì)算機(jī)與通信工程學(xué)院， 鄭州 450002)

隨著具有定位功能的智能設(shè)備的大量使用，產(chǎn)生出海量的空間數(shù)據(jù)，每條數(shù)據(jù)中包含的信息越來越多，而以往的查詢算法多數(shù)僅對單個(gè)關(guān)鍵詞進(jìn)行查詢，已難以滿足用戶更為個(gè)性化的需求.為此，本文提出一種多空間關(guān)鍵詞模糊查詢算法，在該算法中，將以往的兩維空間距離計(jì)算轉(zhuǎn)化為莫頓碼匹配提升查詢效率，且與模糊查詢算法融合支持查詢的容錯.實(shí)驗(yàn)結(jié)果表明，該算法的效率及準(zhǔn)確性較以往查詢算法有較大提高.

空間數(shù)據(jù)； 多關(guān)鍵詞查詢； 莫頓碼； 模糊查詢

近年來，移動信息產(chǎn)業(yè)發(fā)展迅速，隨著移動終端設(shè)備的普及，產(chǎn)生出海量的數(shù)據(jù)，而這些數(shù)據(jù)都具備地理位置信息和文本內(nèi)容雙重屬性，例如在QQ空間或微博中發(fā)布信息，都可以標(biāo)注出用戶所處的地理位置，因此基于位置的服務(wù)(Location Based Service ， LBS)得到人們的廣泛關(guān)注.

目前的LBS系統(tǒng)把關(guān)鍵詞查詢[1](Spatial Keyword Query)作為處理空間數(shù)據(jù)的主要方式之一，簡單的說，假定空間數(shù)據(jù)集中有多個(gè)興趣點(diǎn)(Points of Interest，POI)，每一個(gè)POI點(diǎn)都包含兩種屬性的信息：文本信息和位置信息，用戶通過輸入關(guān)鍵詞將其作為查詢約束條件，從而檢索得到符合要求的POI點(diǎn).這種處理方式也被各搜索引擎公司采用，但隨著空間數(shù)據(jù)量不斷增長、用戶需求更加個(gè)性、智能移動設(shè)備功能的更加齊全導(dǎo)致以往的查詢算法漸漸無法滿足用戶不斷提高的需求.

在實(shí)際使用中，用戶為了獲得更為豐富的信息，輸入多個(gè)關(guān)鍵詞作為查詢條件是經(jīng)常出現(xiàn)的，但一個(gè)POI點(diǎn)包含的信息有限，有很大幾率不能完全覆蓋用戶所輸入的全部文本內(nèi)容，例如，用戶輸入休閑、購物、飯店就可能需要多個(gè)POI點(diǎn)協(xié)作才能滿足用戶需求.而且現(xiàn)在用戶經(jīng)常用便攜的移動設(shè)備進(jìn)行查詢，例如手機(jī)，其可操作面積較小，有較大幾率輸入不規(guī)范的查詢詞，例如將“星巴克”誤寫為“星吧克”，因此還需要查詢算法具備一定的容錯性.如何從海量的空間數(shù)據(jù)中快速高效地找出對應(yīng)的信息已成為目前的研究熱點(diǎn)之一.

1 相關(guān)研究工作

1.1 研究現(xiàn)狀及分析

空間關(guān)鍵詞查詢目前還處于初步階段，經(jīng)過大量學(xué)者的研究仍取得一定成果：Yao[2]等人建立MHR-Tree索引結(jié)構(gòu)，并提出一種近似匹配查詢算法，將編輯距離引入實(shí)現(xiàn)查詢的容錯，在MHR-Tree內(nèi)各子節(jié)點(diǎn)中增設(shè)簽名對查詢結(jié)果進(jìn)行裁剪，但其質(zhì)量無法保證，使得查詢效果并不理想；Yu[3]等人通過建立MRD-tree索引，允許數(shù)據(jù)入口放到中間節(jié)點(diǎn)處，減少I/O重復(fù)次數(shù)解放出大量計(jì)算資源；Wang[4]等人提出RB-Tree作為索引結(jié)構(gòu)，加入位圖使查詢的穩(wěn)定性和準(zhǔn)確性得到提高；Zhang[5]等人將模糊匹配融入到k近鄰查詢中，使得查詢結(jié)果更為符合需求；Yi[6]等人對Patricia樹索引進(jìn)行改進(jìn)，大幅度提高了查詢速度.

但以上都是以單關(guān)鍵詞為主進(jìn)行研究，對多關(guān)鍵詞查詢關(guān)注較少.而且近似匹配查詢是用編輯距離[7]來衡量查詢詞與POI點(diǎn)的相關(guān)程度，通過閾值對POI點(diǎn)進(jìn)行剪切，然而在實(shí)際使用中發(fā)現(xiàn)查詢詞的文本長度是變化的，長文本需要的閾值可能較大，短文本的則較小，閾值過大或過小都可能導(dǎo)致查詢結(jié)果質(zhì)量不高，設(shè)置出合適閾值的難度很大；其次，隨著空間文本數(shù)據(jù)量的激增，傳統(tǒng)的歐式空間距離方法已難以滿足人們?nèi)找嫣岣叩男枨?，而且以往的空間數(shù)據(jù)關(guān)鍵詞查詢研究多數(shù)僅考慮空間信息的相關(guān)性，對文本相關(guān)考慮不夠深入.

1.2 本文工作

對于以上提出的問題，本文設(shè)計(jì)出一種空間數(shù)據(jù)多關(guān)鍵詞模糊查詢算法SMFQ (Spatial Multi-Keyword Fuzzy Query)，該算法綜合考慮文本相關(guān)性及空間相關(guān)性，融合近似匹配查詢方法，支持模糊查詢；不設(shè)置固定的編譯距離閾值，將其與排序算法相融合找出與查詢詞最相似的k個(gè)關(guān)鍵詞，支持容錯且使算法更為靈活.為滿足用戶日益提高的查詢要求，SMFQ算法需支持：

1) 該算法支持多關(guān)鍵詞的模糊查詢，查詢結(jié)果覆蓋用戶輸入的所有文本內(nèi)容，包含一些文本較長且較復(fù)雜的詞，比如Four Seasons Resort.

2) 得到的查詢結(jié)果應(yīng)該是距離用戶最近的，且不過于分散.

3) 該算法對查詢結(jié)果排序，將最相關(guān)的信息優(yōu)先顯示給用戶.

為此，本文引入編輯距離、關(guān)鍵詞權(quán)重、莫頓碼[8]、空間和文本相關(guān)性[9]等概念，綜上本文的主要貢獻(xiàn)如下：

1) 基于RB-Tree與Patricia索引建立出支持多關(guān)鍵詞近似查詢的索引結(jié)構(gòu)MPB-Tree.

2) 提出并設(shè)計(jì)了空間數(shù)據(jù)上多關(guān)鍵詞模糊查詢算法.

3) 使用真實(shí)數(shù)據(jù)進(jìn)行仿真測試，用實(shí)驗(yàn)結(jié)果證明SMFQ算法具有較高的可行性及查詢效率.

2 相關(guān)工作

2.1 基本概念

在給定的某個(gè)空間文本數(shù)據(jù)集中，設(shè)O表示一組POI點(diǎn)，即O={p1，p2，p3， …，pn}，p={o，t}則有O={(o1，t1.1，t1.2，…,t1.w)……(on，tn.1，…,tn.w)}其中每個(gè)POI點(diǎn)對象p都包含有空間位置信息o和文本信息集合t，如圖1所示.

圖1 空間數(shù)據(jù)內(nèi)在分布關(guān)系Fig.1 Spatial distribution of spatial data

假定多空間關(guān)鍵詞查詢Q={ql，qT}，ql表示空間位置，qT表示文本詞集合，那么可以存在，ti是用戶輸入的查詢詞，ki表示編輯距離上限，ql和ol均用二維空間數(shù)值{lon，lat}表示，其中l(wèi)on和lat分別代表經(jīng)度和緯度.

2.2 相關(guān)算法準(zhǔn)備

2.2.1 文本相關(guān)性 本文中SMFQ算法支持查詢?nèi)蒎e，即允許查詢關(guān)鍵詞qt與POI對象詞ot不完全相同，具體的說，本文計(jì)算衡量文本相關(guān)性主要依據(jù)兩個(gè)因素：關(guān)鍵詞權(quán)重和編輯距離.

首先，定義空間數(shù)據(jù)上的多關(guān)鍵詞查詢集(Spatial Multi-Keyword Set， SMKS)，表示為：

{t1,t2,t3,…,tm},1≤|m|≤|qt|.

(1)

在實(shí)際生活中，不同的POI點(diǎn)擁有相同的詞匯描述的現(xiàn)象是肯定存在的，如圖1所示，有三個(gè)不同的POI點(diǎn)：p3、p5、p6，它們具有一個(gè)相同的文本描述詞“NewBalance”.另外，SMFQ是近鄰查詢，可能僅考量空間位置就可以滿足查詢要求，但是查詢結(jié)果的文本相關(guān)性無法保證，因而篩選出與查詢詞最相關(guān)的POI點(diǎn)，就需要通過使用權(quán)重值進(jìn)行衡量，查詢關(guān)鍵詞qt對相應(yīng)對象O的權(quán)重越大說明其文本越相關(guān)，需被優(yōu)先檢索.

本文計(jì)算權(quán)重的方法是在TF-IDF模型[10]基礎(chǔ)上優(yōu)化后得到的：

(2)

其中，tf(t，oT)表示關(guān)鍵詞t在oT中出現(xiàn)的次數(shù)，次數(shù)與權(quán)重成正比，idf(t，P)表示在查詢范圍內(nèi)的POI點(diǎn)中包含有關(guān)鍵詞t的個(gè)數(shù)的倒數(shù).wmax表示全局最大的權(quán)重值，這樣可使權(quán)重處于0到1區(qū)間，便于計(jì)算.

查詢關(guān)鍵詞與相應(yīng)對象詞的編輯距離表示為ed(qt，ot)，即qt轉(zhuǎn)換成ot所需的最小操作數(shù)，例如將“NowBalances”轉(zhuǎn)變?yōu)椤癗ewBalance”，把o換成e然后刪除s需兩步，即編輯距離為2.編輯距離越小說明兩者越相似，文本相關(guān)性也越高.

由此可以為關(guān)鍵詞文本相關(guān)性做出形式化定義，在該式中對編輯距離和權(quán)重值兩方面進(jìn)行綜合考量，如下所示：

(3)

其中,t*表示與查詢關(guān)鍵詞編輯距離最小的文本詞，ed(qt*)表示該詞的編輯距離，w(ot*)表示相應(yīng)權(quán)重值，m用來調(diào)整權(quán)重與編輯距離兩者之間的偏重比，試驗(yàn)中初始化為2，以保證其文本相關(guān)性值是在0到1區(qū)間.

2.2.2 空間相關(guān)性 SMFQ是近鄰查詢算法，要求其查詢范圍內(nèi)檢索到的POI點(diǎn)應(yīng)與ql位置相近.以往的研究多數(shù)使用歐幾里德距離[11]來表示查詢點(diǎn)ql與對象點(diǎn)ol之間的位置關(guān)系，但是隨著POI點(diǎn)數(shù)量的激增其計(jì)算花費(fèi)的時(shí)間將成倍增加.

為解決這一問題，本文將二維的經(jīng)緯度信息轉(zhuǎn)化為一維的莫頓碼，具體的說，就是把空間位置從經(jīng)度和緯度兩個(gè)方向均轉(zhuǎn)化成二進(jìn)制的編碼，如沿著緯線自西向東方向進(jìn)行二分，處于上方區(qū)域的編碼為1，下方為0；類似地，沿著經(jīng)線自南向北進(jìn)行二分，左側(cè)區(qū)域編碼為1，右側(cè)為0.假設(shè)經(jīng)度轉(zhuǎn)化后的的二進(jìn)制編碼為0101，緯度的二進(jìn)制碼為1101，把經(jīng)度二進(jìn)制碼存到偶數(shù)位，緯度的放在奇數(shù)位，如圖2所示，則產(chǎn)生一組新的編碼10110011，即為莫頓碼.

圖2 莫頓碼格式Fig.2 Morton code format

根據(jù)不同的位置精度需求，可以設(shè)置出相應(yīng)長度的二進(jìn)制莫頓碼，距離越近其共同前綴碼的長度就越長，因而可以通過字符串匹配替換傳統(tǒng)的歐式距離計(jì)算節(jié)省大量的計(jì)算資源.其空間相關(guān)性公式可以形式化表示為：

(4)

其中，CPL(q，o)表示查詢點(diǎn)位置ql和相應(yīng)對象ol共同前綴的長度，MCLmax是當(dāng)前所采用的莫頓碼長度.

綜上，將文本相關(guān)性表達(dá)式(3)和空間相關(guān)性表達(dá)式(4)融合得到綜合相關(guān)表達(dá)式：

(cost)q,o=λ·QT(qt,ot)+(1-λ)·QL(qi,oi).

(5)

λ∈(0，1)用來調(diào)節(jié)文本和空間兩者相關(guān)性的偏重比，取值較大則更注重文本相關(guān)，反之則更注重空間相關(guān).

3 基于MPB-Tree索引的多關(guān)鍵詞查詢算法

3.1 MPB-Tree索引

本文把表示地理位置的經(jīng)緯度信息轉(zhuǎn)化為Morton碼，通過比較共同前綴碼的長度近似得到距離的遠(yuǎn)近，從而避免歐式距離所需的巨大計(jì)算量.Patricia樹是一種前綴樹形結(jié)構(gòu)索引，使其與Morton碼相結(jié)合，在該索引結(jié)構(gòu)中，父節(jié)點(diǎn)中存儲的是其子節(jié)點(diǎn)的共同前綴編碼，按規(guī)則“左0右1”放入對應(yīng)子節(jié)點(diǎn)，以此不斷劃分.因?yàn)榫鹊南拗?，每一個(gè)Morton編碼表示的并不是空間地理的某個(gè)具體的點(diǎn)，而是一片矩形區(qū)域，同時(shí)其共有前綴碼表示一個(gè)更大的區(qū)域.為使查詢結(jié)果的文本相關(guān)性更好，需對節(jié)點(diǎn)進(jìn)行改進(jìn)，在上述Patricia樹的基礎(chǔ)上引入長度位圖LB和相關(guān)權(quán)重位圖GB，將qt和ot關(guān)鍵詞相似計(jì)算簡化為位運(yùn)算；同時(shí)節(jié)點(diǎn)內(nèi)還增加存儲該點(diǎn)的查詢范圍MBR；在每個(gè)節(jié)點(diǎn)添加倒排文件DI，方便計(jì)算關(guān)鍵詞的權(quán)重.結(jié)合圖3的位置關(guān)系MPB-tree結(jié)構(gòu)如圖4所示.

表1 相關(guān)倒排文本

圖3 空間對應(yīng)位置關(guān)系Fig.3 Spatial position relation

實(shí)驗(yàn)發(fā)現(xiàn)，在節(jié)點(diǎn)中存的信息稍多一些，其索引體積就呈倍數(shù)擴(kuò)大，因此使用指針代替具體信息，每個(gè)非葉子節(jié)點(diǎn)存放內(nèi)容為{pos， mask， ptr_l， ptr_r}，pos表示該節(jié)點(diǎn)對應(yīng)編碼在整個(gè)編碼中的位置，mask是一組二進(jìn)制編碼(8位)，存儲用來比較的編碼的最高的不同位，ptr_l和ptr_r是兩個(gè)指針分別指其左右兩個(gè)子節(jié)點(diǎn).其葉子節(jié)點(diǎn)中的信息為{maininfo， ptr}，其中ptr 是指針，指向?qū)?yīng)的Morton碼串；maininfo中存放POI點(diǎn)信息，該信息內(nèi)容包含{MBR，LB，GB，DI}.

圖4 MPB-tree索引結(jié)構(gòu)Fig.4 MPB-tree index structure

該索引的建立借鑒二叉樹創(chuàng)建過程，基本思路如下：自根節(jié)點(diǎn)而下，判斷是否為空樹，如果為空，創(chuàng)建一個(gè)新節(jié)點(diǎn)；如果不為空，先查詢出適合插入的位置loc，然后計(jì)算config(pos，mask)，判斷新插入節(jié)點(diǎn)的莫頓碼與loc中的有無差別，如果有，計(jì)算出新的pos和mask并重新設(shè)置；如果沒有，初始化一個(gè)新節(jié)點(diǎn)，新節(jié)點(diǎn)中包含pos、mask及兩個(gè)指針，并用相應(yīng)指針指向下一個(gè)該創(chuàng)建的節(jié)點(diǎn)，以此類推構(gòu)成MPB索引.

3.2 基于MPB-tree的模糊查詢算法

為使得到的查詢結(jié)果是空間位置上相近的，本文以查詢范圍遞增的方式對周邊區(qū)域進(jìn)行檢索，與Top-k算法[12]結(jié)合檢索出一個(gè)初步結(jié)果集；之后在此基礎(chǔ)上進(jìn)行文本相關(guān)性計(jì)算，最終找出N個(gè)最符合要求的結(jié)果.

由Morton碼的特點(diǎn)易知：兩個(gè)POI點(diǎn)距離越近其共有前綴碼越長，由此可以利用其前綴碼進(jìn)行近鄰查詢.但是在實(shí)際情況中可能存在查詢點(diǎn)ql與對象點(diǎn)ol不完全對應(yīng)的情況，為防止遺漏，在查詢時(shí)不僅使用ql對應(yīng)的編碼進(jìn)行檢索，還對編碼進(jìn)行處理，使得其周圍的8個(gè)區(qū)域也能被檢索，算法每循環(huán)一次，都可以在上次的查詢范圍外再增加一層以目前節(jié)點(diǎn)莫頓碼長度表示的范圍，這樣可以充分利用之前的查詢結(jié)果，進(jìn)而提高查詢速率.算法過程如下：

算法1: 獲取初始查詢集，以及對應(yīng)的空間相關(guān)性值

輸入：查詢點(diǎn)ql(lon， lat)；MPB結(jié)構(gòu)指針MPBptr；查詢目標(biāo)數(shù)Num；編碼匹配范圍Range

輸出：含有Num個(gè)目標(biāo)的初始結(jié)果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行初始化一個(gè)結(jié)果隊(duì)列及兩個(gè)數(shù)組，用來保存查詢結(jié)果.第3行到第17行先把經(jīng)緯度數(shù)值轉(zhuǎn)化成莫頓碼，獲取查詢中心區(qū)域，并獲取與中心查詢區(qū)域相鄰的查詢范圍.使用查詢函數(shù)循環(huán)檢索，得出一定數(shù)量的查詢結(jié)果，并將目標(biāo)信息存入Res.temp.其中第12、13行對查詢到的點(diǎn)進(jìn)行空間相似度比較，從而找出最接近的top-k個(gè)結(jié)果，然后存入到結(jié)果隊(duì)列Res.queue中.循環(huán)執(zhí)行，直至完成任務(wù)跳出循環(huán).

為了找出與用戶查詢詞內(nèi)容相關(guān)的POI點(diǎn)，需要對算法1中得到的檢索結(jié)果進(jìn)行二次查詢.基本思路是：從編輯距離為0的項(xiàng)開始查詢，對SMKS內(nèi)的所有關(guān)鍵詞依次進(jìn)行比較，統(tǒng)計(jì)出Res.queue內(nèi)對應(yīng)POI點(diǎn)的文本相關(guān)值，并存入相應(yīng)隊(duì)列內(nèi)，循環(huán)查詢直至遇到以下兩種情形才結(jié)束：(1)在綜合評分集合內(nèi)已存在N個(gè)(N

算法2 ：獲取空間和文本均相關(guān)的查詢結(jié)果集

輸入：查詢關(guān)鍵詞集 SMKS{t1， t2，…，tn}， Res.queue，查詢結(jié)果數(shù)N;

輸出 ：查詢結(jié)果集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的查詢詞開始進(jìn)行處理，在第6行調(diào)用Process()方法對從算法(1)中得到的POI點(diǎn)逐個(gè)比較，第11行到第16行計(jì)算出相應(yīng)查詢詞在其倒排文本中的文本相關(guān)程度，得出評分值，并將結(jié)果存入對應(yīng)的位置，然后編輯距離加1進(jìn)行循環(huán)計(jì)算，直至完成任務(wù)后跳出循環(huán).第20，21行對所有符合條件的POI點(diǎn)進(jìn)行綜合相關(guān)性計(jì)算，返回最相關(guān)的結(jié)果集.

4 實(shí)驗(yàn)及性能分析

實(shí)驗(yàn)環(huán)境為：WIN8操作系統(tǒng)，CPU為Inter(R) Core(TM) i5 ， 運(yùn)行內(nèi)存為4G.數(shù)據(jù)集通過微博API抓取，每條微博都包含發(fā)布的內(nèi)容和發(fā)布時(shí)所處的位置，選取大約2萬條空間數(shù)據(jù)，為能更順利地測試，對每條信息內(nèi)容進(jìn)行過濾，刪除其中的不規(guī)范網(wǎng)絡(luò)詞匯及特殊符號等.查詢集由256個(gè)不同的關(guān)鍵詞構(gòu)成，查詢地點(diǎn)和查詢詞都是隨機(jī)任意選擇，取多次試驗(yàn)數(shù)據(jù)的平均值作為最終結(jié)果.

圖5 不同對象個(gè)數(shù)的存儲空間Fig.5 The storage space of the number of different objects

如圖5所示，莫頓碼越長所表示的位置精度越高，但若是莫頓碼過長會使得MPB-Tree索引中節(jié)點(diǎn)數(shù)增多，造成所需存儲空間激增，同時(shí)這也使檢索所花費(fèi)的時(shí)間更長，影響查詢效率.然而莫頓碼太短又會使劃分的查詢區(qū)域過大，造成查詢位置失真.根據(jù)實(shí)際需要，本文在實(shí)驗(yàn)時(shí)將莫頓碼設(shè)置為32位.

圖6表示查詢關(guān)鍵詞個(gè)數(shù)不同時(shí)SMFQ算法、精確查詢算法、近似算法之間運(yùn)行時(shí)間的變化.可以看出，隨著查詢詞個(gè)數(shù)增加SMFQ算法明顯具有較大優(yōu)勢，因?yàn)樵撍惴ㄓ米址ヅ涞姆椒ㄌ娲酝臍W式距離計(jì)算方法，檢索速度快，從而獲得較高的查詢效率.

圖6 不同個(gè)數(shù)查詢詞的運(yùn)行時(shí)間Fig.6 The running time of different number of query words

圖7 不同查詢結(jié)果數(shù)的滿意度狀況Fig.7 Satisfaction degree of different query results

圖7表示用戶對不同查詢結(jié)果個(gè)數(shù)的滿意度，本文讓多名用戶隨機(jī)挑選3個(gè)查詢關(guān)鍵詞進(jìn)行查詢，然后對得到的結(jié)果進(jìn)行滿意度評分.首先把查詢結(jié)果數(shù)設(shè)為10，使用3種查詢算法進(jìn)行查詢并讓用戶對查詢結(jié)果進(jìn)行評分，可以看出，SMFQ算法獲取的查詢結(jié)果明顯評分較高；隨后將查詢結(jié)果數(shù)設(shè)置為20，SMFQ算法還具有優(yōu)勢但是差距有所降低，隨著查詢結(jié)果數(shù)再次增大3者表現(xiàn)基本持平，這是因?yàn)镾MFQ算法查詢過程中已經(jīng)對檢索到的結(jié)果進(jìn)行排序和剪枝，將最相關(guān)的結(jié)果優(yōu)先提供給用戶，所以在查詢結(jié)果數(shù)較低時(shí)表現(xiàn)優(yōu)異.但是當(dāng)查詢結(jié)果數(shù)超過一定范圍后，一些相關(guān)性不高的信息也會被檢索到，從而影響評分，但是在相同條件下SMFQ算法滿意度評分仍較其他算法高，說明該算法在查詢準(zhǔn)確度上較傳統(tǒng)算法有所提升，且將最相關(guān)結(jié)果優(yōu)先提供給用戶的方式也更符合用戶的查詢習(xí)慣.

5 結(jié)語

本文在RB-Tree索引的基礎(chǔ)上構(gòu)建出支持多關(guān)鍵詞模糊查詢的MPB-Tree索引，并基于該索引設(shè)計(jì)出一種空間數(shù)據(jù)上的多關(guān)鍵詞模糊查詢算法，通過引入莫頓碼、編輯距離，權(quán)重值等多種因子，給出相關(guān)查詢及剪枝方法，從而實(shí)現(xiàn)空間和文本兩方面的相關(guān)查詢.由于采用新型的字符匹配方法替代傳統(tǒng)的歐式距離計(jì)算來處理位置數(shù)據(jù)，從而提高了查詢速度；同時(shí)在查詢時(shí)充分利用MPB-tree索引中的各種位圖信息，對初步結(jié)果集進(jìn)行剪枝、排序，從而確保最終呈現(xiàn)給用戶的結(jié)果集是綜合相關(guān)度最高的集合.最后實(shí)驗(yàn)數(shù)據(jù)證明，該算法的查詢效率及用戶滿意度上較其他算法有較大提升.

[1] 劉喜平， 萬常選， 劉德喜，等. 空間關(guān)鍵詞搜索研究綜述[J]. 軟件學(xué)報(bào)， 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]. 計(jì)算機(jī)工程， 2010，36(12):30-32．

[4] 王金寶， 高 宏， 李建中， 等. RB樹:一種支持空間近似關(guān)鍵字查詢的外存索引[J]. 計(jì)算機(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樹的空間索引結(jié)構(gòu)[J]. 計(jì)算機(jī)工程.2015，41(12)：68-74．

[7] 徐 明. 基于節(jié)點(diǎn)分裂優(yōu)化的R-樹索引結(jié)構(gòu)[J]. 計(jì)算機(jī)應(yīng)用研究， 2016，33(12):3530-3534．

[8] 張文勝， 解 騫， 鐘 瑾， 等. 基于八叉樹鄰域分析的光線跟蹤加速算法[J]. 圖學(xué)學(xué)報(bào)， 2015，36(3): 339-344．

[9] 劉 義， 景 寧， 陳 犖， 等. Map Reduce框架下基于R-樹的k-近鄰連接算法[J]. 軟件學(xué)報(bào)，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] 李 丹， 朱玲玲， 胡迎松. 基于最小生成樹的多視圖特征點(diǎn)快速匹配算法[J]. 華中科技大學(xué)學(xué)報(bào)(自然科學(xué)版)，2017，45(1):41-45．

[12] 胡 俊， 范佳明. 空間數(shù)據(jù)上的Top-k模糊查詢研究[J].計(jì)算機(jī)學(xué)報(bào)， 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.

國家自然科學(xué)基金項(xiàng)目(616772470)；北京市重點(diǎn)實(shí)驗(yàn)室開放課題(BKBD-20171408).

*E-mail: 2680732805@qq.com．

10.19603/j.cnki.1000-1190.2017.06.007

1000-1190(2017)06-0765-07

TP392

A