基于線性四分樹(shù)的空間關(guān)鍵詞最近鄰查詢(xún)方法研究

于啟迪 吳 雷,2 馬 昂

1(石家莊鐵道大學(xué)經(jīng)濟(jì)管理學(xué)院 河北 石家莊 050043)2(燕山大學(xué)信息科學(xué)與工程學(xué)院 河北 秦皇島 066004)

0 引 言

隨著社會(huì)的飛速發(fā)展和科技的不斷進(jìn)步，信息在人們的生活中發(fā)揮著越來(lái)越重要的作用，人們對(duì)信息的需求一直在不斷地增加。尤其隨著互聯(lián)網(wǎng)的高速發(fā)展，智能手機(jī)和移動(dòng)終端的廣泛普及，越來(lái)越多的應(yīng)用中出現(xiàn)了地理位置信息與文本信息的相互交融。人們?cè)诿刻斓墓ぷ骱蛯W(xué)習(xí)生活中，不斷地與這些應(yīng)用進(jìn)行著“交互”?？臻g文本信息已經(jīng)成為人們生活必不可少的一部分，“我現(xiàn)在在哪？附近都有什么景點(diǎn)？我怎么去火車(chē)站？”等問(wèn)題已經(jīng)成為人們?nèi)粘９ぷ骱蜕畹囊徊糠?，并逐步發(fā)展成為可以提高人們生活質(zhì)量的基本信息服務(wù)模式，基于位置的服務(wù)便應(yīng)運(yùn)而生。

基于位置的服務(wù)LBS(Location Based Service)，核心功能就是基于用戶(hù)當(dāng)前的位置信息，為用戶(hù)提供相關(guān)的服務(wù)[1]。例如人們使用大眾點(diǎn)評(píng)搜索附近的餐館，或使用百度地圖查找附近的景點(diǎn)。

作為位置服務(wù)的一種重要應(yīng)用，同時(shí)滿足空間位置和文本信息的查詢(xún)即空間關(guān)鍵詞查詢(xún)(Spatial keyword query)得到了學(xué)術(shù)界和工業(yè)界的廣泛關(guān)注。所謂空間關(guān)鍵詞查詢(xún)，即根據(jù)給定的用戶(hù)的地理位置以及提出的關(guān)鍵詞，在空間文本對(duì)象中查找符合用戶(hù)要求的對(duì)象。在空間關(guān)鍵詞查詢(xún)領(lǐng)域中一種非常重要的操作就是Top-k查詢(xún)[2-3]，即根據(jù)給定的評(píng)分函數(shù)在數(shù)據(jù)集中返回得分最高的k個(gè)對(duì)象[4]。

空間關(guān)鍵詞查詢(xún)中針對(duì)關(guān)鍵詞匹配方面的文本約束分為完全匹配和部分匹配兩種[5]。其中完全匹配[6-9]，要求查詢(xún)返回的空間文本對(duì)象必須全部滿足用戶(hù)的查詢(xún)關(guān)鍵詞要求。而部分匹配[10-13]，要求返回的空間文本對(duì)象具有的關(guān)鍵詞與用戶(hù)的查詢(xún)關(guān)鍵詞部分匹配即可。以圖1為例，該區(qū)域中有6個(gè)空間文本對(duì)象，每個(gè)對(duì)象的地理位置和其具有的關(guān)鍵詞及每個(gè)關(guān)鍵詞所對(duì)應(yīng)的權(quán)重(即關(guān)鍵詞所占對(duì)象中的文本信息的重要程度)已知。例如，對(duì)象o1是一個(gè)專(zhuān)業(yè)游泳館，對(duì)象o6是一個(gè)水上樂(lè)園。假設(shè)用戶(hù)在查詢(xún)點(diǎn)q想要查找一家游泳館并且可以喝一杯果汁，(即q.T={swim，juice})?；谕耆ヅ湔Z(yǔ)義要求的查詢(xún)返回的結(jié)果為對(duì)象o3和o6，而基于部分匹配的語(yǔ)義要求查詢(xún)返回的結(jié)果為對(duì)象o1和o2。這是由于雖然o1和o2均部分滿足查詢(xún)關(guān)鍵詞要求，但o1和o2對(duì)應(yīng)于查詢(xún)文本信息所得的權(quán)重大于o3和o6對(duì)應(yīng)于查詢(xún)文本所得的權(quán)重，且對(duì)象o1和o2與用戶(hù)距離更近。此時(shí)如果用戶(hù)追求的是有品質(zhì)的生活(如：想找一家高品質(zhì)的游泳館，只是順便喝杯果汁)，那基于文本信息部分匹配返回的結(jié)果更能滿足用戶(hù)的要求且距離更近。

圖1 一個(gè)查詢(xún)的例子

隨著信息技術(shù)的發(fā)展，數(shù)據(jù)無(wú)論在內(nèi)容上或是形式上都呈現(xiàn)出多樣性和復(fù)雜性，如何存儲(chǔ)、管理這些數(shù)據(jù)成為該領(lǐng)域的難點(diǎn)，如何從大量數(shù)據(jù)中返回符合用戶(hù)要求的結(jié)果，更給研究者們提出了新的挑戰(zhàn)。眾所周知，建立高效的空間索引能夠提高空間數(shù)據(jù)的查詢(xún)效率，有效的查詢(xún)算法能有效地避免冗余計(jì)算，實(shí)現(xiàn)提前終止。在Top-k 查詢(xún)問(wèn)題上，還需要排序策略。所以，索引技術(shù)與查詢(xún)算法的結(jié)合是解決快速查詢(xún)的關(guān)鍵。

為了解決空間文本對(duì)象上的k最近鄰查詢(xún)問(wèn)題，研究者們提出了許多索引技術(shù)和查詢(xún)算法[5]?，F(xiàn)有文獻(xiàn)中提出了兩種索引結(jié)構(gòu)IR-tree[14]和IR2-tree[15]。在IR-tree索引中，根據(jù)所有對(duì)象的地理位置建立一棵R樹(shù)，每個(gè)結(jié)點(diǎn)都關(guān)聯(lián)一個(gè)倒排文件，因此可以在Top-k查詢(xún)中立即消除不包含任何查詢(xún)關(guān)鍵詞的對(duì)象。當(dāng)關(guān)鍵詞數(shù)量較少時(shí)，IR-tree技術(shù)是有效的。然而，當(dāng)查詢(xún)關(guān)鍵詞的數(shù)量增加時(shí)，IR-tree的性能會(huì)顯著降低；此外，由于只建立了一棵樹(shù)，樹(shù)的維護(hù)成本較高。IR2-tree技術(shù)通過(guò)利用簽名技術(shù)即根據(jù)查看結(jié)點(diǎn)包含的對(duì)象中出現(xiàn)的關(guān)鍵詞的來(lái)決定是否進(jìn)一步探索結(jié)點(diǎn)。然而，所有的空間文本對(duì)象也依然被組織在一個(gè)單一的R樹(shù)中，當(dāng)數(shù)據(jù)量增大時(shí)會(huì)顯著影響搜索算法的性能[16]。為解決上述不足，文獻(xiàn)[16]提出了倒排線性四分樹(shù)索引結(jié)構(gòu)IL-Quadtree，這種索引結(jié)構(gòu)針對(duì)每個(gè)關(guān)鍵詞都建立一棵線性四分樹(shù)。當(dāng)用戶(hù)進(jìn)行查詢(xún)時(shí)，直接訪問(wèn)該查詢(xún)關(guān)鍵詞對(duì)應(yīng)的線性四分樹(shù)即可，直接忽略了那些不包含查詢(xún)關(guān)鍵詞的對(duì)象。然而，該工作僅關(guān)注了空間文本對(duì)象的在語(yǔ)義方面的完全匹配。

本文綜合考慮用戶(hù)的地理位置和查詢(xún)文本信息與區(qū)域中的空間文本對(duì)象的信息匹配情況，對(duì)滿足查詢(xún)條件的空間文本對(duì)象進(jìn)行排序，最終返回前k個(gè)對(duì)象。本文應(yīng)用線性四分樹(shù)提出了一種基于自適應(yīng)虛擬四分樹(shù)的Top-k查詢(xún)算法Avqt，該算法可同時(shí)支持語(yǔ)義上的完全匹配和部分匹配。其中，通過(guò)計(jì)算被查詢(xún)區(qū)域與用戶(hù)所提出關(guān)鍵詞的文本相似性，較早地將不滿足查詢(xún)要求的結(jié)點(diǎn)剪枝。

綜上所述,本文貢獻(xiàn)總結(jié)如下：

1) 從四分樹(shù)本身層層遞進(jìn)四分的特點(diǎn)出發(fā)，提出了一種無(wú)需計(jì)算所有區(qū)域，基于自適應(yīng)虛擬四分樹(shù)的支持高效Top-k空間關(guān)鍵詞查詢(xún)算法Avqt。

2) 在真實(shí)數(shù)據(jù)集上進(jìn)行了大量的實(shí)驗(yàn)，驗(yàn)證了提出的算法在Top-k查詢(xún)中的有效性和高效性。

1 相關(guān)工作

空間文本對(duì)象指既有地理位置信息，又有文本信息的對(duì)象。空間關(guān)鍵詞查詢(xún)指根據(jù)給定用戶(hù)的地理位置以及提出的關(guān)鍵詞，在空間文本對(duì)象中查找符合用戶(hù)要求的對(duì)象。其中，Top-k空間關(guān)鍵詞查詢(xún)成為研究的熱點(diǎn)。2008年，文獻(xiàn)[15]提出了一種新的解決Top-k空間關(guān)鍵詞查詢(xún)問(wèn)題的索引結(jié)構(gòu)——IR2樹(shù)。IR2樹(shù)是將R樹(shù)和簽名文件相結(jié)合，即將R樹(shù)上的每個(gè)結(jié)點(diǎn)都存放一個(gè)簽名文件，該簽名文件包括了該結(jié)點(diǎn)的后代所包含的對(duì)象相關(guān)信息。在查詢(xún)過(guò)程中，如果該結(jié)點(diǎn)的簽名文件中確認(rèn)沒(méi)有包含全部查詢(xún)關(guān)鍵字，則不需要進(jìn)一步探索該節(jié)點(diǎn)，從而在一定程度上提高了剪枝效率。2009年，文獻(xiàn)[17]首次提出了IR樹(shù)，一種新型的結(jié)合倒排文件和R樹(shù)的索引結(jié)構(gòu)，并且在IR樹(shù)的基礎(chǔ)上相繼發(fā)展了DIR樹(shù)、CIR樹(shù)，進(jìn)一步提高了索引效率。2011年，文獻(xiàn)[18]為提高Top-k空間關(guān)鍵詞的查詢(xún)性能提出來(lái)另一種形式的混合索引結(jié)構(gòu)，稱(chēng)為S2I索引。S2I將關(guān)鍵詞按出現(xiàn)的頻率進(jìn)行劃分，對(duì)頻繁出現(xiàn)和不頻繁出現(xiàn)的關(guān)鍵詞區(qū)別對(duì)待。對(duì)于頻繁的關(guān)鍵詞S2I為每個(gè)關(guān)鍵詞建立一棵聚集R樹(shù)，稱(chēng)為aR樹(shù)，對(duì)不頻繁的關(guān)鍵詞，將與其相關(guān)的對(duì)象信息保存在一個(gè)塊文件中。2013年，文獻(xiàn)[16]提出了一種倒排線性四分樹(shù)索引結(jié)構(gòu)IL-Quadtree，針對(duì)每個(gè)關(guān)鍵詞都建立一棵線性四分樹(shù)。當(dāng)用戶(hù)進(jìn)行查詢(xún)時(shí)，直接訪問(wèn)查詢(xún)關(guān)鍵詞對(duì)應(yīng)的線性四分樹(shù)，忽略了那些不包含目標(biāo)關(guān)鍵詞的對(duì)象。

現(xiàn)有文獻(xiàn)已經(jīng)提出了各種類(lèi)型的空間關(guān)鍵詞查詢(xún)。這些相關(guān)作品可以從兩個(gè)方面進(jìn)行分類(lèi)：1) 查詢(xún)是否包含空間約束；2) 關(guān)鍵詞語(yǔ)義使用完全匹配還是部分匹配。

對(duì)于具有空間約束的研究，要求返回的空間文本對(duì)象的位置與查詢(xún)區(qū)域相交或包含在查詢(xún)區(qū)域[19-24]。其中，查詢(xún)處理可分為兩種：空間優(yōu)先或文本優(yōu)先?？臻g優(yōu)先索引是先將空間進(jìn)行劃分建立索引樹(shù)，然后在每個(gè)結(jié)點(diǎn)中存放有關(guān)的關(guān)鍵詞的信息。當(dāng)數(shù)據(jù)量巨大的時(shí)候，這類(lèi)索引的效率會(huì)明顯下降，并且剪枝困難，影響算法的效率[26]。另一類(lèi)是文本優(yōu)先的索引，包括I3[26]、S2I[27]等。這類(lèi)索引針對(duì)每個(gè)關(guān)鍵詞建一棵樹(shù)，由于并不是所有的結(jié)點(diǎn)都存放關(guān)鍵詞的信息，因此可通過(guò)檢索不同樹(shù)的相同結(jié)點(diǎn)，檢驗(yàn)該區(qū)域是否包含所有的關(guān)鍵詞，從而實(shí)現(xiàn)剪枝。

本文研究?jī)?nèi)容，從關(guān)鍵詞語(yǔ)義來(lái)說(shuō)屬于部分匹配語(yǔ)義。從空間約束上來(lái)說(shuō)屬于文本優(yōu)先索引。從索引結(jié)構(gòu)來(lái)說(shuō)本文采用倒排線性四分樹(shù)索引結(jié)構(gòu)，它結(jié)合了IR-Tree和四分樹(shù)索引的優(yōu)點(diǎn)，為每個(gè)關(guān)鍵詞建立一棵B+tree樹(shù)，這棵樹(shù)中只包含滿足該關(guān)鍵詞的對(duì)象，不包含該關(guān)鍵詞的對(duì)象便會(huì)被去除。運(yùn)用線性四分樹(shù)的四分的思想，提出虛擬四分樹(shù)，對(duì)不滿足條件的區(qū)域不再進(jìn)行四分，從而極大地減少了數(shù)據(jù)訪問(wèn)量。另一方面，查詢(xún)只訪問(wèn)具有用戶(hù)查詢(xún)關(guān)鍵詞的空間文本對(duì)象，節(jié)省了索引占據(jù)的空間，并且索引將位置相近的對(duì)象聚合在磁盤(pán)中，減少了I/O次數(shù)，提高索引效率[16]。

2 問(wèn)題的形式化描述

設(shè)空間數(shù)據(jù)庫(kù)中一組空間文本對(duì)象集合O可表示為O={o1,o2,…,on}。其中，對(duì)于任意一個(gè)o∈O均包含空間位置信息l和文本信息T，表示為o=(l,T)。具體來(lái)說(shuō)，o.l表示對(duì)象o在二維空間內(nèi)的地理位置點(diǎn)；o.T={t1,t2,…,tn}表示一組關(guān)鍵詞的集合。用戶(hù)提出的查詢(xún)記為q，其中q中包含用戶(hù)的查詢(xún)位置和一系列查詢(xún)關(guān)鍵詞集合以及查詢(xún)要求返回的結(jié)果個(gè)數(shù)k，記為q=(q.l,q.T,q.k)。任意兩個(gè)空間文本對(duì)象的相似性包括空間相似性和文本相似性?xún)蓚€(gè)方面。

定義1空間相似性。兩個(gè)對(duì)象之間的空間相近程度用空間相似性表示，記為fs(q,o)。文本采用歐幾里得距離來(lái)衡量查詢(xún)對(duì)象與空間文本對(duì)象之間的空間相似性，其中用ζ(q.l,o.l)表示查詢(xún)對(duì)象和空間文本對(duì)象之間的空間距離。設(shè)ζmax表示空間中任意兩點(diǎn)的最遠(yuǎn)距離，其目的是將距離規(guī)范到區(qū)間[0,1]。此時(shí)，查詢(xún)對(duì)象q與對(duì)象o的空間相似性定義為：

(1)

對(duì)象間空間距離的大小直接影響空間相似性。由式(1)可知，兩個(gè)對(duì)象距離越遠(yuǎn)，即ζ(q.l,o.l)越大，其空間相似程度越低。因此fs(q,o)的值越小，兩對(duì)象間的空間相似性越大。此外，若將對(duì)象o擴(kuò)展為一個(gè)區(qū)域R，則該區(qū)域R與查詢(xún)對(duì)象q的距離定義為q到該區(qū)域的最近距離。

(2)

式中：maxP為整個(gè)區(qū)域中每個(gè)關(guān)鍵詞的最大關(guān)鍵詞權(quán)重加和，其目的是將權(quán)重規(guī)范到區(qū)間[0,1]。類(lèi)似的，若對(duì)象o擴(kuò)大為一個(gè)區(qū)域R，則該區(qū)域包含的關(guān)鍵詞是所有被包含在區(qū)域R中的空間文本對(duì)象所包含的關(guān)鍵詞的并，每個(gè)關(guān)鍵詞的權(quán)重是該關(guān)鍵詞在該區(qū)域內(nèi)的最大權(quán)重。由式(2)可知ft(q,o)值越小，查詢(xún)對(duì)象q與空間文本對(duì)象o的文本相似性越大。

由于本文在計(jì)算對(duì)象間文本相似性時(shí)使用的權(quán)重是對(duì)象中所有滿足查詢(xún)q的關(guān)鍵詞的權(quán)重加和，式(2)中的文本相似性的計(jì)算實(shí)現(xiàn)了對(duì)OR語(yǔ)義的支持。此外，本文對(duì)OR語(yǔ)義的支持還體現(xiàn)在查詢(xún)算法中。

定義3空間文本相似性。任意兩個(gè)空間文本對(duì)象的相似性為同時(shí)考慮空間距離和文本內(nèi)容的相似程度。結(jié)合式(1)和式(2)，查詢(xún)對(duì)象q與空間文本對(duì)象o之間的空間文本相似性定義為：

f(q,o)=αfs(q,o)+(1-α)ft(q,o)

(3)

式中：α是一個(gè)固定值參數(shù)，用來(lái)調(diào)節(jié)兩對(duì)象間空間距離和文本相似性之間的相對(duì)重要程度，且α∈[0，1]。此時(shí)，f(q,o)的值越小，對(duì)象q與o的相似性就越大。

定理兩個(gè)空間文本對(duì)象o1、o2。如果ζ(q.l,o1.l)≤ζ(q.l,o2.l)，且對(duì)于任意一個(gè)t∈q.T，滿足wt,o1≥wt,o2，則有f(q,o1)≤(q,o2)。

直觀地來(lái)講，定理反映為與查詢(xún)對(duì)象q部分匹配的兩個(gè)對(duì)象，在空間上，其中一個(gè)對(duì)象比另一個(gè)對(duì)象距離q更近，同時(shí)該對(duì)象的每個(gè)關(guān)鍵詞的權(quán)重都比另一個(gè)對(duì)象更高時(shí)，那么該對(duì)象較另一個(gè)對(duì)象與查詢(xún)q更匹配。該定理的證明較直觀，具體證明過(guò)程省略。

根據(jù)定理可得出以下推論：

推論設(shè)一個(gè)空間文本對(duì)象集合R，用覆蓋這些對(duì)象的最小邊界矩形表示其位置，R的關(guān)鍵詞是R中所有對(duì)象具有的關(guān)鍵詞的并，記為R.T={o1.t∪o2.t∪…∪on.t}，R中關(guān)鍵詞的權(quán)重由關(guān)鍵詞在R中所有對(duì)象中的權(quán)值最大值加和表示，記為R.wt∈R.T=∑o∈Rmax(wt,o)。因此對(duì)于區(qū)域R中任意一個(gè)對(duì)象o，均有f(q,R)≤(q,o)。

證明對(duì)象o在R的覆蓋中，由推論可知，對(duì)象o到查詢(xún)點(diǎn)q的距離小于等于空間文本對(duì)象集合R到查詢(xún)點(diǎn)的距離，即ζ(q.l,R.l)≤ζ(q.l,o.l)，所以由式(1)可知fs(q,R)≤fs(q,o)。由于對(duì)象o中的關(guān)鍵詞是空間文本對(duì)象集合R中關(guān)鍵詞的一部分，且空間文本對(duì)象集合R的文本權(quán)重是其包含的所有滿足查詢(xún)關(guān)鍵詞的文本權(quán)重最大值的和，所以由式(2)可知ft(q,R)≤ft(q,o)。綜合以上運(yùn)用式(3)，則f(q,R)≤(q,o)。

3 部分匹配空間關(guān)鍵詞查詢(xún)算法

本文的研究目標(biāo)是要運(yùn)用倒排線性四分樹(shù)(詳見(jiàn)3.1節(jié))，從空間文本對(duì)象組成的集合O中，尋找與查詢(xún)q空間文本相似性最高的k個(gè)對(duì)象，即k最鄰近查詢(xún)。

3.1 倒排線性四分樹(shù) IL-quadtree

本文采用倒排四分樹(shù)索引所有的空間文本對(duì)象。具體來(lái)講，IL-quadtree是倒排文件和線性四分樹(shù)的結(jié)合，對(duì)于每個(gè)關(guān)鍵詞，維護(hù)一棵線性四分樹(shù)，四分樹(shù)中索引了所有包含該關(guān)鍵詞的對(duì)象。圖2顯示了圖1中包含關(guān)鍵詞的對(duì)象所對(duì)應(yīng)的倒排線性四分樹(shù)。

圖2 聚集倒排線性四分樹(shù)

這些結(jié)點(diǎn)所在空間遵循一定的規(guī)則進(jìn)行編碼，最常用的地址碼是四進(jìn)制的或十進(jìn)制的Morton碼，本文采用四進(jìn)制的Morton編碼。文獻(xiàn)[28]對(duì)Morton編碼方法進(jìn)行了詳細(xì)說(shuō)明，這里進(jìn)行簡(jiǎn)要介紹。首先設(shè)定好區(qū)域要?jiǎng)澐值淖畲笊疃萺，每個(gè)區(qū)域單元的碼值可由深度計(jì)算，則一個(gè)區(qū)域最多可被劃分為2r×2r個(gè)區(qū)域單元。在空間的某一深度h(h≤r)下區(qū)域空間被四等分。四等分的區(qū)域根據(jù)一個(gè)標(biāo)簽方案進(jìn)行標(biāo)記，其中區(qū)域四個(gè)方向SW、SE、NW、NE分別標(biāo)記為0、1、2、3，如圖3所示。Morton碼的左邊第一位數(shù)字表示區(qū)域在深度為1時(shí)的所處的方向和位置，左邊第二位數(shù)字是深度為2時(shí)區(qū)域所處的方向和位置，依次類(lèi)推。因此，Morton碼始終以數(shù)字r為準(zhǔn)，所劃分深度為h

圖3 空間中四個(gè)區(qū)域的劃分

利用上述編碼方式，對(duì)空間中的四個(gè)區(qū)域SW、SE、NW、NE進(jìn)行自頂向下的自適應(yīng)的四等分。自適應(yīng)的含義是對(duì)每一個(gè)象限都進(jìn)行四等分，直至該區(qū)域僅包含一個(gè)對(duì)象或劃分達(dá)到最大劃分深度。因此，每個(gè)區(qū)域的劃分深度不盡相同，劃分深度依據(jù)該象限包含的對(duì)象數(shù)進(jìn)行自適應(yīng)的調(diào)節(jié)。圖4是根據(jù)上述編碼方式，將圖1的空間區(qū)域進(jìn)行劃分(r=3)。劃分后，每個(gè)區(qū)域的編碼如圖4所示。

圖4 區(qū)域編碼

依據(jù)上述編碼規(guī)則，空間中的所有單元(cell)均可用四進(jìn)制串表示。進(jìn)而，可以采用最常用的B+tree存儲(chǔ)所有非空單元，極大程度上減少存儲(chǔ)空間。每個(gè)關(guān)鍵詞均對(duì)應(yīng)著一棵B+tree。其中每個(gè)非葉子結(jié)點(diǎn)均存儲(chǔ)帶有層次標(biāo)號(hào)的Morton碼值和該單元下包含的對(duì)象中關(guān)于該特定關(guān)鍵詞的權(quán)重最大值。每個(gè)葉子結(jié)點(diǎn)存儲(chǔ)其父類(lèi)結(jié)點(diǎn)所包含的具有該特定關(guān)鍵詞的對(duì)象。以圖1為例，關(guān)鍵詞“swim”對(duì)應(yīng)的B+tree如圖5所示，其中單元編號(hào)包括Morton碼和單元所處的層次標(biāo)識(shí)兩部分組成。

圖5 “swim”對(duì)應(yīng)的線性四分樹(shù)

3.2 Avqt 部分匹配查詢(xún)算法

本文采用最小最佳優(yōu)先原則，基于根據(jù)查詢(xún)關(guān)鍵詞對(duì)應(yīng)的IL-quadtrees上建立的虛擬四分樹(shù)，提出了一種新穎的Top-k部分匹配查詢(xún)算法。本文的目標(biāo)即從帶有同時(shí)帶有空間位置和文本信息的空間文本對(duì)象集合O中，根據(jù)查詢(xún)集合q，運(yùn)用倒排線性四分樹(shù)，尋找包含q中所有或部分關(guān)鍵字集合并且空間文本相似性盡可能大的k個(gè)對(duì)象。

具體來(lái)講，查詢(xún)結(jié)果需要滿足空間與語(yǔ)義兩方面要求：從語(yǔ)義的角度講，查詢(xún)結(jié)果中的點(diǎn)集合應(yīng)包含所有或部分查詢(xún)點(diǎn)語(yǔ)義；從空間的角度講，查詢(xún)點(diǎn)到對(duì)象點(diǎn)距離盡可能短，以滿足空間上興趣點(diǎn)接近預(yù)設(shè)地點(diǎn)的要求。

3.2.1 自適應(yīng)虛擬四分樹(shù)的建立

虛擬四分樹(shù)之所以稱(chēng)為“虛擬”在于其物理上并不真實(shí)存在。預(yù)先設(shè)定好區(qū)域劃分的深度，則四分樹(shù)中每個(gè)區(qū)域的編碼和每個(gè)區(qū)域的上層結(jié)點(diǎn)區(qū)域編碼均可知。所以，根據(jù)已知的區(qū)域間的層級(jí)關(guān)系就能夠建立一棵體現(xiàn)層級(jí)關(guān)系的虛擬四分樹(shù)。由于虛擬四分樹(shù)在對(duì)空間進(jìn)行邏輯上的劃分時(shí)，可對(duì)空間區(qū)域進(jìn)行自適應(yīng)的劃分，會(huì)導(dǎo)致不同的層次相同編碼的現(xiàn)象。因此本文采用對(duì)虛擬四分樹(shù)進(jìn)行四分時(shí)對(duì)被四分單元進(jìn)行層次標(biāo)號(hào)編輯，進(jìn)而區(qū)分不同層次的碼值，形成自適應(yīng)虛擬四分樹(shù)。圖6顯示了與圖1對(duì)應(yīng)的針對(duì)查詢(xún)q的虛擬四分樹(shù)，其中黑色表示查詢(xún)?cè)L問(wèn)可不再深入的單元，白色表示查詢(xún)需繼續(xù)訪問(wèn)的單元。假設(shè)區(qū)域被劃分的最大深度為3，虛擬四分樹(shù)的劃分深度為該區(qū)域包含的對(duì)象數(shù)小于等于1時(shí)停止劃分。則虛擬四分樹(shù)的根節(jié)點(diǎn)為整個(gè)區(qū)域，即(000,0)表示該區(qū)域是處于第0層上碼值為000的區(qū)域。虛擬四分樹(shù)的第一層結(jié)點(diǎn)即第0層區(qū)域的下一層區(qū)域，編碼為{(000,1)，(100,1)，(200,1)，(300，1)}。虛擬四分樹(shù)中第一層(000,1)結(jié)點(diǎn)的第二層結(jié)點(diǎn)，編碼為{(000,2)，(010,2)，(020,2)，(030,2)}，依次類(lèi)推，即可構(gòu)建一棵完整的自適應(yīng)虛擬四分樹(shù)。

圖6 自適應(yīng)虛擬四分樹(shù)

3.2.2 Avqt算法流程

Avqt算法將整個(gè)空間區(qū)域按照邏輯上四分樹(shù)的思想運(yùn)用自適應(yīng)虛擬四分樹(shù)進(jìn)行劃分，利用最小最佳優(yōu)先原則查找符合要求的Top-k個(gè)空間文本對(duì)象。算法1中展示了Avqt算法的具體過(guò)程。在該算法中，用棧h存放從虛擬四分樹(shù)中取得的被標(biāo)記過(guò)層次的結(jié)點(diǎn)碼值以及該結(jié)點(diǎn)與查詢(xún)q之間的空間文本相似性值。棧h中的元素以該元素與查詢(xún)點(diǎn)之間的空間文本相似性值為排序依據(jù)，升序排列。自適應(yīng)虛擬四分樹(shù)的劃分程度為該區(qū)域下只有一個(gè)對(duì)象或該區(qū)域的層次已經(jīng)處于預(yù)先設(shè)定好的最深層次r，滿足其中一種即可認(rèn)為該區(qū)域?yàn)槿~子結(jié)點(diǎn)，否則為非葉子結(jié)點(diǎn)。首先找到與查詢(xún)關(guān)鍵字q.T對(duì)應(yīng)的聚集線性四分樹(shù)記為tset。將虛擬四分樹(shù)的根結(jié)點(diǎn)放入棧h中(第3行)。當(dāng)棧h不為空時(shí)，從棧h中取出棧頂結(jié)點(diǎn)e(第5行)。判斷結(jié)點(diǎn)e是否為空間文本對(duì)象(第9行)，如果是，則將結(jié)點(diǎn)e直接放入結(jié)果集R中。如果不是，判斷結(jié)點(diǎn)e的類(lèi)型。如果結(jié)點(diǎn)e是非葉子結(jié)點(diǎn)(第12行)，則依次計(jì)算e的四個(gè)孩子結(jié)點(diǎn)e’ 在tset中的關(guān)鍵詞權(quán)重加同時(shí)運(yùn)用式(3)計(jì)算e’與查詢(xún)q之間的空間文本相似性f(q,e’)存入棧h中(第14-18行)。如果結(jié)點(diǎn)e為葉子結(jié)點(diǎn)(第22行)，則將結(jié)點(diǎn)e在不同的與查詢(xún)關(guān)鍵詞對(duì)應(yīng)的線性四分樹(shù)上的對(duì)象取出，計(jì)算每個(gè)對(duì)象與查詢(xún)q之間的空間文本相似性放入棧h中。最后，當(dāng)結(jié)果集R中對(duì)象個(gè)數(shù)達(dá)到k時(shí)，算法終止。

算法在完全匹配語(yǔ)義上的擴(kuò)展：算法1可以很容易地?cái)U(kuò)展到對(duì)完全匹配語(yǔ)義的支持。在完全匹配語(yǔ)義中，只需在取出線性四分樹(shù)上某一層次的結(jié)點(diǎn)時(shí)，判斷其是否在所有的聚集線性四分樹(shù)中存在。如果是則證明該結(jié)點(diǎn)所在區(qū)域含有全部關(guān)鍵詞。執(zhí)行算法的相關(guān)計(jì)算即算法1中，在第14行和第22行加上相應(yīng)的約束即可。

算法1基于自適應(yīng)虛擬四分樹(shù)的空間關(guān)鍵詞查詢(xún)算法(Avqt)

Input:L Q:線性四分樹(shù)，

k:要求返回對(duì)象的個(gè)數(shù),

q:查詢(xún)對(duì)象 Output,

d:空間距離約束

Output:R:前k個(gè)f值最小的對(duì)象集合

1.R=?; h=?;

2.tset=所有與q.T相對(duì)應(yīng)的LQ;

3.將虛擬四分樹(shù)的根結(jié)點(diǎn)放入棧h;

4.while h≠? do

5. 從棧nbs中出棧頂結(jié)點(diǎn)e;

6. if |R|=k then

7. break;

8. end if:

9. if e是一個(gè)對(duì)象then

10. R:=R∪e;

11. else

12. if e 是一個(gè)非葉子結(jié)點(diǎn) then

13. for 該結(jié)點(diǎn)的每一個(gè)孩子結(jié)點(diǎn)e’

14. for tset中的每一棵LQ

15. 計(jì)算e’中關(guān)鍵字對(duì)應(yīng)的權(quán)重加和;

16. end for;

17. 計(jì)算 f(q,e’);

18. 將代有層次標(biāo)號(hào)的子結(jié)點(diǎn)e’和f(q,e’)入棧h;

19. end for;

20. else

21. for 葉子結(jié)點(diǎn)e 中的每一個(gè)對(duì)象o

22. for tset中的每一棵LQ

23. 計(jì)算o中關(guān)鍵字對(duì)應(yīng)的權(quán)重加和;

24. end for;

25. 計(jì)算 f(o,q);

26. 將對(duì)象o和f(q,o)入棧 h;

27. end for;

28. end if;

29. end if;

30. end while;

31.return R;

4 實(shí) 驗(yàn)

本節(jié)將通過(guò)一系列的實(shí)驗(yàn)來(lái)驗(yàn)證本文提出的Avqt空間關(guān)鍵詞查詢(xún)算法的查詢(xún)效率。

本文在公開(kāi)的真實(shí)數(shù)據(jù)集上進(jìn)行算法性能的評(píng)估。應(yīng)用Foursquare簽到數(shù)據(jù)集[29-30]，采用數(shù)據(jù)集上紐約(NYC)和洛杉磯(LA)的簽到數(shù)據(jù)。表1中列出了數(shù)據(jù)集的具體信息，包括對(duì)象數(shù)量，關(guān)鍵詞數(shù)量與每個(gè)對(duì)象的平均關(guān)鍵詞數(shù)量，其中數(shù)據(jù)集中的對(duì)象由該對(duì)象的地理坐標(biāo)和一組文本描述組成。

表1 數(shù)據(jù)集的統(tǒng)計(jì)信息

一次最近鄰查詢(xún)由200個(gè)查詢(xún)組成，通過(guò)改變算法中的各個(gè)參數(shù)和實(shí)驗(yàn)數(shù)據(jù)集的大小形成的不同查詢(xún)平均處理時(shí)間來(lái)評(píng)價(jià)算法的性能。其中，查詢(xún)點(diǎn)的坐標(biāo)在整個(gè)被查詢(xún)區(qū)域中隨機(jī)生成，查詢(xún)點(diǎn)所具有的多個(gè)查詢(xún)關(guān)鍵詞在整個(gè)被查詢(xún)區(qū)域中的所有關(guān)鍵詞中隨機(jī)抽取。查詢(xún)關(guān)鍵詞的個(gè)數(shù)(l)被設(shè)置從1到5，查詢(xún)返回的結(jié)果個(gè)數(shù)k被設(shè)置為從10到50，調(diào)節(jié)空間與文本的權(quán)重比例的參數(shù)α被設(shè)置為從0.1到0.9。默認(rèn)l=3，k=10，α=0.3。

實(shí)驗(yàn)中的所有算法均用Java實(shí)現(xiàn)，運(yùn)行于Intel(R) i5 2.30 GHz CPU處理器、4 GB內(nèi)存的Windows 8計(jì)算機(jī)上。實(shí)驗(yàn)將本文提出的ORQN算法在兩個(gè)數(shù)據(jù)集上進(jìn)行對(duì)比。并對(duì)Avqt算法中的各參數(shù)和影響因素進(jìn)行分析。

圖7對(duì)比展示了Avqt算法在兩個(gè)真實(shí)數(shù)據(jù)集上的算法的查詢(xún)平均處理時(shí)間。由圖7可知，Avqt算法在兩個(gè)數(shù)據(jù)集上的平均處理時(shí)間相差不大，表明Avqt的算法性能較穩(wěn)定，受不同區(qū)域情況的影響很小。由于Avqt在查詢(xún)的過(guò)程中采用自適應(yīng)虛擬四分樹(shù)，將不滿足查詢(xún)的區(qū)域直接剪枝。且Avqt算法運(yùn)用倒排線性四分樹(shù)存儲(chǔ)每個(gè)關(guān)鍵字的權(quán)重，查詢(xún)過(guò)程中只需訪問(wèn)查詢(xún)關(guān)鍵詞對(duì)應(yīng)的幾棵線性四分樹(shù)，極大地減少了計(jì)算的次數(shù)，提高了算法的效率。

圖7 不同數(shù)據(jù)集上的算法性能

圖8對(duì)比展示了查詢(xún)平均處理時(shí)間在不同查詢(xún)返回結(jié)果個(gè)數(shù)k下的變化。ALA和ANYC分別表示Avqt算法在LA數(shù)據(jù)集和NYC數(shù)據(jù)集下不同查詢(xún)返回的結(jié)果個(gè)數(shù)k下所產(chǎn)生的平均響應(yīng)時(shí)間的變化。由圖8可以看出，Avqt算法的性能在兩個(gè)數(shù)據(jù)集上均隨著查詢(xún)返回結(jié)果的個(gè)數(shù)的增加而相應(yīng)的降低。這是由于查詢(xún)返回的結(jié)果個(gè)數(shù)增加了查詢(xún)的范圍所導(dǎo)致的。

圖8 不同查詢(xún)結(jié)果數(shù)下的算法效率

圖9對(duì)比展示了查詢(xún)平均處理時(shí)間在不同查詢(xún)關(guān)鍵詞數(shù)l下的變化。Avqt算法在兩個(gè)數(shù)據(jù)集上的平均查詢(xún)處理時(shí)間均隨著查詢(xún)關(guān)鍵詞個(gè)數(shù)的增加而增加，而增加幅度在逐漸降低，這是由于Avqt算法的剪枝能力均隨著查詢(xún)關(guān)鍵字個(gè)數(shù)的增加而不斷地增強(qiáng)。

圖9 不同數(shù)量查詢(xún)關(guān)鍵詞下的算法效率

圖10對(duì)比展示了Avqt算法的查詢(xún)平均處理時(shí)間在不同數(shù)據(jù)集大小下的變化。由圖10可以看出，Avqt算法的性能隨著數(shù)據(jù)集數(shù)量的增加而有所下降，這是由于隨著數(shù)據(jù)集的增大，區(qū)域中空間文本對(duì)象的密度也在不斷增大，造成了在查詢(xún)的過(guò)程中自適應(yīng)虛擬四分樹(shù)須更多的訪問(wèn)區(qū)域下的對(duì)象。但圖中兩條線整體上比較穩(wěn)定，說(shuō)明Avqt算法能較好地適應(yīng)較大的數(shù)據(jù)集。

圖10 不同大小的數(shù)據(jù)集下的算法效率

圖11對(duì)比展示了查詢(xún)平均處理時(shí)間在不同參數(shù)α值下的變化。其中α為一個(gè)可調(diào)節(jié)參數(shù)，用來(lái)調(diào)節(jié)查詢(xún)時(shí)對(duì)空間距離和文本相似程度的重要性的比例關(guān)系。由圖11可以看出，當(dāng)參數(shù)α在0.3附近時(shí)算法在兩個(gè)數(shù)據(jù)集上的平均處理時(shí)間相差很小且曲線波動(dòng)較小，此時(shí)算法性能較穩(wěn)定。因此，本文將α等于0.3設(shè)置為默認(rèn)參數(shù)值，以保證算法的穩(wěn)定運(yùn)行。

圖11 不同參數(shù)值下算法的效率

5 結(jié) 語(yǔ)

隨著移動(dòng)互聯(lián)網(wǎng)的高速發(fā)展和移動(dòng)定位設(shè)備的廣泛普及，基于位置的地理信息服務(wù)逐漸滲透進(jìn)人們生活的方方面面。隨之而來(lái)的空間關(guān)鍵詞的查詢(xún)研究成為位置服務(wù)領(lǐng)域研究的熱點(diǎn)。如何在保證查詢(xún)準(zhǔn)確性的前提下，不斷高效快速地滿足用戶(hù)的實(shí)際查詢(xún)需求成為該研究面臨的主要挑戰(zhàn)。本文研究了基于自適應(yīng)虛擬四分樹(shù)高效Top-k空間關(guān)鍵詞查詢(xún)技術(shù)。綜合考慮實(shí)際生活中用戶(hù)的個(gè)性化的查詢(xún)需求，實(shí)現(xiàn)高效快速地返回用戶(hù)的查詢(xún)結(jié)果，并通過(guò)大量的實(shí)驗(yàn)證明了所提算法的有效性和穩(wěn)定性。未來(lái)考慮將此技術(shù)擴(kuò)展到路網(wǎng)的研究中。