支持空間數(shù)據(jù)移動查詢的索引研究

張素智,趙亞楠,楊 芮

(鄭州輕工業(yè)學院 計算機與通信工程學院,鄭州 450002)

支持空間數(shù)據(jù)移動查詢的索引研究

張素智,趙亞楠,楊 芮

(鄭州輕工業(yè)學院 計算機與通信工程學院,鄭州 450002)

隨著智能移動設(shè)備的普及,空間數(shù)據(jù)也隨之呈現(xiàn)出幾何級增長,結(jié)合空間對象位置和關(guān)鍵字的查詢越來越受到人們的關(guān)注.然而,在之前的大量研究中多是假設(shè)空間詞為不變的,但是在實際生活中,空間對象的位置有許多是移動的,這就可能導致查詢結(jié)果不符合實際需求.針對上述狀況,提出一種支持移動空間關(guān)鍵詞查詢方法.經(jīng)實驗驗證,該方法具備一定的實用性,且查詢效率有較大的提高.

空間數(shù)據(jù)；移動空間詞查詢；APR-tree；空間關(guān)鍵詞

近年來隨著具有定位功能的智能移動設(shè)備的大量普及使用,產(chǎn)生出海量的數(shù)據(jù),這些數(shù)據(jù)往往具備地理位置和文本內(nèi)容雙重屬性,例如：在微博或是Twitter中發(fā)布用戶所處的地理位置、影院、景點等網(wǎng)頁中會附加位置信息及簽到功能等.隨著基于位置服務(wù)的飛速發(fā)展,空間關(guān)鍵詞查詢也越來越受到學術(shù)界的關(guān)注,漸成為科技前沿,人們對基于位置服務(wù)的要求也是越來越高.如圖1所示,在一個較大的商業(yè)區(qū)內(nèi),u1,u2,u3分別表示不同的用戶,各自有著不同的關(guān)注點.e1,e2表示兩戶商家.以u1為例,他對打折的ipad很有興趣,在搜索查詢附近符合要求的商家.u1在移動過程中e1,e2進入其查詢范圍,e1就被推送給u1.

但是實際情況卻更為復雜,首先用戶的數(shù)量會是萬級的；其次數(shù)據(jù)庫內(nèi)的待查詢信息可能會出現(xiàn)重復或部分重復現(xiàn)象；最后,用戶不可能一直處于靜止狀態(tài),因此移動時的查詢也需關(guān)注.

1 問題的形式化描述

1.1問題來源

作為前沿科技,空間關(guān)鍵詞查詢還處于初步階段,但是經(jīng)過眾多學者的研究還是取得了一定的成果.現(xiàn)有的查詢方法多是把空間索引和文本索引[1]結(jié)合起來重構(gòu)對象結(jié)構(gòu)之后實現(xiàn)對空間和文本的剪枝處理,以便快速查詢.Yao等[2]提出的MHR-tree,在這之前的索引結(jié)構(gòu)只支持精確匹配查詢,MHR-tree索引首次將近似串匹配(approximate string matching,ASM)引入空間查詢當中,并在每個樹節(jié)點中加入min-wise簽名對查詢結(jié)果進行剪枝,但該簽名數(shù)據(jù)沒有質(zhì)量保證,結(jié)果返回率較??；Hu等[3]將近似匹配應(yīng)用到周邊查詢,但是他們都是單關(guān)鍵詞查詢;而Xv等[4]又提出多關(guān)鍵詞模糊查詢,可以實現(xiàn)多個不同關(guān)鍵詞的相關(guān)的查詢,然而其查詢速度不高.而且上述工作都是假設(shè)用戶處于靜止的環(huán)境下實現(xiàn)的,對于動態(tài)環(huán)境下的查詢幾乎沒有研究.

就目前來說,Guo等[5]的研究是相對較好的,最近他們提出一個解決此類問題的框架,稱為Elaps,它的主要作用是通過使用safe-zone技術(shù)和區(qū)域影響技術(shù)來減少用戶和服務(wù)器之間的通訊代價.本文所做的工作和上述有個很大的不同點,就是讓用戶不斷的標注出自己的位置,以便中央服務(wù)器更新用戶的空間位置信息,實時更新查詢結(jié)果.盡管Elaps使用了BEQ-Tree[7]作為索引來減少通訊代價,但是該方法占用了較大的內(nèi)存和計算資源.本文的主要工作是建立更高效的索引結(jié)構(gòu)APR-tree實現(xiàn)快速查詢,從而提升效能比.

1.2預備工作

在給定的空間數(shù)據(jù)集中,M代表總空間文本信息集,m代表一個空間文本信息,(m1,m2,...mi)∈M.該信息是帶有地理位置信息的,比如簽到位置和地理標記.那么,一條空間文本信息m可以模式化表示為m = (ψ,loc),其中m.ψ表示關(guān)鍵詞詞匯集V中明確存在的關(guān)鍵詞集,m.loc表示位置.各個字符表示的具體含義如表1所示.

表1 字符含義

這里,一個空間關(guān)鍵詞查閱s被表示為s=(ψ,r),其中s.ψ是用戶指定要查詢的關(guān)鍵詞集,s.r是一個矩形區(qū)域.s是被長時間持續(xù)查詢的,除非用戶自主終止該項查詢.本文所提的對空間文本信息的空間關(guān)鍵詞查詢是當它符合空間和文本雙重約束條件后的匹配查詢.

定義1 當且僅當滿足以下條件時,輸入的空間文本信息才會被作為約束條件去執(zhí)行查詢,即m.ψ?s.ψ,m.loc∈s.r.

對于輸入的信息流,本文用處理固定空間關(guān)鍵詞的方法[8]來處理,具體如圖2所示,有9個空間關(guān)鍵詞查詢集合{s1,s2...s9}和兩條文本信息{m1,m2}.m1處于{s1,s2,s4,s7}的查詢范圍之內(nèi),但是它的關(guān)鍵詞只符合s7,那么m1就推送給{s7}.基于同樣的機理,m2匹配到{s1,s4}.

圖2 POI點位置分布Fig.2 Distribution of POI points

2 APR-tree基本框架

結(jié)合MHR-tree索引和R+樹[10]索引,提出一種全新的自適應(yīng)索引結(jié)構(gòu)去組織空間數(shù)據(jù),稱為APR-tree.

2.1設(shè)計要求

移動智能應(yīng)用的大量普及意味著訪問數(shù)據(jù)的激增,那么如何盡可能用較低的代價、快速地得出結(jié)果是研究的重點.

1)可適應(yīng)性.對現(xiàn)有的資料研究發(fā)現(xiàn),空間關(guān)鍵詞查詢索引主要分為文本優(yōu)先和空間優(yōu)先兩種方式,根據(jù)文本不同的表述,空間部分和關(guān)鍵詞部分都可能成為索引的關(guān)鍵因子.但是,對于那些關(guān)鍵詞有大量重復的查詢集,如果預先使用IQ-tree[11]構(gòu)建空間優(yōu)先索引,雖然子節(jié)點部分也考慮了文本約束,然而通過實驗發(fā)現(xiàn)其查詢效果并不理想.類似地,文本優(yōu)先索引RQ-tree[12]也可能遭遇類似的問題.這促使構(gòu)建新的結(jié)構(gòu)去動態(tài)適應(yīng)不同情行,該結(jié)構(gòu)根據(jù)空間文本信息的特征分成空間部分和關(guān)鍵詞部分.由空間詞組成的節(jié)點分段稱為S-node(另一個稱為K-node),通過建立的代價公式來判斷優(yōu)先使用哪種方式來構(gòu)建節(jié)點.

2)空間部分(spatial partition).本文研究的空間位置數(shù)據(jù)都是二維的,經(jīng)過分析后Quadtree[13]和R+-tree被引入,因為Quadtree可以使關(guān)鍵詞不產(chǎn)生交集,R+-tree可以給每個查詢集一個單獨的區(qū)域.另外每一個S-node其在索引結(jié)構(gòu)內(nèi)的位置都經(jīng)過代價模型計算得出,具體如圖3所示.

3)文本詞部分(keyword partition).簡單的說就是通過給定的文本信息找到對應(yīng)關(guān)鍵詞的位置,使用有序樹[14]因為它對處理具有相同前綴的關(guān)鍵詞組是有較大優(yōu)勢,另外它是分層的樹形結(jié)構(gòu).同空間部分一樣,樹中所有相關(guān)的關(guān)鍵詞節(jié)點也都經(jīng)過模型計算,具體結(jié)構(gòu)如圖4所示.

對于每個K-node,為了防止因提交的關(guān)鍵詞數(shù)量不夠從而造成查詢集無法分割,即s.ψlt;Nl,采用虛擬分割(dummy cut)保存所有的關(guān)鍵詞.每個S-node N有一個dummy cell包含N的區(qū)域,因此不需要在節(jié)點上進行進一步的剪切.

2.2 APR-tree索引結(jié)構(gòu)

圖5 APR-tree基本結(jié)構(gòu)Fig.5 APR-Tree basic structure

在移動空間關(guān)鍵詞查詢中,因為需要對信息進行更新所以對空間文本信息進行重新定義表示為m=(ψ,loc,tc,te),其中tc和te分別表示在一個時間戳t內(nèi)m的產(chǎn)生時間和有效期,其余的屬性沒變.那么根據(jù)以上的敘述可以建立出APR-tree框架,如圖5所示.它使用spatial partition 和 keyword partition的方法自上而下地分割空間數(shù)據(jù),每個查詢信息按照各自的關(guān)鍵詞和查詢范圍被分配給一個或多個葉子節(jié)點,每個葉子節(jié)點里面的查詢信息用地圖結(jié)構(gòu)組織起來稱作S-list,以便插入或刪除信息.m-list用來存儲那些在查詢過程中被訪問過的L-node信息,一個m-list里基本上都是與查詢信息(被存放到L-node內(nèi)的)相關(guān)的內(nèi)容.

2.3 APR-tree的構(gòu)造

給定一個空間數(shù)據(jù)集S,APR-tree是由自上而下構(gòu)建而成的,因此需要通過代價模型來評估采用spatial partition或keyword partition來自適應(yīng)查詢工作的需要.

(1)

用B表示spatial(keyword)partition的一個單元節(jié)點,w(B)是B的權(quán)重,p(B)表示該單元在查詢過程中被命中的概率.rm表示在一個時間戳內(nèi)信息變化的比率,可以通過歷史數(shù)據(jù)獲得,在本文中設(shè)置為1.其中w(b)可以用改進的TF-IDF模型[15]得到：

(2)

其中tfw,d表示查詢詞在數(shù)據(jù)集中出現(xiàn)次數(shù),權(quán)重值與出現(xiàn)次數(shù)成正比,idfw,D,S表示在僅查詢詞組|D,S|中某個關(guān)鍵詞出現(xiàn)次數(shù)的倒數(shù).wmax表示該關(guān)鍵詞最大權(quán)重值.

(3)

式(3)中p(w)表示關(guān)鍵詞w的命中概率,f(w)表示w在整個S中出現(xiàn)的頻率.

(4)

(5)

其中:w(wj)表示S中第L個關(guān)鍵詞是wj的次數(shù)和該關(guān)鍵詞權(quán)重的乘積,p(wj)是關(guān)鍵詞wj的命中概率.算法1描述了最優(yōu)keyword partition 程序設(shè)計方式.

算法1：GetKeywordpartition

輸入：V：被分割的關(guān)鍵詞集

f:分割的單元數(shù)

輸出：pk 最優(yōu)關(guān)鍵詞部分

1 for 1 lt;= i lt;= V

2 compute C(Pk*(i,j,1)); // 公式5

3 for 2 lt;= c lt;= f-1{

4 for 1 lt;= i lt;= V+1-c

5 compute C(Pk*(i,V,c)); // 公式4

6 }

7 compute C(Pk*(1,V,f)); //公式4

8 return Pk*(1,V,f);

這里,第1,2行計算出每個partition被分割成只有一個單元的代價,然后在第3,4,5行計算出分解成帶有c個單元時的最優(yōu)結(jié)果,最后得出整體的最優(yōu)結(jié)構(gòu),時間復雜度O(f*V2).

2.3.2 空間部分 這里,假定f=x * y,PS表示節(jié)點N的某一部分,而這個部分的區(qū)域被分割映射到一個x*y網(wǎng)格單元中,

由式(6)可以得到在節(jié)點N上的某個部分PS的代價.

(6)

(7)

從而使得C(Ps)lt;= 1,也就實現(xiàn)了每個單元內(nèi)只有一個查詢詞的目的.實際上需要有個工作不能忽略,移動查詢在位置信息更新時會有產(chǎn)生一定的代價,那么可以評估它在完全離開它原來所在節(jié)點N的代價：

CLM=2×lpath×logf

(8)

Lpath是從根節(jié)點在當前節(jié)點N的路徑長度,logf是在這個路徑上定位每個分割單元的代價,至于乘2則是因為更新有插入和刪除兩個操作.

結(jié)合以上的工作,可以由算法2簡要說明APR-tree的構(gòu)建.

算法2： IndexConstruction(N,S,l,kP,sP)

輸入：N：當前節(jié)點,S：一個查詢集

l:在N節(jié)點里的關(guān)鍵詞部分的偏移量

kP和sP:選取標記,用于選擇keyword或spatial partition

輸出：APR-tree

1 if(kP == falseamp;amp;sP==false){

2 Construct N as a l-node,and add S to the m-list;

3 return;

4 }

5 Ck:= +∞;Cs=+∞;

6 if(kP is true)

7 Cklt;-keyword partition on S with offset l;

8 if (sP is true)

9 Cs lt;-- spatial partition on S;

10 if (keyword partition is chosen|| Cklt;Cs){

11 Construct N as a K-node with node offset Nl:=l;

12 S'lt;- subscriptions {s} in S with |s.|lt;l;

13 B'lt;-dummy cut of N;

14 IndexConstruction(B',S',l+1,kP:=false,sP);

15 for each child node B of N{

16 SBlt;-subscription in s-s' which hit the cut B;

17 IndexConstruction(B,SB,l+1,kP,sP);

18 }

19 }

20 else{

21 Construct N as a S-node

22 S'lt;- subscription in S which contain Nr;

23 B'lt;-dummy cut of N;

24 indexConstruction(B',S',l,kP,sP:=false);

25 for each child node B of N{

26 SBlt;-subscription in s-s' which contain or overlap B;

27 IndexConstruction(B,SB,l,kP,sP);

28 }}

這里主要分為兩個部分,首先第1行到第5行,先進行初始化,準備好將要使用的鏈表,以及把空間和文本權(quán)重值設(shè)為無窮大.然后依據(jù)權(quán)重值的不同依次做不同的操作,第6行判斷出是文本詞的標志位為真,即這里文本描述的權(quán)重較大,則有第7至第19行構(gòu)建k-node,同理,在第20行至第26行構(gòu)建出s-node.迭代循環(huán)直至所有的點都被訪問之后返回構(gòu)建好的ARP-tree索引結(jié)構(gòu).

3 實驗結(jié)果與分析

圖6 參數(shù)值f取值對運行時間的影響Fig.6 The effect of the parameter value f on the run time

實驗環(huán)境為Inter(R)Core CPU 3.4GHz,4G內(nèi)存,操作系統(tǒng)為win 10,實驗數(shù)據(jù)是由購物街11 243個空間數(shù)據(jù)和396個不同的關(guān)鍵詞集合組成,包含商店及餐廳的信息.查詢關(guān)鍵詞個數(shù)j在1到5之間隨機選擇,查詢范圍是以查詢信息的地理位置為中心的矩形,其區(qū)域大小是均勻地選擇在0.01%和1%之間的數(shù)據(jù)空間.

實驗中首先評估f對測試的影響,通常來說,f太小會造成每個K-node的分割單元太小而無法充分利用keyword partition,f太大又有可能使APR-tree的適用性降低.圖6表示隨著f從50增長400,平均運行時間的變化情況,由實驗結(jié)果將f設(shè)置成200.

如圖7所示,隨著關(guān)鍵詞個數(shù)在1到5之間變換APR-tree、空間優(yōu)先索引IQ-tree和文本優(yōu)先索引RQ-tree的查詢時間是不同的.當只有一個關(guān)鍵詞時,因為需要匹配的項目太多造成查詢時間較長,但是隨著關(guān)鍵詞個數(shù)增加明顯可以看出前者具有較大的優(yōu)勢,說明其對文本的剪枝效果較好.

圖8表示隨著查詢范圍的變化不同索引結(jié)構(gòu)查詢所用時間的情況,其中APR-tree表現(xiàn)較其他兩者有明顯優(yōu)勢且表現(xiàn)也較為穩(wěn)定.同時可以看出當查詢范圍較小時IQ-tree比RQ-tree好,但是隨著范圍增長則呈現(xiàn)出相反的狀態(tài),說明查詢范圍較小時,空間優(yōu)先結(jié)構(gòu)更有利.

圖7 關(guān)鍵詞個數(shù)對運行時間的影響 圖8 查詢范圍對運行時間的影響

4 結(jié)語

本文根據(jù)實際使用需要,提出一個面向移動空間關(guān)鍵詞查詢的方法,并設(shè)計出代價模型,引入權(quán)重值、命中概率等多種參數(shù).相較傳統(tǒng)的單一優(yōu)先結(jié)構(gòu),APR-tree表現(xiàn)更為高效.最后通過實驗結(jié)果證明,與以往的索引方式相比較,在查詢效率上有較大的提高.

[1] 劉喜平,萬常選,劉德喜,等.空間關(guān)鍵詞搜索研究綜述[J].軟件學報,2016,27(2):329-347.

[2] YAO B,LI F F,HADJIELEFTHERIOU M,et al.Approximate string search in spatial databases[C]//Proc of the ICDE,Washington :IEEE,2010.545-556.

[3] HU J,FAN J,LI GL,et al.Top-k fuzzy spatial keyword search[C]//Chinese Journal of Computers,2012,35(11):2237-2246.

[4] XV J,ZHANG S Z.Research on fuzzy matching query alogorithm based on spatial multi keywords[C]//Chinese Journal of Computers,2016,35(11):223-231.

[5] ALSUBAIEE S,BEHM A,LI C.Supporting location-based approximate keyword queries[C]// Proc of the SIGSPATIAL GIS.New York:ACM Press,2010:61-70.

[6] WANG J B,GAO H,LI J Z,et al.An index supporting spatial approximate keyword search on disks[J].Journal of Computer Research and Development,2012,49(10) :2142-2152.

[7] 胡俊,范佳明.空間數(shù)據(jù)上的Top-k模糊查詢研究[就].計算機學報,2012,35(11):2237-2246.

[8] ZHANG D X,CHEN Y M,MONDAL A,et,al.Keyword search in spatial databases:to-wards searching by document[C]//Proceeding of the 2009 IEEE international confe-rence Data Engineering Washington,DC:IEEE,ComputerSociety,2009:688-699.

[9] CAO X,CONG G J L,JENSEN C S,et al.Collective spatial keyword querying[C]// Proceedings of the 2011 ACM SIGMOD,International Conference on Management of Data.New York:ACM,2011:373-384.

[10] 徐明.基于節(jié)點分裂優(yōu)化的R-樹索引結(jié)構(gòu)[J].計算機應(yīng)用研究,2016,33(12):3530-3534.

[11] 王金寶,高宏,李建中,等.RB樹:一種支持空間近似關(guān)鍵字查詢的外存索引[J].計算機研究與發(fā)展,2012,49(10):2142-2152.

[12] 易顯天,徐展,郭承軍,等.基于Patricia樹的空間索引結(jié)構(gòu)[J].計算機工程，2015,41(12):68-74.

[13] 路煒,張宇,周美孜,等.高性能文本索引系統(tǒng)的設(shè)計與實現(xiàn)[J].中國科技論壇，2014(1):92-95.

[14] 特日根,李巍,李雄飛.動態(tài)有序樹存儲模型與實現(xiàn)方法[J].計算機研究與發(fā)展,2013,50(5):969-985.

[15] 路永和,李焰鋒.改進TF-IDF算法的文本特征項權(quán)值計算方法[J].圖書情報工作,2013,57(3):90-95.

責任編輯：高山

ResearchonMatchingQueryBasedonMovingSpatialKeywords

ZHANG Suzhi，ZHAO Yanan,YANG Rui

(School of Computer and Communication Engineering,Zhengzhou University of Light Industry,Zhengzhou 450002,China)

Along with the popularization of intelligent mobile devices,the spatial data also present a geometric growth.With the query of spatial object position and keywords,more and more people pay attention to it.However,in previous studies,it is assumed that the spatial keywords are invariant,but in real life,many of the spatial objects are moved,which may make the query results fail to meet the actual needs.Aiming at the above situation,this paper proposes a query method to support mobile space keywords.The experiments show that the proposed method has some practicality,and the query accuracy has been greatly improved.

spatial data;moving spatial word query;APR-tree;spatial keywords

2017-04-16.

國家自然科學基金項目(61672470)

張素智(1965-),男,博士,教授,主要從事Web數(shù)據(jù)庫、分布式計算和異構(gòu)系統(tǒng)集成的研究.

1008-8423(2017)04-0423-06

10.13501/j.cnki.42-1569/n.2017.12.016

TP391

A

圖1 服務(wù)實例
Fig.1 Service example