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

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

?

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

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

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

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

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

信息的外存索引結(jié)構(gòu)Filter-Rtree，并給出了相應(yīng)的凸包最遠(yuǎn)單元過(guò)濾R樹(shù)(CHFilterRtree)高效算法.通過(guò)真實(shí)數(shù)據(jù)集的實(shí)驗(yàn)測(cè)試，驗(yàn)證這三種算法的有效性，并分析比較了其性能與效率.

近似

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

1　引言

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

2　問(wèn)題的定義

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

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

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

3　ASRFNS問(wèn)題的基本解決方法

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

3.1凸包最遠(yuǎn)單元交集算法

3.2凸包最遠(yuǎn)單元近似字符串串行查詢算法

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

4　ASRFNS問(wèn)題的高效算法——凸包最遠(yuǎn)單元過(guò)濾R樹(shù)算法

4.1索引結(jié)構(gòu)Filter-Rtree

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

4.2查詢算法

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

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

1.LetLbe a FIFO queue initialized to ?;

2.Set FvcSet=?,ResultSet=?;

3./*第1步：先執(zhí)行空間部分的查詢，得到Q在數(shù)據(jù)集P中所有的反遠(yuǎn)鄰集合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構(gòu)建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中所有的反遠(yuǎn)鄰集合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構(gòu)建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的凸包，判斷查詢點(diǎn)q的位置是否在凸包內(nèi)部，如果在，說(shuō)明查詢點(diǎn)在數(shù)據(jù)集P上不存在反遠(yuǎn)鄰，返回空集；否則繼續(xù).利用得到的凸包計(jì)算查詢點(diǎn)q的最遠(yuǎn)voronoi單元，這個(gè)單元將作為查詢區(qū)域作用于其后的Filter-Rtree上.為數(shù)據(jù)集P創(chuàng)建Filter-Rtree，整個(gè)Filter-Rtree結(jié)構(gòu)存儲(chǔ)于外存中.Filter-Rtree的第一層根據(jù)查詢關(guān)鍵字的長(zhǎng)度剔除掉那些不可能滿足閾值條件的點(diǎn)；滿足條件的關(guān)鍵字長(zhǎng)度分別對(duì)應(yīng)著一個(gè)Rtree子樹(shù)，在各個(gè)Rtree子樹(shù)上以之前得到的最遠(yuǎn)voronoi單元執(zhí)行空間范圍查詢，找到與單元相交的Rtree葉子結(jié)點(diǎn)，再根據(jù)position filter取出我們想要的倒排列表，分別對(duì)每個(gè)倒排列表執(zhí)行近似關(guān)鍵字查詢合并算法，分別判斷所得關(guān)鍵字匹配點(diǎn)是否在最遠(yuǎn)voronoi單元中，如果是，則點(diǎn)是要找的最終結(jié)果，即查詢點(diǎn)的一個(gè)近似關(guān)鍵字反遠(yuǎn)鄰對(duì)象.

5　實(shí)驗(yàn)結(jié)果與分析

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

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

5.2預(yù)處理結(jié)果分析

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

表1　索引構(gòu)建代價(jià)

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

5.3查詢結(jié)果分析

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

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

6　結(jié)論

[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].電子學(xué)報(bào),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生出生于安徽馬鞍山，博士研究生，副教授.研究方向?yàn)闀r(shí)空數(shù)據(jù)庫(kù)、移動(dòng)互聯(lián)網(wǎng).

E-mail:taiweipeng@ahut.edu.cn

岳建華男，1964年出生于山東濟(jì)寧，教授，博士生導(dǎo)師，研究方向?yàn)榈厍蛭锢恚珿IS系統(tǒng).

鄧育男，1990年出生于安徽六安，碩士研究生.研究方向?yàn)闀r(shí)空數(shù)據(jù)庫(kù).

陳業(yè)斌男，1971年出生于安徽滁州，教授.研究方向?yàn)闀r(shí)空數(shù)據(jù)庫(kù).

秦鋒男，1962年出生于安徽馬鞍山，教授.研究方向?yàn)槿斯ぶ悄?

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；責(zé)任編輯：梅志強(qiáng)

國(guó)家自然科學(xué)基金項(xiàng)目(No.61003311);安徽高校省級(jí)自然科學(xué)研究重大項(xiàng)目(No.KJ2014ZD05);安徽高校省級(jí)自然科學(xué)研究重點(diǎn)項(xiàng)目(No.KJ2013Z023,No.KJ2013A058);安徽省振興計(jì)劃資助項(xiàng)目(No.2013ZDJY073)

TP311

A

0372-2112 (2016)06-1343-06