支持OR語義的高效受限Top-k空間關(guān)鍵字查詢技術(shù)?

潘 曉,于啟迪,馬 昂,孫亞欣,吳 雷,,郭景峰

1(石家莊鐵道大學(xué) 經(jīng)濟管理學(xué)院,河北 石家莊 050043)

2(燕山大學(xué) 信息科學(xué)與工程學(xué)院,河北 秦皇島 066004)

隨著智能手機和移動終端的普及,越來越多的應(yīng)用中出現(xiàn)了地理位置與文本信息交融的現(xiàn)象[1,2].一方面,越來越多的場所,例如商店、飯店、游樂場等,都附加了與其地理位置相關(guān)的文本描述信息;另一方面,文本信息也通過地名、街道地址等特征與地理信息相關(guān)聯(lián).研究表明,大約有五分之一的互聯(lián)網(wǎng)搜索與地理位置相關(guān),包括地名、郵政編碼等[3].在同時含有空間信息和文本信息的對象上進行空間文本查詢(簡稱為空間關(guān)鍵字查詢)是當前研究的熱點問題之一[4],即給定查詢點位置和文本信息,從大量空間文本對象中找到符合查詢要求的對象.

Top-k空間關(guān)鍵字搜索是空間關(guān)鍵字查詢領(lǐng)域中非常重要的操作之一,其根據(jù)給定的評分函數(shù)在數(shù)據(jù)集中返回得分最高的k個對象[5-13].現(xiàn)有大部分空間關(guān)鍵字查詢工作最先考慮的是滿足用戶所有文本要求和位置鄰近性要求的對象,可稱其為基于AND 語義的查詢.然而,基于AND 語義的查詢結(jié)果需完全匹配查詢關(guān)鍵字,有時會使用戶錯失一些較好的選擇.以圖1 為例,空間中的每個對象(即黑色點o1至o6)均具有地理位置坐標和相應(yīng)的關(guān)鍵字集合,其中每一個關(guān)鍵字對應(yīng)一個權(quán)值,表示該關(guān)鍵字的重要程度(如用戶評分).例如,對象o2是一個電影院,對象o4是一個綜合性商場.假設(shè)用戶初到該城市,在查詢點q(紅色點)的位置查找一家電影院,并想喝杯咖啡.基于AND 語義的Top-2 查詢將返回對象集合{o4,o5},因為僅此兩個對象同時包含{cinema,coffee}兩個關(guān)鍵字.觀察圖1 中的對象,很明顯,對象o2和o1均部分滿足用戶要求,且對象o2和o1在對應(yīng)查詢關(guān)鍵字上的權(quán)重均大于對象o4和對象o5在相應(yīng)查詢關(guān)鍵字上的權(quán)重(設(shè)權(quán)重越高越好),此外,q到對象集合{o1,o2}的距離較到對象集合{o4,o5}更近.換句話說,如果用戶更看重品質(zhì),基于AND 語義查詢返回的結(jié)果將錯過更符合用戶品質(zhì)要求的對象(即對象o2和對象o1),并且,該對象距離查詢用戶位置并不遠.本文關(guān)注的基于OR 語義的受限Top-k空間關(guān)鍵字查詢可解決此類問題.

Fig.1 A simple example圖1 查詢示例

研究者針對Top-k空間關(guān)鍵字搜索問題提出了許多索引技術(shù)和查詢算法[14].其中最普遍使用的是IR-tree索引.在該索引中,根據(jù)所有對象的地理位置建立一棵R 樹,每個節(jié)點關(guān)聯(lián)一個倒排文件.當數(shù)據(jù)量較小時,IRtree 處理效率較高,而當數(shù)據(jù)量增多時,其查詢和更新效率就會下降;此外,由于在空間中只建立了一棵樹,樹的維護時間較長[15,16].為了解決上述不足,文獻[13]提出了一種倒排線性四分樹索引結(jié)構(gòu)IL-Quadtree.IL-Quadtree 為每個關(guān)鍵字都建立了一棵線性四分樹,快速返回符合查詢關(guān)鍵字要求的k個對象.當用戶進行查詢時,只訪問查詢關(guān)鍵字所對應(yīng)的線性四分樹,直接忽略掉那些不包含目標關(guān)鍵字的對象.然而,文獻[16]僅滿足AND 語義要求.本文從查詢OR 語義出發(fā),綜合考慮用戶的地理位置和查詢關(guān)鍵字與空間文本對象匹配的情況,返回在用戶空間范圍要求內(nèi)的空間文本相似性最高的前k個對象,即支持OR 語義的受限Top-k空間關(guān)鍵字查詢.

本文采用倒排聚集線性四分樹AIL 索引所有的空間文本對象.即在倒排文件中存儲所有關(guān)鍵字,倒排文件中的每個關(guān)鍵字指向包含該關(guān)鍵字的所有對象組成的聚集線性四分樹.在AIL 的基礎(chǔ)上,本文提出了兩種查詢處理算法VQuad 和VGrid.受文獻[16]的啟發(fā),VQuad 算法將整個空間區(qū)域看成一個虛擬四分樹,基于此,虛擬四分樹采用最小最佳優(yōu)先原則返回同時支持OR 語義與空間距離約束的結(jié)果.VQuad 算法是一個自頂向下的空間搜索算法.然而,線性四分樹在物理上存儲的并不是空間層次型結(jié)構(gòu),造成了在非空間層次結(jié)構(gòu)上構(gòu)建層次結(jié)構(gòu)信息時,VQuad 重復(fù)遍歷線性四分樹.我們發(fā)現(xiàn),線性四分樹中的空間編碼相當于將整個區(qū)域劃分為虛擬網(wǎng)格,線性四分樹中的對象位置與網(wǎng)格單元中的碼值具有一一對應(yīng)的關(guān)系.利用該對應(yīng)關(guān)系,在網(wǎng)格中可以通過O(1)的時間復(fù)雜度訪問任意單元的鄰近單元,避免了線性四分樹的重復(fù)遍歷.基于上述想法,本文提出了一種基于虛擬網(wǎng)格的高效查詢算法VGrid.

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

● 在倒排聚集線性四分樹的基礎(chǔ)上,提出了一種支持OR 語義的基于虛擬四分樹的Top-k空間關(guān)鍵字搜索算法VQuad.

● 從線性四分樹中空間位置的編碼特點出發(fā),提出了一種基于虛擬網(wǎng)格遍歷的高效OR 語義查詢的Top-k空間關(guān)鍵字搜索算法VGrid.

● 在真實數(shù)據(jù)集上進行了大量的實驗,驗證了所提方法在支持OR 語義和AND 語義上的有效性和高效性.

本文第1 節(jié)回顧Top-k空間關(guān)鍵字查詢領(lǐng)域的相關(guān)工作.第2 節(jié)給出問題的形式化描述以及相關(guān)定義.第3節(jié)闡述聚集倒排線性四分樹索引結(jié)構(gòu)AIL,并詳細介紹在該樹上的相關(guān)操作.第4 節(jié)提出基于OR 語義的受限Top-k空間關(guān)鍵字查詢處理算法VQuad 和VGrid.第5 節(jié)闡述在真實數(shù)據(jù)上進行的一系列實驗,并對實驗結(jié)果進行分析.最后,第6 節(jié)對全文進行總結(jié).

1 相關(guān)工作

空間關(guān)鍵字查詢的文本約束可分為4 種[11]:完全匹配、部分匹配、模糊匹配和布爾約束.文獻[8,16-20]屬于完全匹配約束(即AND 語義約束),查詢完全滿足用戶關(guān)鍵字要求的對象.適用于用戶對文本相似性要求較高的情況.文獻[7,12,15,21-24]屬于部分匹配約束(即OR 語義約束),查詢滿足用戶部分關(guān)鍵字要求的對象.相較于完全匹配約束,當查詢用戶對文本相似性要求的嚴格程度不那么高時,可以采用部分匹配的方式.模糊匹配[25-29]要求對象關(guān)鍵字與查詢關(guān)鍵字進行字符串相似度匹配.布爾約束[30-33]是用一個布爾表達式指定必須包含或可包含的關(guān)鍵詞以及不包含的關(guān)鍵詞.

就查詢結(jié)果的排序方式而言,排序公式一般為空間距離和文本相關(guān)性的某種組合.例如,文獻[30,34]僅依據(jù)查詢對象與被查詢對象的空間距離作為排序依據(jù);文獻[35]以空間和文本相關(guān)性的比值作為排序依據(jù);文獻[16,36-39]采用的是空間和文本相關(guān)性的線性組合;文獻[16,35-39]使用戶對于空間距離與文本相關(guān)性的重要程度有一定的選擇權(quán),但不能完全約束空間距離,導(dǎo)致查詢返回的結(jié)果有距離用戶過遠的可能.本文采取空間距離與文本相關(guān)性的線性組合排序,并且增加了對空間距離的約束,充分考慮了用戶對空間距離與文本重要程度的實際需求.

現(xiàn)有的在空間文本對象上建立的索引結(jié)構(gòu)可分為空間優(yōu)先和文本優(yōu)先兩類.空間優(yōu)先的索引是先根據(jù)空間劃分建立索引,然后在每個節(jié)點中存放有關(guān)的關(guān)鍵字信息.空間優(yōu)先的索引中使用最多的是IR-tree[19,22]和IR2-tree[18]等.IR-tree 為R-tree 中的每個節(jié)點關(guān)聯(lián)了一個倒排文件.IR2-tree 為R-tree 中的每個節(jié)點關(guān)聯(lián)了簽名文件,簽名文件概括了一個節(jié)點所包含的關(guān)鍵字信息.當數(shù)據(jù)量較小時,IR-tree 和IR2-tree 的處理較為高效,當數(shù)據(jù)量增大時,這類索引的效率將明顯下降,并且剪枝困難,影響到算法效率[15].另一類是文本優(yōu)先的索引,這類索引是在現(xiàn)有文本索引(如倒排文件)上進行的改進,將每一個關(guān)鍵字映射到一個含有空間信息的數(shù)據(jù)結(jié)構(gòu)上,如I3[15]、S2I[13]、IL-Quadtree[16]等.I3索引使用四分樹(quadtree)將位置空間進行劃分,提出關(guān)鍵字單元作為基本存儲單元,根據(jù)不同關(guān)鍵字在單元格中出現(xiàn)的次數(shù),分為頻繁和非頻繁的關(guān)鍵字.對于非頻繁的關(guān)鍵字,直接用一個頁面存儲相關(guān)對象,通過查找表直接映射到數(shù)據(jù)文件中的物理位置;對于頻繁的關(guān)鍵字,為頻繁的關(guān)鍵字設(shè)計頭文件指向關(guān)鍵字單元格所在磁盤頁,其中,頭文件是一個類似于四分樹的結(jié)構(gòu),每個節(jié)點存儲關(guān)于頻繁關(guān)鍵字的概要信息.IL-Quadtree 針對每個關(guān)鍵字建立一棵線性四分樹.通過檢測不同樹的相同節(jié)點,檢驗該區(qū)域是否包含所有的關(guān)鍵字,以實現(xiàn)剪枝.

本文在研究內(nèi)容上,就文本約束而言,屬于部分匹配約束;就排序方式而言,采用空間與文本相似性的線性組合;就索引結(jié)構(gòu)而言,采用文本優(yōu)先的聚集倒排線性四分樹.與現(xiàn)有工作的區(qū)別主要體現(xiàn)在以下3 點:第一,本文將整個區(qū)域劃分為虛擬網(wǎng)格,網(wǎng)格中每一個單元均具有唯一的碼值標識,非空網(wǎng)格單元以聚集線性四分樹的形式存儲.第二,利用單元碼唯一并與單元坐標可相互轉(zhuǎn)換的性質(zhì),鄰近單元可通過O(1)時間復(fù)雜度的方法計算來獲得,極大地加快了查詢速度.第三,空間和文本相關(guān)性的線性組合同時考慮了空間距離與文本相關(guān)性,并且在此基礎(chǔ)上增加了對空間距離的約束,通過對空間距離的約束有效地縮小了可查詢的空間范圍.

2 問題的形式化定義

空間中任意對象均包含地理位置和文本關(guān)鍵字集合,記為o=(loc,T),其中,空間位置o.loc=(x,y),文本關(guān)鍵字集合o.T={t1,t2,...,tn},ti是文本關(guān)鍵字.任意兩個空間文本對象的相似性包括空間相似性和文本相似性兩個方面.

定義1(空間相似性).任意兩個空間文本對象在空間中的相似程度用空間相似性表示.查詢對象q與被查詢對象o的空間相似性定義為

其中,δmax表示空間中任意兩點的最遠距離.fs(q,o)可采用任意兩點間的距離公式,本文采用的是歐幾里德距離.兩個對象空間距離越近,fs(q,o)的值越小,空間相似性越大.

定義2(文本相似性).空間文本對象o中的每個關(guān)鍵字都被賦予一個權(quán)重,代表該關(guān)鍵字在對象o中的重要程度.對于任意的關(guān)鍵字t,在對象o中的重要程度記為wt,o.wt,o=tft,o×idft,其中,tft,o是詞頻,idft表示逆向文件頻率.兩個對象q和o的文本相似性為

∑t∈q.T wt,o是所有查詢關(guān)鍵字在o中的權(quán)重加和.maxP是每個關(guān)鍵字在所有對象中的最大權(quán)重加和,用以歸一化計算.ft(q,o)的值越小,文本相似性越大.定義2 中的文本相似性定義支持查詢關(guān)鍵字的OR 語義.具體地,即使查詢q.T中的部分關(guān)鍵字不被包含在對象o中(即wt,o=0),其文本相似性也不會為0.

定義3(空間文本相似性).結(jié)合定義1 和定義2,任意兩個空間文本對象的相似性為

其中,α(α∈[0,1])是一個可調(diào)節(jié)參數(shù),用以調(diào)節(jié)空間距離與文本相似性之間的重要程度.f(q,o)的值越小,q與o的空間文本相似性就越大.

本文問題描述如下:設(shè)空間文本對象集合O={o1,o2,…,on},用戶查詢q=(loc,T,d,k).loc是用戶查詢所在位置,T是由一系列查詢關(guān)鍵字組成的集合,d是用戶可以接受的最遠距離,k即最近鄰對象個數(shù),其中,d的優(yōu)先級比k高.受限Top-k空間關(guān)鍵字查詢即從O中查找在距離d范圍內(nèi)空間文本相似性最高的k個被查詢對象.其形式化表示見定義4.

定義4(受限Top-k 空間關(guān)鍵字查詢).設(shè)查詢對象q和被查詢集合O,一個對象o∈O是查詢q的受限Top-k關(guān)鍵字查詢結(jié)果當且僅當對象o滿足

3 倒排聚集線性四分樹AIL

本文采用倒排聚集線性四分樹索引所有的空間文本對象.倒排聚集線性四分樹是倒排表與聚集線性四分樹的結(jié)合.倒排表中的每一個關(guān)鍵字指向一棵聚集線性四分樹.圖2 是基于圖1 中的空間文本對象建立的倒排聚集線性四分樹示例.

一個關(guān)鍵字對應(yīng)一棵聚集線性四分樹.該樹由包含該關(guān)鍵字的所有空間文本對象組成,那些不包含該關(guān)鍵字的對象不會在該聚集線性四分樹中被索引.“聚集”是指在樹中每一個節(jié)點中都存儲一個聚集值,即該關(guān)鍵字在此節(jié)點下的最大權(quán)重.如圖4 所示,“coffee”對應(yīng)的線性四分樹的根節(jié)點中的0.176 表示樹下所有的對象{o1,o3,o4,o5}中“coffee”的權(quán)重均不大于0.176.線性四分樹源于四分樹,與四分樹不同的是,線性四分樹以B+-樹的形式存儲空間位置的編碼值,不是直接存儲空間位置(編碼方法將在本節(jié)后面加以闡述).此外,線性四分樹中不存儲不包含任何對象的空間碼值.若采用四進制Morton 碼對圖1 所示的空間進行編碼,其結(jié)果可如圖3 所示.包含“coffee”關(guān)鍵字的對象有{o1,o3,o4,o5},將這些對象所在位置對應(yīng)的Morton 碼用B+-樹索引起來即形成“coffee”關(guān)鍵字對應(yīng)的聚集線性四分樹,如圖4 所示.類似地,“cinema”對應(yīng)的聚集線性四分樹如圖5 所示.圖4 和圖5 中的兩棵聚集線性四分樹是圖2 中“coffee”和“cinema”的關(guān)鍵字對應(yīng)的聚集線性四分樹的詳細版.

Fig.2 Aggregate inverted linear quadtree圖2 聚集倒排線性四分樹

Fig.3 Encoded space圖3 空間編碼

Fig.4 Aggregate linear quadtree w.r.t.coffee圖4 “coffee”對應(yīng)的聚集線性四分樹

Fig.5 Aggregate linear quadtree w.r.t.cinema圖5 “cinema”對應(yīng)的聚集線性四分樹

空間位置可遵循一定的規(guī)則進行編碼,常用的有四進制或十進制Morton 碼,本文采用四進制Morton 碼.文獻[40]對空間位置編碼方法進行了詳細闡述,這里僅作簡要說明.編碼過程需要借助四分樹,設(shè)四分樹最大層次為r.自頂向下地對空間位置進行四等分直至層數(shù)r.在任意層次h(h≤r)下,將SW、SE、NW、NE 這4 個方向的等分區(qū)域分別標記為0、1、2、3,如圖6(a)所示.在空間上建立四分樹(如圖6(b)所示).四分樹上一個h層的空間位置可用一個h位的四進制串表示,稱為位置Morton 碼.如在圖6(b)所示的第3 層,任意一個空間位置都是一個3 位的四進制串.四進制串中從左向右的任意一位表示的是該位置在相應(yīng)層次的方向.具體地,第3 層的Morton碼左側(cè)第1 位數(shù)字表示該節(jié)點在四分樹深度為1 時區(qū)域位于的方向.如圖6(b)所示的中間4 個區(qū)域的編碼為120、121、122、123,其中左側(cè)第1 位的“1”表示這4 個區(qū)域均處于四分樹第1 層的SE 方向.左側(cè)第2 位數(shù)字表示深度為2 時該節(jié)點所屬區(qū)域的方向.繼續(xù)上面的例子,左側(cè)第2 位的“2”表示這4 個區(qū)域均處于四分樹第2層劃分的NW 方向.第3 位的0、1、2、3 表示第3 層上4 個方向的劃分.在線性四分樹中索引的均是底層(最深層)的Morton 碼.因此,采用Morton 碼對圖1 所示的空間進行編碼,圖3 和圖6(b)所示的最底層葉子節(jié)點編碼是一致的.

Fig.6 Encoded Morton圖6 Morton 編碼

線性四分樹是將上述非空葉子節(jié)點的四進制Morton 碼值以數(shù)字的形式索引起來.綜上所述,聚集線性四分樹AIL 的創(chuàng)建算法如算法1 所示.

算法1.構(gòu)建倒排聚集線性四分樹AIL.

4 基于OR 語義的受限Top-k 空間關(guān)鍵字查詢算法

本文的研究目標是基于AIL,從帶有空間位置和文本信息的對象集合O中,尋找在受限范圍內(nèi)與查詢q空間文本相似性最高的k個對象.AIL融合了空間與文本信息,其中的線性四分樹實質(zhì)存儲的是空間位置編碼,倒排文件中存儲了文本信息.所以,基于AIL進行Top-k空間關(guān)鍵字查詢有兩種思路:(1)將線性四分樹轉(zhuǎn)化為空間上的四分樹,改進已有經(jīng)典算法,這是設(shè)計VQuad 算法的初衷(詳見第4.2 節(jié));(2)從線性四分樹的空間編碼入手,直接在編碼后的空間上進行查詢,這是設(shè)計VGrid 算法的動機(詳見第4.3 節(jié)).在介紹具體算法之前,我們先來說明在兩種算法中都將用到的定義和定理.

4.1 相關(guān)定義

在后續(xù)算法中需要計算查詢點到一個覆蓋多個對象的矩形的空間文本相似性.因此,下面首先定義擴展的空間文本對象,然后說明如何利用定義3 計算查詢點到擴展空間文本對象的空間文本相似性.

定義5(擴展的空間文本對象).擴展的空間文本對象R包含地理位置和文本關(guān)鍵字集合兩個部分,其形式化的表示為R=(loc,T).該對象的空間位置loc用一個矩形表示,該矩形可覆蓋R下的每一個空間文本對象.T為R下的所有覆蓋對象的關(guān)鍵字集合的并集,其中,針對每一個屬于T的關(guān)鍵字由兩個元素組成(t,w),t是關(guān)鍵字本身,w是該關(guān)鍵字在R中的最大權(quán)重.

以圖7 為例說明定義5.圖7 顯示了一個擴展的空間文本對象R,其中,R.loc覆蓋對象o3和o4.R.T={coffee(0.088),cinema(0.075),library(0.119),swim(0.151)}.

Fig.7 Extended spatio-textual object R圖7 擴展的空間文本對象R

在擴展的空間文本對象上,依然可以利用公式(3)計算查詢q與擴展空間文本對象R的空間文本相似性.其中,空間相似性采用查詢q到矩形R.loc的最小空間距離,文本相似性采用公式(2)即可.

下面的定理1 證明了查詢q與擴展的空間文本對象R的空間文本相似性是查詢q到R中覆蓋的任意對象的空間文本相似性的上限.

定理1.對于R下覆蓋的任意對象o,f(q,R)≤f(q,o).

證明:從空間和文本兩個角度證明.

從空間的角度,易知對于R中包含的任意對象o,對象o到查詢點q的空間距離不小于R到q的空間距離,即δ(q.loc,R.loc)≤δ(q.loc,o.loc).因此,由公式(1)可知f s(q,R)≤f s(q,o).

從文本的角度,易知對于R中的任意對象o,o.t∈R.T,對象o對應(yīng)于查詢q的文本權(quán)重不大于R對應(yīng)于查詢q.T的文本權(quán)重,即∑t∈q.Twt,o≤∑t∈q.TR.T.Wt,o.因此,由公式(2)可知f t(q,R)≤f t(q,o).

綜合上述空間和文本兩個角度,由公式(3)可得f(q,R)≤f(q,o).由于f(q,o)的值越小越好,因此查詢q與R的文本相似性是查詢q到R中覆蓋的任意空間文本對象的空間文本相似性的上限. □

4.2 VQuad算法

VQuad 算法的基本思想是采用最小最佳優(yōu)先原則,利用AIL中存儲的空間位置重建虛擬四分樹[16],在虛擬四分樹上尋找滿足OR 語義的空間受限的k最近鄰查詢結(jié)果.文獻[16]在虛擬四分樹上進行Top-k關(guān)鍵字查詢處理,但其僅實現(xiàn)了AND 語義.VQuad 算法改進了文獻[16]以支持OR 語義的空間受限查詢.下面首先簡要介紹線性四分樹與虛擬四分樹的轉(zhuǎn)換過程.接下來,在虛擬四分樹的基礎(chǔ)上詳細介紹VQuad 查詢處理方法.

4.2.1 虛擬四分樹

建立虛擬四分樹的目的是將查詢中不同關(guān)鍵字對應(yīng)的聚集線性四分樹整合起來,通過計算虛擬四分樹的節(jié)點與查詢之間的空間文本相似性,將不滿足查詢要求的節(jié)點較早地剪枝掉.虛擬四分樹之所以稱為“虛擬”在于其物理上并不真實存在.由于四分樹中每個層次在線性四分樹的區(qū)域編碼已知,所以根據(jù)樹的層次以及區(qū)域編碼能夠建立一棵虛擬四分樹.圖8 是與圖6(b)一樣的虛擬四分樹.唯一不同的是,這里將每個層次的編碼擴展為r(=3)位.空缺位用X 字符補位.虛擬四分樹的根節(jié)點即整個區(qū)域編碼為XXX(其中,X 可取{0,1,2,3}中的任意值).第1 層的4 個區(qū)域編碼分別為0XX、1XX、2XX、3XX(僅左側(cè)第1 位有意義).虛擬四分樹的第2 層節(jié)點區(qū)域編碼范圍是00X～33X(僅左側(cè)前2 位有意義),虛擬四分樹的第3 層節(jié)點區(qū)域編碼范圍是000～333.

Fig.8 Virtual quadtree圖8 虛擬四分樹

在查詢過程中需要計算虛擬四分樹上的一個區(qū)域與查詢之間的空間文本相似性.然而,虛擬四分樹僅是邏輯上的概念,在物理上實際存儲的是以B+-樹組織起來的碼值.因此,在計算空間文本相似性時,在空間方面,用區(qū)域中的最大Morton 碼值與最小Morton 碼值的橫縱坐標所圍成的區(qū)域限定區(qū)域范圍,表示為(最小Morton 碼值,最大Morton 碼值).通過區(qū)域碼值與空間橫縱坐標的轉(zhuǎn)換即可確定該區(qū)域的空間位置及空間相似性.在文本方面,將區(qū)域中所有單元的關(guān)鍵字權(quán)重最大值加和作為該區(qū)域?qū)?yīng)查詢的文本權(quán)重.由此,可利用公式(3)計算區(qū)域與查詢間的空間文本相似性.例如,圖8 中第2 層編碼為12X 的區(qū)域,其在B+-樹上實際對應(yīng)的編碼為{120,121,122,123}.該區(qū)域?qū)?yīng)查詢要求的文本權(quán)重,即4 個單元內(nèi)對應(yīng)查詢關(guān)鍵字權(quán)重最大值的加和.

4.2.2 VQuad 算法流程

VQuad 算法邏輯上將整個空間用四分樹進行劃分,利用最小最佳優(yōu)先原則選擇符合查詢要求的Top-k個空間文本對象.算法2 展示了VQuad 算法的具體過程.在算法2 中,用棧nbs存放從虛擬四分樹中取得的節(jié)點.棧中元素以節(jié)點到查詢q之間的空間文本相似性的值升序排序.首先,找到查詢q包含的所有關(guān)鍵字對應(yīng)的聚集線性四分樹btset(第2 行),將虛擬四分樹的根節(jié)點入棧nbs中(第3 行).當棧nbs不為空時,從nbs中取棧頂e(第5行).如果e是空間文本對象,則將該對象存入結(jié)果集R中(第8 行～第9 行).如果e是節(jié)點,判斷e是葉子節(jié)點或非葉子節(jié)點,如果e是非葉子節(jié)點,則將節(jié)點e所在區(qū)域進行邏輯上四等分,計算e的4 個孩子節(jié)點與查詢q之間的空間距離,判斷該空間距離是否在用戶允許范圍d內(nèi).如果在空間限制范圍內(nèi),則運用公式(3),計算e的孩子節(jié)點與查詢q之間的空間文本相似性,并將該孩子節(jié)點碼值及其空間文本相似性f(q,e′)入棧nbs(第10 行～第16行).如果e為葉子節(jié)點,則將e在不同的線性四分樹中包含的所有對象取出,判斷取出對象空間上是否在用戶允許范圍d內(nèi).如果是,則計算對象與查詢q之間的空間文本相似性并入棧nbs中(第18 行～第23 行).最后,當結(jié)果集R中的對象個數(shù)達到k時,算法終止.

需要說明的是,VQuad 算法不僅可以支持OR 語義,也可以支持AND 語義.即只需在取出線性四分樹上某一層次的節(jié)點時,判斷其是否在所有的聚集線性四分樹中存在.如果在所有查詢要求的關(guān)鍵字對應(yīng)的線性四分樹中均存在,則執(zhí)行算法的相關(guān)計算,即修改算法2 中的第13 行和第20 行.

4.2.3 運行示例

我們用圖1 來說明算法VQuad 的運行過程.設(shè)AIL的層數(shù)r=3,查詢點q={(5.8,5.8),{coffee,cinema},3,1},其中,d=3,k=1.

首先,虛擬四分樹根節(jié)點的區(qū)域碼值為(000,333).通過公式(3)計算查詢點q與虛擬四分樹根節(jié)點的空間文本相似性f(q,code)=0.344.將{(000,333),0.344}入棧nbs中.由于nbs不為空,棧頂出棧e=(000,333).計算e的4 個孩子節(jié)點的碼值,即{(000,033),(100,133),(200,233),(300,333)}.判斷4 個孩子均在查詢點q的d范圍內(nèi).計算4 個孩子節(jié)點與查詢q的空間文本相似性,見表1 中第3 列.將節(jié)點碼值及其與查詢對應(yīng)的空間文本相似性值按升序存入棧nbs中(見表1 中第4 列).取棧頂e=(300,333),因為單元(300,333)是四分樹的中間節(jié)點,計算e=(300,333)的4 個孩子節(jié)點的碼值,即{(300,303),(310,313),(320,323),(330,333)}.計算查詢點q到d范圍內(nèi)的孩子節(jié)點的空間文本相似性,見表1.將節(jié)點碼值及其與查詢對應(yīng)的空間文本相似性值按升序存入棧nbs中(見表1 中第2 行).

重復(fù)上述操作,直至表1 第4 行,取當前棧頂e=(330,330).因為單元(330,330)是葉子節(jié)點.從與查詢關(guān)鍵字對應(yīng)的B+-樹中取出330 單元以下的對象,即{o2}.因為o2與查詢點q的距離小于d,則計算查詢點q到對象o2的空間文本相似性.將對象及其與查詢q的空間文本相似性的值入棧nbs中(見表1 中第4 行).第5 行中,取棧頂e=o2,因為o2是空間文本對象,將o2存入結(jié)果集.此時k=1,且棧nbs中棧頂元素的空間文本相似性上限小于當前查詢結(jié)果中最差的空間文本相似性,由定理1 可知,程序停止.輸出結(jié)果集R={(o2,0.510)}.

Table 1 A running example of VQuad表1 VQuad 算法運行實例

算法2.基于虛擬四分樹的OR 語義查詢排序算法VQUAD.

4.3 VGird查詢算法

因為VQuad 算法在計算四分樹某一層節(jié)點與查詢點的空間文本相似性時,需要不斷重復(fù)地訪問線性四分樹,進行Morton 碼與空間位置的轉(zhuǎn)換,從而影響了查詢效率.實際上,無需將線性四分樹構(gòu)建成虛擬四分樹,可直接從線性四分樹上的Morton 碼出發(fā),通過二進制的位運算獲得單元的鄰近區(qū)域和區(qū)域中的空間文本對象.基于這樣的動機,本文提出了基于虛擬網(wǎng)格的VGrid 查詢算法.VGrid 將整個空間看成一個虛擬網(wǎng)格,網(wǎng)格中每一個單元均有唯一的Morton 碼.利用單元的Morton 碼與單元位置坐標可相互轉(zhuǎn)換的性質(zhì),鄰近單元可通過公式(5)在O(1)時間復(fù)雜度下計算獲得,提高了查詢效率.

(1)VGrid 算法流程

算法的基本思想是以查詢q所在位置為中心,從中心單元開始,循環(huán)尋找中心單元的鄰近8 個單元(如圖9中的n0～n7所示)中包含的對象,計算該對象與查詢q的空間文本相似性,不斷更新查詢結(jié)果集直至獲得滿足空間限制的Top-k結(jié)果.為了防止空間單元的重復(fù)訪問,采用visit布爾集合來標識單元是否已被訪問.

具體地,首先找到查詢點q所在的單元,確定相應(yīng)的四進制Morton 碼,記為code(第2 行).找到查詢q包含的所有關(guān)鍵字對應(yīng)的聚集線性四分樹btset(第3 行).根據(jù)定義3 計算查詢q到單元code的空間文本相似性,以(code,f(q,code))的形式存入棧nbs(第4 行).nbs中的元素以空間文本相似性升序排序.取nbs棧頂nbs_t.若棧頂對應(yīng)的碼值nbs_t.code存在于線性四分樹集合btset中的任意一棵樹中,則從具有nbs_t.code的線性四分樹中取出nbs_t.code單元下的對象組成Oset(第7 行～第8 行).計算Oset中的對象與查詢q的空間文本相似性,將滿足空間距離約束d的對象放入不斷更新的候選結(jié)果集RSet中,以查詢q到該對象的空間文本相似性為排序關(guān)鍵字(第9 行～第11 行).當Rset中的第k個對象的空間文本相似性值大于棧頂元素的空間文本相似性值時,說明空間中存在比候選集中更符合用戶要求的查詢結(jié)果.此時,利用公式(5)尋找棧頂單元的鄰近8 個單元,將8 個單元中滿足空間距離約束d并且未被訪問的單元的code值及其與查詢的空間文本相似性存入nbs,并在visit中將code單元標識為已訪問(第12 行～第17 行).重復(fù)第6 行～第19 行,直至候選結(jié)果集|Rset|=k,且Rset中對象的第k個對象的空間文本相似性值優(yōu)于nbs中棧頂元素的空間文本相似性值.

算法3.基于虛擬網(wǎng)格的OR 語義查詢排序算法VGrid.

這里需要說明兩點:(1)為保證算法的正確性,在算法3 的第15 行中計算虛擬網(wǎng)格中的一個單元到查詢q的空間文本相似性時,單元格關(guān)鍵字權(quán)重采用的是該關(guān)鍵字在空間中的全局最大值;(2)VGrid 算法可同時支持OR 語義和AND 語義.在完成AND 語義查詢時僅需將算法3 中的第7 行修改為被查詢單元或?qū)ο笫欠翊嬖谟诓樵冴P(guān)鍵字對應(yīng)的所有線性四分樹即可.

(2)運行實例

繼續(xù)以圖1 和查詢點q={(5.8,5.8),{coffee,cinema},3,1}的例子說明算法3(VGrid)的運行過程.首先找到查詢點q所在的單元,確定相應(yīng)的code值為303.在visit中將303 標記為已訪問.通過公式(3)計算查詢點q到303 單元的空間文本相似性f(q,303)=0.700.將(303,0.700)入棧nbs中.設(shè)關(guān)鍵字coffee、cinema 分別對應(yīng)的線性四分樹為bt1和bt2(即圖3 和圖4).棧頂元素303 出棧.雖然單元303 到查詢點q的距離小于d,但303 沒有在bt1和bt2中,說明303 中沒有對應(yīng)查詢文本的對象.利用公式(5)計算303 的相鄰8 個單元,即{300,301,310,312,330,321,320,302}.計算查詢q到每一個單元的空間文本相似性,見表2 的第1 行.將單元Morton 碼值及其與查詢對應(yīng)的空間文本相似性值按升序存入棧nbs中,并在visit中將這些單元標記為已訪問.

從棧nbs中取棧頂330.因為330 到查詢點q的距離小于d,取出樹bt1和bt2中330 單元對應(yīng)的對象,去重后得h={o2}.計算o2與查詢q的空間文本相似性f=0.510,并存入結(jié)果集R={(o2,0.510)}.此時,結(jié)果集R中對象o2的空間文本相似性大于棧頂元素與查詢q的空間相似性(即0.510＞0.485).根據(jù)公式(4)計算棧頂330 相鄰8 個單元,即{303,312,313,331,333,332,323,321}.其中,{303,312,321}均已被訪問,因此將剩余單元到查詢點q的距離小于d的單元,即{313,331,333,332,323}入棧,見表2 第2 行.將{313,331,333,332,323}標記為已訪問.由于此時結(jié)果集R中o2與查詢q空間文本相似性小于棧頂元素對應(yīng)的空間文本相似性(即0.510＜0.576).所以,程序終止.輸出的結(jié)果集R={(o2,0.510)}.

Table 2 Running instance of VGRID表2 VGRID 算法運行實例

(3)鄰近8 個單元的計算方法

Morton 碼[23]是空間網(wǎng)格劃分后每一個單元(cell)的唯一標識,與單元的空間坐標可進行相互轉(zhuǎn)換.利用這個性質(zhì),通過二進制位運算很容易獲得某單元周圍鄰近8 個單元的碼值乃至位置坐標.下面首先說明Morton 碼與空間坐標的相互轉(zhuǎn)換方法,接下來說明如何通過二進制的位運算在O(1)時間內(nèi)獲得鄰近單元的碼值.

已知某單元的十進制坐標為(x,y),其Morton 碼的具體計算方法如下.先將單元位置坐標(x,y)的值轉(zhuǎn)化為二進制形式,令x=xr-1...x1x0,y=yr-1...y1y0,其中,xi,yi∈{0,1},r為線性四分樹劃分的深度.該單元對應(yīng)的二進制編碼為n=yr-1xr-1...y1x1y0x0.例如,圖3 中單元303 的坐標為(5,5),將兩個坐標轉(zhuǎn)化為二進制,分別是x=110,y=110,則該單元對應(yīng)的編碼為n=110011,轉(zhuǎn)化為四進制后即Morton 碼為303.

在算法3 的第13 行需要查找中心單元鄰近的8 個單元,如圖9 所示.其中,任意單元的8 個鄰近單元的計算方法如公式(5)[36].設(shè)中心單元的Morton 碼值為code,則有:

Fig.9 The eight neighbor cells for the cell 303圖9 303 單元的8 個鄰近單元

在公式(5)中,mq是鄰近單元Morton 碼的二進制表示.nq是中心單元code的二進制表示.tx和ty是兩個二進制常數(shù):tx=01...0101 表示“01”重復(fù)r次,ty=10...1010 表示“10”重復(fù)r次.Δni是基本方向增量之一,即計算中心單元任意方向的單元碼值時坐標的變化量,8 個方位的基本增量即Δn0=(-1,-1),Δn1=(0,-1),Δn2=(1,-1),Δn3=(1,0),Δn4=(1,1),Δn5=(0,1),Δn6=(-1,1),Δn7=(-1,0).采用上文單元碼值的計算方法,將?ni由坐標值轉(zhuǎn)換為Morton 碼(見表3 第2 列).公式(5)采用的是位運算:“+”表示相加;“|”表示OR;“^”表示AND.設(shè)線性四分樹劃分深度r=3,計算中心單元303(轉(zhuǎn)換成二進制為110011)的鄰近8 個單元碼值的過程見表3.

Table 3 Increment of direction表3 方向增量

5 實 驗

5.1 實驗設(shè)置

實驗采用Foursquare 上真實的簽到數(shù)據(jù)集[41,42],包括紐約(NYC)和洛杉磯(LA)兩個城市用戶的簽到數(shù)據(jù).圖10 和圖11 展示了將兩個數(shù)據(jù)集導(dǎo)入QGIS 后,簽到興趣點POI(point of interests)的分布情況.表4 列出了數(shù)據(jù)集的統(tǒng)計信息,包括POI 數(shù)量、鍵字數(shù)量以及每個POI 上的平均關(guān)鍵字數(shù).實驗中的所有算法用Java 實現(xiàn).運行于Intel(R)i5 2.30GHzCPU 處理器、4GB 內(nèi)存的Windows 8 計算機上.實驗中,所有的POI 組成被查詢點集合.查詢點集合從POI 集合中隨機抽取10 000 個.隨機抽取的點位置即查詢點位置信息.查詢點的文本關(guān)鍵字按照不同等級的詞頻隨機分配.文本關(guān)鍵字的等級是根據(jù)關(guān)鍵字詞頻的上四分位、中位數(shù)劃分的3 個等級(即高頻、中頻和低頻詞).實驗?zāi)J設(shè)置見表5.

文獻[16]是第1 篇在線性四分樹上進行Top-k關(guān)鍵字查詢的代表性工作,但其僅支持AND 語義.本文提出的VQuad 算法是在文獻[16]中提出的基于虛擬四分樹算法基礎(chǔ)上的改進,所以在支持OR 語義方面,實驗僅對比了VQuad 算法和VGrid 算法在兩個不同數(shù)據(jù)集上平均查詢時間的變化情況(見第5.2 節(jié)).為了驗證兩種算法在AND 語義方面的有效性,第5.3 節(jié)對兩種算法支持AND 語義的實驗結(jié)果進行了對比分析.實驗變動參數(shù)有關(guān)鍵字個數(shù)(l)、返回結(jié)果數(shù)(k)、數(shù)據(jù)集大小等.由于文獻[16]已驗證了倒排線性四分樹與經(jīng)典索引結(jié)構(gòu)的對比情況,這里沒有再對索引結(jié)構(gòu)大小等進行贅述.

Fig.10 LA check-in datasets圖10 LA 簽到數(shù)據(jù)集

Fig.11 NYC check-in datasets圖11 NYC 簽到數(shù)據(jù)集

Table 4 Statistics for the dataset表4 數(shù)據(jù)集的統(tǒng)計信息

Table 5 Default setting表5 實驗?zāi)J設(shè)置

5.2 支持OR語義的算法性能對比

圖12 對比展示了VQuad 和VGird 算法在兩個不同真實數(shù)據(jù)集上的查詢平均處理時間.從圖12 觀察到兩種算法在LA 和NYC 數(shù)據(jù)集上的性能表現(xiàn)類似.從圖10 和圖11 可以看出,兩個簽到數(shù)據(jù)集POI 分布類似且POI個數(shù)接近.無論是在LA 的數(shù)據(jù)集上還是在NYC 的數(shù)據(jù)集上,VGird 的平均處理時間均優(yōu)于VQuad.其原因在于,VQuad 算法需要多次訪問查詢關(guān)鍵字對應(yīng)的線性四分樹.具體地,VQuad 查詢過程中采用的虛擬四分樹是一個邏輯概念上的結(jié)構(gòu),物理上并不存在.因此,每次訪問到某一個層次的四分樹節(jié)點時,需要進行物理上線性四分樹存儲的Morton 碼到虛擬四分樹的轉(zhuǎn)換(見第4.2.1 節(jié)).同時,VQuad 算法在計算非葉子節(jié)點與查詢點的空間文本相似性時,需要該節(jié)點下覆蓋對象的查詢關(guān)鍵字的最大權(quán)重.然而,線性四分樹上存儲的是虛擬四分樹上葉子節(jié)點中所有對象在對應(yīng)關(guān)鍵字的最大權(quán)重.因此,虛擬四分樹的非葉子節(jié)點的關(guān)鍵字最大權(quán)重需要從該節(jié)點下的所有葉子節(jié)點獲得,導(dǎo)致線性四分樹的重復(fù)訪問,影響了查詢效率.相比之下,在空間方面,VGird 算法中通過二進制的位運算(見公式(5))直接獲得附近單元位置,利用visit布爾數(shù)組防止了單元的重復(fù)訪問;在文本關(guān)鍵字方面,VGird 直接運用的是聚集線性四分樹中存儲的每個關(guān)鍵字的最大權(quán)重.因此,查詢效率得到了明顯提高.

圖13 對比展示了查詢平均處理時間在不同查詢關(guān)鍵字個數(shù)l下的變化情況.這里用LVQuad 和LVGrid 分別表示在LA 數(shù)據(jù)集運行VQuad 算法和VGrid 算法.NVQuad 和NVGrid 分別表示在NYC 數(shù)據(jù)集上運行VQuad算法和VGrid 算法.查詢關(guān)鍵字數(shù)量從1 增加到5.隨著查詢關(guān)鍵字個數(shù)的增加,VQuad 和VGrid 均需要訪問更多的關(guān)鍵字對應(yīng)的線性四分樹,因此查詢平均處理時間會隨著關(guān)鍵字個數(shù)的增加而增加.圖13 印證了我們的想法,兩種算法的查詢平均處理時間均隨著查詢關(guān)鍵字個數(shù)的增加亦在增長.然而,兩種算法的增加幅度是逐漸降低的.這是因為在OR 語義環(huán)境下,更多的查詢關(guān)鍵字意味著用戶對查詢需求的放松.線性四分樹中會有更多的候選結(jié)果供選擇.在k確定的前提下,一定程度地舒緩了查詢時間的增長幅度.通過對比圖13 中的4 條曲線可以發(fā)現(xiàn),無論是在LA 數(shù)據(jù)集還是在NYC 數(shù)據(jù)集下,VGrid 算法的查詢效率均比VQuad 算法要好,由圖13 可以看出,VGrid 比VQuad 平均快2.5 倍.

Fig.12 Performance on different datasets圖12 不同數(shù)據(jù)集上的查詢平均處理時間

Fig.13 Performance on different number of query keywords圖13 不同查詢關(guān)鍵字數(shù)量上的查詢平均處理時間

圖14 對比展示了查詢平均處理時間在不同查詢返回結(jié)果個數(shù)k下的變化情況.觀察圖14 發(fā)現(xiàn),兩種算法的平均處理時間均隨著查詢返回結(jié)果的個數(shù)k的增加而增加.顯而易見,由于用戶提高了查詢要求,兩種算法均需要更多的時間在空間中尋找滿足查詢要求的結(jié)果.同時,從圖14 還可以發(fā)現(xiàn),隨著k的增大,在相同的數(shù)據(jù)集上,VQuad 算法的增長幅度比VGrid 平均要大0.05ms.這是因為,隨著查詢返回結(jié)果個數(shù)的增加,VQuad 算法訪問了虛擬四分樹上更多的非葉子節(jié)點,增加了對關(guān)鍵字權(quán)重的計算次數(shù),而VGrid 算法可直接在線性四分樹上獲取關(guān)鍵字權(quán)重,相比之下提高了查詢的效率.最終,從圖14 可以看出,VGrid 算法在兩個數(shù)據(jù)集的查詢平均處理時間相差不大(約差0.07ms).

我們從原始數(shù)據(jù)集中隨機抽取50 000、100 000、150 000、200 000 個POI 對象組成了不同的被查詢對象集合.從圖10 和圖11 可以看出,兩個數(shù)據(jù)集中的POI 不是均勻分布的.所以,不同大小的數(shù)據(jù)集不是在整個空間上均勻增長,而是隨著POI 分布的密集程度而增長.圖15 對比顯示了查詢平均處理時間在不同POI 數(shù)據(jù)集大小下的變化情況.可以看出,整體上來看,兩種算法的性能均隨著數(shù)據(jù)集數(shù)量的增加而下降.平均而言,隨著POI 數(shù)量的增加,在四分樹上一個節(jié)點或網(wǎng)格單元下覆蓋的POI 數(shù)量會增多.這就造成了從一個四分樹節(jié)點或網(wǎng)格單元下需要抽取更多的POI 對象進行檢驗.但無論在哪個數(shù)據(jù)集上,VGrid 的性能都是優(yōu)于VQuad 的.我們發(fā)現(xiàn),兩種算法在數(shù)據(jù)從150 000 增長到200 000 時,NYC 數(shù)據(jù)集上的增長幅度高于LA 數(shù)據(jù)集.通過分析圖10 和圖11 后發(fā)現(xiàn),在相同的POI 集合大小下,NYC 數(shù)據(jù)集比LA 的數(shù)據(jù)集分布得更為分散.整體上來看,兩種算法在處理時間上是高效的,VQuad 在1.1ms 以下,VGrid 在0.43ms 以下.

圖16 對比展示了查詢平均處理時間在不同α值下的變化.α是一個可調(diào)節(jié)參數(shù),用來調(diào)節(jié)空間相似性與文本相似性的重要程度.α越大表示空間相似性的重要程度越大,反之,文本相似性的重要程度越大.由圖16 可以看出,當α從0.1 變到0.9 時,兩種算法在LA 數(shù)據(jù)集和NYC 數(shù)據(jù)集上的平均查詢處理時間均保持平穩(wěn),兩種算法的性能始終保持大約0.5ms 的差距.

由于VGrid 中遞歸計算鄰近8 個單元,為了驗證算法在空間搜索方面的效率,圖17 對比展示了VGrid 算法在兩個數(shù)據(jù)集上的空間搜索占比的變化情況.空間搜索占比即查找到用戶要求的k個最近鄰結(jié)果,算法遍歷過的空間與整個空間面積比值.k從10 增加到50.此時,d被設(shè)置為無窮大.由圖17 可以看出,查詢搜索空間占比會隨著查詢返回結(jié)果個數(shù)的增加而增加.這是比較自然的現(xiàn)象,因為滿足要求的結(jié)果分布在更遠的單元.有趣的是,相同k值設(shè)置下NVGrid 要找到查詢結(jié)果,比LYGrid 搜索的空間更廣.這從另一方面驗證了在NYC 上的查詢平均處理時間比在LA 上要更長.即使k增長到50,搜索空間的占比也低于4.5%.

Fig.14 Performance on different k圖14 不同查詢結(jié)果數(shù)量上的查詢平均處理時間

Fig.16 Performance on different α圖16 不同參數(shù)值α上的查詢平均處理時間

Fig.17 Percentage on different k圖17 不同查詢結(jié)果數(shù)量上的搜索空間占比

5.3 支持AND語義的算法性能對比

本文提出的VGrid 算法和VQuad 算法可同時支持OR 語義和AND 語義.為了全面驗證算法的性能,本節(jié)對比展示了兩種算法在支持AND 語義方面的性能.

圖18 對比展示了VQuad 和VGrid 算法在支持AND 語義時在兩個真實數(shù)據(jù)集上的平均查詢處理時間.與支持OR 語義的情況相比,其相同之處是,在兩個數(shù)據(jù)集上,算法VGrid 的平均處理時間依然均優(yōu)于VQuad;不同之處在于,從整體上來講,VQuad 在OR 語義上運行的時間比AND 語義長0.2ms,而VGrid 在AND 和OR 語義上的運行時間很近,平均都是0.49ms.這是因為,VQuad 算法的處理單位是虛擬四分樹上的節(jié)點,而VGrid 的處理單位是網(wǎng)格單元.基于虛擬四分樹的VQuad 本質(zhì)上是一種自頂向下的算法,在支持AND 語義時,節(jié)點剪枝效果更明顯,而VGird 本質(zhì)上是基于中心單元的遍歷,所以AND 語義與OR 語義差別不大.

圖19 對比展示了查詢平均處理時間在查詢關(guān)鍵字數(shù)量從1 增加到5 的變化情況.隨著查詢關(guān)鍵字個數(shù)的增加,VQuad 和VGrid 的查詢平均處理時間均有所增加,其原因與支持OR 語義的原因相同,這里不再贅述.在l=1時,AND 語義與OR 語義無差異.當l繼續(xù)增加時,4 條線均在l增加到3 時發(fā)生了陡變.當l增加到4、5 時,增長速率減緩.圖20 對比展示了AND 語義下兩種算法在不同返回結(jié)果個數(shù)k下的變化情況.從圖20 不難發(fā)現(xiàn),兩種算法的平均處理時間大體上均隨著查詢返回結(jié)果的個數(shù)k的增加而增加.從兩組數(shù)據(jù)來看,VGrid 較VQuad 性能更穩(wěn)定.平均來講,在不同數(shù)據(jù)集上,VQuad 的平均查詢處理時間為1.25ms,VGrid 的平均查詢處理時間是0.69ms.圖21 和圖22 對比展示了POI 數(shù)據(jù)集大小、參數(shù)α值變化時算法的性能.兩者的變化趨勢與圖15、圖16 類似,這里也不再贅述.

Fig.18 Performance on different datasets w.r.t AND constraints圖18 不同數(shù)據(jù)集上支持AND 語義的查詢效率

Fig.19 Performance on different number of query keywords w.r.t AND constraints圖19 不同查詢關(guān)鍵字數(shù)量上支持AND 語義的查詢效率

Fig.20 Performance on different number results w.r.t AND constraints圖20 不同查詢結(jié)果數(shù)量上支持AND 語義的查詢效率

Fig.21 Performanceon different size of query datasets w.r.t AND constraints圖21 不同大小的數(shù)據(jù)集上支持AND語義的查詢查詢效率

Fig.22 Performance on different α圖22 不同參數(shù)值α上支持AND 語義的查詢效率

6 總結(jié)

基于位置的地理信息服務(wù)在人們的生活中發(fā)揮著越來越重要的作用,針對空間文本對象查詢的研究成為工業(yè)界和學(xué)術(shù)界關(guān)注的研究熱點問題之一.為了給用戶提供更多高品質(zhì)的選擇結(jié)果,本文針對基于聚集倒排線性四分樹的高效OR 語義的受限Top-k空間關(guān)鍵字查詢的問題進行了研究.綜合考慮空間距離、空間文本相似程度的需求,基于聚集倒排線性四分樹,分別提出基于虛擬四分樹的VQuad 和基于虛擬網(wǎng)格的VGrid 算法.兩種算法均可同時支持AND 語義和OR 語義.通過一系列的實驗發(fā)現(xiàn),由于VGrid 直接利用了線性四分樹上空間編碼的特點,在所有的實驗設(shè)置中其性能均優(yōu)于VQuad 且算法性能更穩(wěn)定.未來考慮將此技術(shù)思想應(yīng)用到在道路網(wǎng)絡(luò)上的查詢研究中.