空間近似關鍵字反遠鄰查詢

邰偉鵬,岳建華,鄧　育,陳業(yè)斌,秦　鋒

(1.中國礦業(yè)大學資源與地球科學學院,江蘇徐州 221116; 2安徽工業(yè)大學計算機與技術學院,安徽馬鞍山 243032)

?

邰偉鵬1,2,岳建華1,鄧育2,陳業(yè)斌2,秦鋒2

(1.中國礦業(yè)大學資源與地球科學學院,江蘇徐州 221116; 2安徽工業(yè)大學計算機與技術學院,安徽馬鞍山 243032)

空間數(shù)據(jù)集中的點普遍由空間信息及描述文本信息組成.空間近似

反遠鄰查詢(Approximate String Reverse Furthest Neighbors Search,ASRFNS)問題是在一個空間數(shù)據(jù)集中搜索所有以給定查詢點為最遠鄰，且滿足文本相似度條件的目標.基于現(xiàn)有的空間反遠鄰查詢算法以及近似

查詢算法，我們提出了兩個基本的解決算法：凸包最遠單元交集(CHFCsJoin) 算法和凸包最遠單元近似字符串串行查詢(CHFCASSS) 算法；我們又設計了一種包含空間和

信息的外存索引結構Filter-Rtree，并給出了相應的凸包最遠單元過濾R樹(CHFilterRtree)高效算法.通過真實數(shù)據(jù)集的實驗測試，驗證這三種算法的有效性，并分析比較了其性能與效率.

近似

查詢；反遠鄰查詢；空間數(shù)據(jù)庫；外存索引

1　引言

RFN作為空間數(shù)據(jù)庫查詢的一部分，近年來逐漸被許多學者深入研究.Bin Yao等人對于單色反遠鄰問題提出的改進的高效算法凸包最遠單元算法(CHFC，the Convex Hull Furthest Cell algorithm)，證明了只有在查詢點位于凸包上或者凸包外側時，查詢點才會有最遠voronoi單元，以凸包求出最遠voronoi單元，進而在R-tree上執(zhí)行一個范圍查詢，可以高效的得到查詢點的反遠鄰[4].而近似字符串查詢算法一直以來都是廣大學者的研究熱點[10～12]，大多數(shù)算法采用q-gram技術，依靠倒排列表來產生候選字符串，相似的字符串之間必然有足夠多相同的gram.基于這個原理， Heap算法和MergeOpt算法，ScanCount算法，MergeSkip算法和DivideSkip算法等高效的近似關鍵字查詢算法被提出，還可以加入長度(length filter)、位置(position filter)、前綴(prefix filter)等字符串過濾器快速排除不符合條件的字符串，進一步提高查詢效率[10,11].

2　問題的定義

空間反遠鄰分為單色反遠鄰(MRFN)和雙色反遠鄰(BRFN)問題，但因其解決方法相似，本文僅以MRFN分析空間近似關鍵字反遠鄰問題.

定義2單色反遠鄰查詢的是指給定一個查詢q,在P中找到所有以q點為最遠鄰的點集，即MRFN(q,P)={p|p∈P,fn(p,P{q})=q}.

定義3給定一個帶字符串的查詢點Q(q,σ)，其中q代表點的坐標信息，σ表示一個字符串，Ε(σ1,σ2)為字符串σ1與σ2之間的編輯距離.則近似字符串反遠鄰查詢是指在P中找出所有以Q點為最遠鄰且字符串與Q.σ滿足給定字符串相似度條件的點集.設編輯距離的閾值為τ，近似字符串反遠鄰查詢可表示為ASRFNS(Q,τ,P)={p|p∈P,fn(p,P{Q})=Q,E(p.σ,Q.σ)≤τ}.

3　ASRFNS問題的基本解決方法

對于空間近似字符串反遠鄰查詢，目前還沒有針對的解決算法.空間查詢的對象是空間數(shù)據(jù)集，而文本查詢對象是文本數(shù)據(jù)集，此二者有獨立的查詢處理方法.針對ASRFNS問題可以通過分別處理空間數(shù)據(jù)與文本數(shù)據(jù)，再結合二者查詢結果的方法來解決.基于上述思路，提出了如下兩種算法.

3.1凸包最遠單元交集算法

3.2凸包最遠單元近似字符串串行查詢算法

凸包最遠單元近似字符串串行查詢(CHFCASSS)算法首先得到查詢點在給定數(shù)據(jù)集上的反遠鄰集合作為候選集，對此，利用現(xiàn)有的CHFC算法，再針對候選的反遠鄰集合執(zhí)行近似字符串查詢算法.

4　ASRFNS問題的高效算法——凸包最遠單元過濾R樹算法

4.1索引結構Filter-Rtree

過濾器的不同使用方法將直接影響到算法的性能優(yōu)劣.首先使用單簽名過濾器，再加入多簽名過濾器.

4.2查詢算法

由于查詢算法同樣是基于凸包，求出查詢點的最遠voronoi單元，所以將此算法命名為凸包最遠單元過濾R樹算法(CHFilterRtree).同前兩種算法一樣，首先需要通過給定的查詢點位置信息和數(shù)據(jù)集得到查詢點的最遠voronoi單元.再以這個voronoi單元為一個查詢范圍配合所要求的查詢關鍵字及閾值在Filter-Rtree上執(zhí)行近似關鍵字范圍查詢.

算法1CHFilterRtree(Query Q(q,σ),int τ)

1.LetLbe a FIFO queue initialized to ?;

2.Set FvcSet=?,ResultSet=?;

3./*第1步：先執(zhí)行空間部分的查詢，得到Q在數(shù)據(jù)集P中所有的反遠鄰集合FvcSet */

4.Compute convex hullCPof datasetP;

5.ifQ?CPthen return ?;

6.else

7.ComputeCP*usingCP∪{Q};

8.Set fvc (Q,P*) equal to fvc(Q,CP*);

9./*第2步：為數(shù)據(jù)集P構建Filter-Rtree FRT*/

10.Create Filter-Rtree FRT of datasetP;

12.Letube the root node of FRT;

for every child entryciofudo

13.LetLbe a FIFO queue initialized to ?;

14.LetLbe a FIFO queue initialized to ?;

15.Set FvcSet=?,ResultSet=?;

16./*第1步：先執(zhí)行空間部分的查詢，得到Q在數(shù)據(jù)集P中所有的反遠鄰集合FvcSet */

17.Compute convex hullCPof datasetP;

18.ifQ?CPthen return ?;

19.else

20.ComputeCP*usingCP∪{Q};

21.Setfvc(Q,P*) equal to fvc(Q,CP*);

22./*第2步：為數(shù)據(jù)集P構建Filter-Rtree FRT*/

23.Create Filter-Rtree FRT of datasetP;

25.Letube the root node of FRT;

26.for every child entryciofudo

27.If |ci|≥|Q.σ-τ| and |ci|≤|Q.σ+τ| then

28.Insert the child nodeuiintoL;

29.WhileLis not empty do

30.Pop the head entryeofL;

31.Ifeis a leaf node then

32.Ife∩fvc(Q,P*)≠? then

33.Let list be the inverted list contained bye;

34.Letp1，…，pfbe the results after performing an approximate string search merging algorithm(e.g.,MergeSkip algorithm) with list;

35.Fori=1,…,fdo

36.Ifpiis contained in fvc(Q，P*) then

37.Insertpinto ResultSet;

38.Else

39.Letw1,…,wfbe children MBRs of nodee;

40.Fori=1,…,fdo

41.Ifwi∩fvc(Q，P*)≠? then

42.Insert the child nodewiintoL;

ReturnResultSet;

CHFilterRtree算法求出數(shù)據(jù)集P的凸包，判斷查詢點q的位置是否在凸包內部，如果在，說明查詢點在數(shù)據(jù)集P上不存在反遠鄰，返回空集；否則繼續(xù).利用得到的凸包計算查詢點q的最遠voronoi單元，這個單元將作為查詢區(qū)域作用于其后的Filter-Rtree上.為數(shù)據(jù)集P創(chuàng)建Filter-Rtree，整個Filter-Rtree結構存儲于外存中.Filter-Rtree的第一層根據(jù)查詢關鍵字的長度剔除掉那些不可能滿足閾值條件的點；滿足條件的關鍵字長度分別對應著一個Rtree子樹，在各個Rtree子樹上以之前得到的最遠voronoi單元執(zhí)行空間范圍查詢，找到與單元相交的Rtree葉子結點，再根據(jù)position filter取出我們想要的倒排列表，分別對每個倒排列表執(zhí)行近似關鍵字查詢合并算法，分別判斷所得關鍵字匹配點是否在最遠voronoi單元中，如果是，則點是要找的最終結果，即查詢點的一個近似關鍵字反遠鄰對象.

5　實驗結果與分析

5.1實驗設置

測試平臺為一臺PC機，配置為i5-2400四核CPU，主頻為2.80GHz，8GB內存；7200轉500GB硬盤，系統(tǒng)為Linux.算法由GNU C++語言編程實現(xiàn).磁盤頁面大小為4KB.實驗使用的真實數(shù)據(jù)集CA來自開源項目Open Street Map Project，包含1,983,155條元組，每個元組包含一個標識，一個二維坐標和一組字符串描述文本.

5.2預處理結果分析

三種算法預處理時都要構建外存空間索引，其中，CHFCsJoin和CHFCASS是串行處理方式，在空間查詢部分構建的是傳統(tǒng)的Rtree索引，而CHFilterRtree算法則需要構建FilterRtree.對CA數(shù)據(jù)集預處理，分別構建索引，記錄其所占空間及構建時間，實驗次數(shù)為3次，取記錄的均值，如表1所示.

表1　索引構建代價

從表1可以看出，F(xiàn)ilterRtree索引較傳統(tǒng)Rtree索引占更多地外存空間，構建時間也明顯高于Rtree，這是由于FilterRtree將記錄關鍵字信息的倒排列表加入到R-tree中，還加入了特定的Filter.而在FilterRtree加入兩種過濾器的構建代價也要明顯大于只加入一種過濾器.由于FilterRtree索引是外存索引，構建的代價較大，其插入更新的代價也很大，因此，此適用于更新周期較長的數(shù)據(jù)集，每次數(shù)據(jù)集更新，索引將被重新創(chuàng)建.

5.3查詢結果分析

考慮到圖3中在處理倒排列表時，使用了基礎的Heap算法.使用在處理性能上更優(yōu)的MergeSkip算法，試圖提高三種算法查詢性能.從圖5可以看出，采用MergeSkip算法處理字符串數(shù)據(jù)的方法可以有效減少三種算法的查詢時間，提高算法性能，而對CHFCsJoin算法的影響尤為顯著.這是由于CHFCsJoin算法首先處理全部查詢點的文本數(shù)據(jù)，文本數(shù)據(jù)量很大，MergeSkip算法的優(yōu)越性得到了較好的體現(xiàn)，而CHFCASSS算法是對滿足空間條件的點處理其文本信息，數(shù)據(jù)量相對小的多，MergeSkip算法效果不明顯，CHFilterRtree算法采用Filter-Rtree索引結構，查詢性能明顯優(yōu)于之前兩種算法，而因其分批處理倒排列表，倒排列表的規(guī)模很小，Heap算法和MergeSkip算法對其查詢性能的影響忽略不計.

在倒排列表索引中加入不同的過濾器也會最終影響三種算法的查詢性能.如圖6所示，無論是在處理倒排列表時采用Heap或MergeSkip算法，僅加入了Length過濾器的效率要略優(yōu)于加入Length和Postion過濾器，這也驗證了文獻[11]所指出的過濾器的使用原則，即過濾器并非加入的越多越好，過濾器的加入具有數(shù)據(jù)集相關性，不同的數(shù)據(jù)集可能有不同的過濾器最優(yōu)搭配方式.

6　結論

[1]Feifei Li,Bin Yao,Mingwang Tang,et al.Spatial approximate string search[J].TKDE,2013,25(6):1394-1409.

Wang Jin-bao,Gao Hong,Li Jian-zhong,et al.Index supporting spatial approximate keyword search on disks[J].Journal of Computer Research and Development,2012,49(10):2142-2152.(in Chinese)

[3]Jiaheng Lu,Ying Lu,Gao Cong.Reverse spatial and textualknearest neighbor search[A].SIGMOD 2011[C].Athens:ACM,2011.349-360.

[4]Bin Yao,Feifei Li,Piyush Kumar.Reverse furthest neighbors in spatial databases[A].Proceedings of the 25th International Conference on Data Engineering[C].Shanghai:IEEE,2009.664-675.

[5]Gísli R Hjaltason,Hanan Samet.Distance browsing in spatial databases[J].ACM Trans Database System,1999,24(2):265-318.

[6]Bin Yao,Feifei Li,Piyush Kumar.Knearest neighbor queries and KNN-Joins in large relational databases (almost) for free[A].Proceedings of the 26th International Conference on Data Engineering[C].Long Beach:IEEE,2010.4-15.

[7]Flip Korn,Suresh Muthukrishnan.Influence sets based on reverse nearest neighbor queries[A].SIGMOD 2000[C].Dallas:ACM,2000.201-212.

[8]Rimantas Benetis,Christian S Jensen,Gytis Karciauskas,et al.Nearest and reverse nearest neighbor queries for moving objects[J].The VLDB Journal,2006,15(3):229-249.

[9]蔣濤,高云君,張彬,等.不確定數(shù)據(jù)查詢處理[J].電子學報,2013,41(5):966-976.

Jiang Tao,Gao Yun-jun,Zhang Bin,et al.Query processing on uncertain data[J].Acta Electronica Sinica,2013,41(5):966-976.(in Chinese)

[10]Sunita Sarawagi,Alok Kirpal.Efficient set joins on similarity predicate[A].SIGMOD 2004[C].Paris:ACM,2004.743-754.

[11]Chen Li,Jiaheng Lu,Yiming Lu.Efficient merging and filtering algorithms for approximate string searches[A].Proceedings of the 24th International Conference on Data Engineering[C].Cancún:IEEE,2008.257-266.

[12]Ian De Felipe,Vagelis Hristidis,Naphtali Rishe.Keyword search on spatial databases[A].Proceedings of the 24th International Conference on Data Engineering[C].Cancún:IEEE,2008.656-665.

邰偉鵬男，1979生出生于安徽馬鞍山，博士研究生，副教授.研究方向為時空數(shù)據(jù)庫、移動互聯(lián)網.

E-mail:taiweipeng@ahut.edu.cn

岳建華男，1964年出生于山東濟寧，教授，博士生導師，研究方向為地球物理，GIS系統(tǒng).

鄧育男，1990年出生于安徽六安，碩士研究生.研究方向為時空數(shù)據(jù)庫.

陳業(yè)斌男，1971年出生于安徽滁州，教授.研究方向為時空數(shù)據(jù)庫.

秦鋒男，1962年出生于安徽馬鞍山，教授.研究方向為人工智能.

Approximate String Reverse Furthest Neighbors Search

TAI Wei-peng1,2,YUE Jian-hua1,DENG Yu2,CHEN Ye-bin2,QIN Feng2

(1.SchooloftheEarthScienceandResources,ChinaUniversityofMiningandTechnology,Xuzhou,Jiangsu221008,China;2.SchoolofComputerScience,AnhuiUniversityofTechnology,Ma’anshan,Anhui243032,China)

The points of spatial dataset usually consist of the spatial information and the described text information.The problem of approximate string reverse furthest neighbors search(ASRFNS) query is defined to search all points in a spatial dataset that take the given query point as its furthest neighbor while their text satisfies the string similarity constraint.Based on the existing reverse furthest neighbors search algorithm and approximate string search algorithm,we proposed two solution algorithms:the convex hull furthest cells join algorithm(CHFCsJoin) and the convex hull furthest cell approximate string serial search algorithm(CHFCASSS).In order to further improve the query performance,we also proposed an efficient algorithm of the convex hull furthest cell filter-Rtree(CHFilterRtree) which contains disk resident structure of space and keyword information.With the real dataset experiments and analysis,the results demonstrate that our proposed algorithms obtained a good performance.

approximate string search;reverse furthest neighbors search;spatial database;disk resident index

2014-10-15；修回日期：2014-04-12；責任編輯：梅志強

國家自然科學基金項目(No.61003311);安徽高校省級自然科學研究重大項目(No.KJ2014ZD05);安徽高校省級自然科學研究重點項目(No.KJ2013Z023,No.KJ2013A058);安徽省振興計劃資助項目(No.2013ZDJY073)

TP311

A

0372-2112 (2016)06-1343-06