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

張素智， 趙亞楠， 楊 芮

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

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

張素智*， 趙亞楠， 楊 芮

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

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

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

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

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

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

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

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

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

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

1.2 本文工作

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

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

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

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

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

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

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

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

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)對(duì)象p都包含有空間位置信息o和文本信息集合t，如圖1所示.

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

假定多空間關(guān)鍵詞查詢(xún)Q={ql，qT}，ql表示空間位置，qT表示文本詞集合，那么可以存在，ti是用戶(hù)輸入的查詢(xún)?cè)~，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算法支持查詢(xún)?nèi)蒎e(cuò)，即允許查詢(xún)關(guān)鍵詞qt與POI對(duì)象詞ot不完全相同，具體的說(shuō)，本文計(jì)算衡量文本相關(guān)性主要依據(jù)兩個(gè)因素：關(guān)鍵詞權(quán)重和編輯距離.

首先，定義空間數(shù)據(jù)上的多關(guān)鍵詞查詢(xú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是近鄰查詢(xún)，可能僅考量空間位置就可以滿(mǎn)足查詢(xún)要求，但是查詢(xún)結(jié)果的文本相關(guān)性無(wú)法保證，因而篩選出與查詢(xún)?cè)~最相關(guān)的POI點(diǎn)，就需要通過(guò)使用權(quán)重值進(jìn)行衡量，查詢(xún)關(guān)鍵詞qt對(duì)相應(yīng)對(duì)象O的權(quán)重越大說(shuō)明其文本越相關(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)表示在查詢(xún)范圍內(nèi)的POI點(diǎn)中包含有關(guān)鍵詞t的個(gè)數(shù)的倒數(shù).wmax表示全局最大的權(quán)重值，這樣可使權(quán)重處于0到1區(qū)間，便于計(jì)算.

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

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

(3)

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

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

為解決這一問(wèn)題，本文將二維的經(jīng)緯度信息轉(zhuǎn)化為一維的莫頓碼，具體的說(shuō)，就是把空間位置從經(jīng)度和緯度兩個(gè)方向均轉(zhuǎn)化成二進(jìn)制的編碼，如沿著緯線自西向東方向進(jìn)行二分，處于上方區(qū)域的編碼為1，下方為0；類(lèi)似地，沿著經(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)長(zhǎng)度的二進(jìn)制莫頓碼，距離越近其共同前綴碼的長(zhǎng)度就越長(zhǎng)，因而可以通過(guò)字符串匹配替換傳統(tǒng)的歐式距離計(jì)算節(jié)省大量的計(jì)算資源.其空間相關(guān)性公式可以形式化表示為：

(4)

其中，CPL(q，o)表示查詢(xún)點(diǎn)位置ql和相應(yīng)對(duì)象ol共同前綴的長(zhǎng)度，MCLmax是當(dāng)前所采用的莫頓碼長(zhǎ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)用來(lái)調(diào)節(jié)文本和空間兩者相關(guān)性的偏重比，取值較大則更注重文本相關(guān)，反之則更注重空間相關(guān).

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

3.1 MPB-Tree索引

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

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

3.2 基于MPB-tree的模糊查詢(xún)算法

為使得到的查詢(xún)結(jié)果是空間位置上相近的，本文以查詢(xún)范圍遞增的方式對(duì)周邊區(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)距離越近其共有前綴碼越長(zhǎng)，由此可以利用其前綴碼進(jìn)行近鄰查詢(xún).但是在實(shí)際情況中可能存在查詢(xún)點(diǎn)ql與對(duì)象點(diǎn)ol不完全對(duì)應(yīng)的情況，為防止遺漏，在查詢(xún)時(shí)不僅使用ql對(duì)應(yīng)的編碼進(jìn)行檢索，還對(duì)編碼進(jìn)行處理，使得其周?chē)?個(gè)區(qū)域也能被檢索，算法每循環(huán)一次，都可以在上次的查詢(xún)范圍外再增加一層以目前節(jié)點(diǎn)莫頓碼長(zhǎng)度表示的范圍，這樣可以充分利用之前的查詢(xún)結(jié)果，進(jìn)而提高查詢(xún)速率.算法過(guò)程如下：

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

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

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

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

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

輸出 ：查詢(xú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的查詢(xún)?cè)~開(kāi)始進(jìn)行處理，在第6行調(diào)用Process()方法對(duì)從算法(1)中得到的POI點(diǎn)逐個(gè)比較，第11行到第16行計(jì)算出相應(yīng)查詢(xún)?cè)~在其倒排文本中的文本相關(guān)程度，得出評(píng)分值，并將結(jié)果存入對(duì)應(yīng)的位置，然后編輯距離加1進(jìn)行循環(huán)計(jì)算，直至完成任務(wù)后跳出循環(huán).第20，21行對(duì)所有符合條件的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ù)集通過(guò)微博API抓取，每條微博都包含發(fā)布的內(nèi)容和發(fā)布時(shí)所處的位置，選取大約2萬(wàn)條空間數(shù)據(jù)，為能更順利地測(cè)試，對(duì)每條信息內(nèi)容進(jìn)行過(guò)濾，刪除其中的不規(guī)范網(wǎng)絡(luò)詞匯及特殊符號(hào)等.查詢(xún)集由256個(gè)不同的關(guān)鍵詞構(gòu)成，查詢(xún)地點(diǎn)和查詢(xún)?cè)~都是隨機(jī)任意選擇，取多次試驗(yàn)數(shù)據(jù)的平均值作為最終結(jié)果.

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

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

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

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

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

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

5 結(jié)語(yǔ)

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

[1] 劉喜平， 萬(wàn)常選， 劉德喜，等. 空間關(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樹(shù):一種支持空間近似關(guān)鍵字查詢(xú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樹(shù)的空間索引結(jié)構(gòu)[J]. 計(jì)算機(jī)工程.2015，41(12)：68-74．

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

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

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

[12] 胡 俊， 范佳明. 空間數(shù)據(jù)上的Top-k模糊查詢(xún)研究[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.

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

*E-mail: 2680732805@qq.com．

10.19603/j.cnki.1000-1190.2017.06.007

1000-1190(2017)06-0765-07

TP392

A