于啟迪 吳 雷,2 馬 昂

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

0 引 言

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

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

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

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

圖1 一個查詢的例子

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

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

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

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

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

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

1 相關(guān)工作

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

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

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

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

2 問題的形式化描述

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

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

(1)

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

(2)

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

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

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

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

(3)

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

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

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

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

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

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

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

本文的研究目標是要運用倒排線性四分樹(詳見3.1節(jié))，從空間文本對象組成的集合O中，尋找與查詢q空間文本相似性最高的k個對象，即k最鄰近查詢。

3.1 倒排線性四分樹 IL-quadtree

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

圖2 聚集倒排線性四分樹

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

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

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

圖4 區(qū)域編碼

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

圖5 “swim”對應的線性四分樹

3.2 Avqt 部分匹配查詢算法

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

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

3.2.1 自適應虛擬四分樹的建立

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

圖6 自適應虛擬四分樹

3.2.2 Avqt算法流程

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

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

算法1基于自適應虛擬四分樹的空間關(guān)鍵詞查詢算法(Avqt)

Input:L Q:線性四分樹，

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

q:查詢對象 Output,

d:空間距離約束

Output:R:前k個f值最小的對象集合

1.R=?; h=?;

2.tset=所有與q.T相對應的LQ;

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

4.while h≠? do

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

6. if |R|=k then

7. break;

8. end if:

9. if e是一個對象then

10. R:=R∪e;

11. else

12. if e 是一個非葉子結(jié)點 then

13. for 該結(jié)點的每一個孩子結(jié)點e’

14. for tset中的每一棵LQ

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

16. end for;

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

18. 將代有層次標號的子結(jié)點e’和f(q,e’)入棧h;

19. end for;

20. else

21. for 葉子結(jié)點e 中的每一個對象o

22. for tset中的每一棵LQ

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

24. end for;

25. 計算 f(o,q);

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

27. end for;

28. end if;

29. end if;

30. end while;

31.return R;

4 實 驗

本節(jié)將通過一系列的實驗來驗證本文提出的Avqt空間關(guān)鍵詞查詢算法的查詢效率。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié) 語

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