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

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

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

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

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

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

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

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

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

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

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

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

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

1 相關(guān)工作

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

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

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

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

2 問題的形式化定義

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

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

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

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

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

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

其中,α(α∈[0,1])是一個(gè)可調(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是用戶可以接受的最遠(yuǎn)距離,k即最近鄰對象個(gè)數(shù),其中,d的優(yōu)先級(jí)比k高.受限Top-k空間關(guān)鍵字查詢即從O中查找在距離d范圍內(nèi)空間文本相似性最高的k個(gè)被查詢對象.其形式化表示見定義4.

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

3 倒排聚集線性四分樹AIL

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

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

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

Fig.6 Encoded Morton圖6 Morton 編碼

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

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

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

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

4.1 相關(guān)定義

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

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

以圖7 為例說明定義5.圖7 顯示了一個(gè)擴(kuò)展的空間文本對象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 擴(kuò)展的空間文本對象R

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

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

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

證明:從空間和文本兩個(gè)角度證明.

從空間的角度,易知對于R中包含的任意對象o,對象o到查詢點(diǎn)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).

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

4.2 VQuad算法

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

4.2.1 虛擬四分樹

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

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

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

4.2.2 VQuad 算法流程

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

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

4.2.3 運(yùn)行示例

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

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

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

Table 1 A running example of VQuad表1 VQuad 算法運(yùn)行實(shí)例

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

4.3 VGird查詢算法

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

(1)VGrid 算法流程

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

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

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

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

(2)運(yùn)行實(shí)例

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

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

Table 2 Running instance of VGRID表2 VGRID 算法運(yùn)行實(shí)例

(3)鄰近8 個(gè)單元的計(jì)算方法

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

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

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

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

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

Table 3 Increment of direction表3 方向增量

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

5.1 實(shí)驗(yàn)設(shè)置

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

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

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)計(jì)信息

Table 5 Default setting表5 實(shí)驗(yàn)?zāi)J(rèn)設(shè)置

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

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

圖13 對比展示了查詢平均處理時(shí)間在不同查詢關(guān)鍵字個(gè)數(shù)l下的變化情況.這里用LVQuad 和LVGrid 分別表示在LA 數(shù)據(jù)集運(yùn)行VQuad 算法和VGrid 算法.NVQuad 和NVGrid 分別表示在NYC 數(shù)據(jù)集上運(yùn)行VQuad算法和VGrid 算法.查詢關(guān)鍵字?jǐn)?shù)量從1 增加到5.隨著查詢關(guān)鍵字個(gè)數(shù)的增加,VQuad 和VGrid 均需要訪問更多的關(guān)鍵字對應(yīng)的線性四分樹,因此查詢平均處理時(shí)間會(huì)隨著關(guān)鍵字個(gè)數(shù)的增加而增加.圖13 印證了我們的想法,兩種算法的查詢平均處理時(shí)間均隨著查詢關(guān)鍵字個(gè)數(shù)的增加亦在增長.然而,兩種算法的增加幅度是逐漸降低的.這是因?yàn)樵贠R 語義環(huán)境下,更多的查詢關(guān)鍵字意味著用戶對查詢需求的放松.線性四分樹中會(huì)有更多的候選結(jié)果供選擇.在k確定的前提下,一定程度地舒緩了查詢時(shí)間的增長幅度.通過對比圖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ù)集上的查詢平均處理時(shí)間

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

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

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

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

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

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

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

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

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

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

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

圖19 對比展示了查詢平均處理時(shí)間在查詢關(guān)鍵字?jǐn)?shù)量從1 增加到5 的變化情況.隨著查詢關(guān)鍵字個(gè)數(shù)的增加,VQuad 和VGrid 的查詢平均處理時(shí)間均有所增加,其原因與支持OR 語義的原因相同,這里不再贅述.在l=1時(shí),AND 語義與OR 語義無差異.當(dāng)l繼續(xù)增加時(shí),4 條線均在l增加到3 時(shí)發(fā)生了陡變.當(dāng)l增加到4、5 時(shí),增長速率減緩.圖20 對比展示了AND 語義下兩種算法在不同返回結(jié)果個(gè)數(shù)k下的變化情況.從圖20 不難發(fā)現(xiàn),兩種算法的平均處理時(shí)間大體上均隨著查詢返回結(jié)果的個(gè)數(shù)k的增加而增加.從兩組數(shù)據(jù)來看,VGrid 較VQuad 性能更穩(wěn)定.平均來講,在不同數(shù)據(jù)集上,VQuad 的平均查詢處理時(shí)間為1.25ms,VGrid 的平均查詢處理時(shí)間是0.69ms.圖21 和圖22 對比展示了POI 數(shù)據(jù)集大小、參數(shù)α值變化時(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)鍵字?jǐ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)注的研究熱點(diǎn)問題之一.為了給用戶提供更多高品質(zhì)的選擇結(jié)果,本文針對基于聚集倒排線性四分樹的高效OR 語義的受限Top-k空間關(guān)鍵字查詢的問題進(jìn)行了研究.綜合考慮空間距離、空間文本相似程度的需求,基于聚集倒排線性四分樹,分別提出基于虛擬四分樹的VQuad 和基于虛擬網(wǎng)格的VGrid 算法.兩種算法均可同時(shí)支持AND 語義和OR 語義.通過一系列的實(shí)驗(yàn)發(fā)現(xiàn),由于VGrid 直接利用了線性四分樹上空間編碼的特點(diǎn),在所有的實(shí)驗(yàn)設(shè)置中其性能均優(yōu)于VQuad 且算法性能更穩(wěn)定.未來考慮將此技術(shù)思想應(yīng)用到在道路網(wǎng)絡(luò)上的查詢研究中.