支持OR語義的高效受限Top-k空間關鍵字查詢技術?

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

1(石家莊鐵道大學 經濟管理學院,河北 石家莊 050043)

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

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

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

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

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

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

綜上所述,本文貢獻總結如下.

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

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

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

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

1 相關工作

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

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

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

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

2 問題的形式化定義

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

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

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

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

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

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

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

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

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

3 倒排聚集線性四分樹AIL

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

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

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

Fig.3 Encoded space圖3 空間編碼

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

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

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

Fig.6 Encoded Morton圖6 Morton 編碼

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

算法1.構建倒排聚集線性四分樹AIL.

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

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

4.1 相關定義

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

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

以圖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對應于查詢q的文本權重不大于R對應于查詢q.T的文本權重,即∑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 算法的基本思想是采用最小最佳優先原則,利用AIL中存儲的空間位置重建虛擬四分樹[16],在虛擬四分樹上尋找滿足OR 語義的空間受限的k最近鄰查詢結果.文獻[16]在虛擬四分樹上進行Top-k關鍵字查詢處理,但其僅實現了AND 語義.VQuad 算法改進了文獻[16]以支持OR 語義的空間受限查詢.下面首先簡要介紹線性四分樹與虛擬四分樹的轉換過程.接下來,在虛擬四分樹的基礎上詳細介紹VQuad 查詢處理方法.

4.2.1 虛擬四分樹

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

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

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

4.2.2 VQuad 算法流程

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

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

4.2.3 運行示例

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

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

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

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

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

4.3 VGird查詢算法

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

(1)VGrid 算法流程

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

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

算法3.基于虛擬網格的OR 語義查詢排序算法VGrid.

這里需要說明兩點:(1)為保證算法的正確性,在算法3 的第15 行中計算虛擬網格中的一個單元到查詢q的空間文本相似性時,單元格關鍵字權重采用的是該關鍵字在空間中的全局最大值;(2)VGrid 算法可同時支持OR 語義和AND 語義.在完成AND 語義查詢時僅需將算法3 中的第7 行修改為被查詢單元或對象是否存在于查詢關鍵字對應的所有線性四分樹即可.

(2)運行實例

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

從棧nbs中取棧頂330.因為330 到查詢點q的距離小于d,取出樹bt1和bt2中330 單元對應的對象,去重后得h={o2}.計算o2與查詢q的空間文本相似性f=0.510,并存入結果集R={(o2,0.510)}.此時,結果集R中對象o2的空間文本相似性大于棧頂元素與查詢q的空間相似性(即0.510＞0.485).根據公式(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}標記為已訪問.由于此時結果集R中o2與查詢q空間文本相似性小于棧頂元素對應的空間文本相似性(即0.510＜0.576).所以,程序終止.輸出的結果集R={(o2,0.510)}.

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

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

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

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

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

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

在公式(5)中,mq是鄰近單元Morton 碼的二進制表示.nq是中心單元code的二進制表示.tx和ty是兩個二進制常數:tx=01...0101 表示“01”重復r次,ty=10...1010 表示“10”重復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由坐標值轉換為Morton 碼(見表3 第2 列).公式(5)采用的是位運算:“+”表示相加;“|”表示OR;“^”表示AND.設線性四分樹劃分深度r=3,計算中心單元303(轉換成二進制為110011)的鄰近8 個單元碼值的過程見表3.

Table 3 Increment of direction表3 方向增量

5 實 驗

5.1 實驗設置

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

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

Fig.10 LA check-in datasets圖10 LA 簽到數據集

Fig.11 NYC check-in datasets圖11 NYC 簽到數據集

Table 4 Statistics for the dataset表4 數據集的統計信息

Table 5 Default setting表5 實驗默認設置

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6 總結

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