移動云計算環境下的雙色反近鄰查詢算法

季長清,余　勝,王寶鳳,陶　帥,汪祖民,王潤方

(1. 大連大學 物理科學與技術學院,遼寧 大連 116622；2. 大連大學 信息工程學院,遼寧 大連 116622)

?

移動云計算環境下的雙色反近鄰查詢算法

季長清1,2,余勝1,王寶鳳2,陶帥2,汪祖民2,王潤方2

(1. 大連大學 物理科學與技術學院,遼寧 大連 116622；2. 大連大學 信息工程學院,遼寧 大連 116622)

摘要:研究在移動云計算環境下的最大雙色反最近鄰查詢優化問題,設計新的高效的雙色反最近鄰查詢算法——SILM算法.SILM算法是基于MapReduce框架下的倒排網格索引結構,在Map函數中對分片數據區域使用 PCT 輪圈算法.對包含在圓區域內或與圓相交的網格的權值記為1,在Reduce函數中使用網格處理算法對分片數據區域進行掃描及合并,對重疊的網格的權值進行累加,輸出網格空間中權值最大的網格區域.SILM算法可以在多計算節點上進行分布式計算,更適合于在移動云計算環境下處理大規模并行查詢請求.通過實驗對SILM算法的效率進行驗證.實驗結果表明,當數據量較大(數據點個數大于2.0×106)時,SILM算法的查詢效率是目前解決最優選址問題最佳算法的2倍.

關鍵詞：最大雙色反最近鄰查詢；倒排網格索引；移動云計算

近年來，隨著移動定位技術(mobilepositioningtechnology,MPT)和地理信息系統(geographicinformationsystem,GIS)等技術的發展，空間數據查詢技術受到學術界的廣泛關注.反最近鄰(reversenearestneighbor,RNN)查詢[1-5]作為空間數據查詢技術中最重要的查詢技術之一，學術界對該查詢技術展開了深入研究，已提出了多種用于解決RNN查詢問題、雙色反最近鄰(bichromaticreversenearestneighbor,BRNN)查詢[6-8]問題和最大雙色反最近鄰(maxbichromaticreversenearestneighbor,MaxBRNN)查詢[9-10]問題的算法，但這些算法無法解決在移動云計算環境下難以并行運行，從而導致查詢效率低下的問題.

目前，MaxOverlap算法[11]是解決最優選址問題的最佳算法，該算法通過求解多個最近位置圓(nearestlocationcircle,NLC)的交點解決MaxBRNN問題.其中，NLC是以客戶c的位置為圓心，以客戶c與該客戶最近鄰的距離為半徑的圓.

MaxOverlap算法是第一個通過多項式時間求解MaxBRNN問題的算法，該算法的時間復雜度O(|O|log|P|+m2|O|+m|O|log|O|)為二階多項式(其中m為NLC相交次數的最大值).隨著NLC交點的增多,采用MaxOverlap算法求得最優位置區域的效率急劇下降,該缺點在大數據環境下尤為明顯.

MaxOverlap算法采用的R-tree索引結構因傳統的自上而下和層次遍歷搜索特性,導致該算法很難在移動云計算環境下直接運行.而復雜的結構和固有的順序執行等特性使得該算法不支持并行運行.所以,MaxOverlap算法在大數據情況下存在查詢等待時間過長的問題.

而很多實際問題(如地震救災服務點的設置、戰機群的空中最佳加油點等)都需要在較短的時間內得到最優位置區域,因此需要設計響應時間短的算法高效地求解MaxBRNN問題.本文通過對RNN查詢、BRNN查詢等問題及相關算法的研究,設計了能夠高效解決MaxBRNN問題的ScalableInfluentialLocationMiner算法(簡稱SILM算法).

1相關工作

近年來,RNN查詢研究最初是從暴力地線性掃描全部空間對象開始的[4],后來經過不斷的技術改進與算法優化[1-5,12-13],RNN查詢研究日益成熟.目前,有效的索引與查詢是RNN查詢研究的兩個密切相關的問題.在索引方面,基于R-tree索引的RNN查詢如KM[4]與YL[12],采用的層次結構化方法不適合在分布式環境下運行；增量的IGERN[6]采用網格索引,但只能監控較小的數據集,上述索引方法目前只在非分布式環境下被證明是正確的.在查詢方面,Singh等[3]提出的近似算法SFT存在查詢結果丟失的問題；TPL算法[1]是目前單機環境下最好的RNN查詢算法之一,由于大量的迭代過程及R-tree結構,采用該算法很難進行分布式處理.現有的RNN查詢算法研究因索引、查詢的結構化特性等問題,導致算法存在潛在的順序執行、缺乏精度、產生維災難以及不能在移動云計算環境下運行等問題.因此,關于RNN查詢的研究仍面臨困難與挑戰.

隨著基于位置的服務(locationbasedservice,LBS)相關研究與應用的興起,新的支持各類大規模RNN查詢算法相繼被開發,但能夠有效地支持大規模RNN查詢的研究成果較少.在已有的研究中,MRVoronoi算法[13]除設計空間索引結構外,也簡略地描述了利用MapReduce[2]框架進行RNN查詢的過程,但該算法需要額外時間定位查詢點,當維度增加時需要較高的維護與計算代價.RankReduce算法[5]通過利用MapReduce框架處理大規模近似kNN查詢問題,但該算法不精確,只適用于高維條件,且沒有描述解決RNN查詢的過程.現有的方法均不能很好地直接用來解決大規模RNN查詢問題.

基于RNN查詢研究存在的問題,Kang等[6]開發了BRNN查詢算法,該算法在空間數據庫中已得到廣泛應用,一直被用來在眾多服務點中查找“最有影響力”的服務點.在已有的研究中,MaxOverlap算法[11]通過計算查詢集與數據集中點之間的NLC交點求解MaxBRNN問題；Liu等[14]基于MaxOverlap算法提出MaxSegment算法解決MaxBRNN問題,該算法將MaxBRNN問題轉變為最優圓弧搜索問題；FILM算法[15]是一種基于網格的近似算法,該算法可以保證返回的小網格單元對所有位置區域都有影響.

由于單機環境下的計算與存儲能力有限,無法支持大規模空間查詢,最好的解決方案是同時利用多個計算節點并行參與分布式計算并提高計算效率,因此需要設計新的分布式索引與并行查詢算法.2004年,Google提出的MapReduce框架[2]可以在云計算環境下并行執行Map和Reduce階段支持大規模并行數據分析.基于此,本文提出SILM算法,該算法在倒排網格索引結構的基礎上設計雙色反最近鄰查詢算法.SILM算法能夠在移動云計算環境下運行,可以提高求解大規模MaxBRNN問題的計算效率.本文首先利用SILM算法對空間數據集進行離線預計算,然后在在線實時查詢時直接推送結果,從而實現SILM算法在移動云計算環境下的高效實時運行效果.

2問題定義

定義1最近鄰(nearestneighbor,NN)查詢[16]給定空間數據集P和一空間點p,dist(p,pi)為p和pi之間的距離,最近鄰查詢是求P中的一個子集NN(p),其中NN(p)滿足表達式：

NN(p)={pi∈P|?pj∈P:

dist (p,pi)≤dist (p,pj)}.

定義2k近鄰(knearestneighbor,kNN)查詢[5]給定一個查詢點c,kNN查詢找到k個到查詢點c的最近數據點si∈S,其中dist(c,si)≤dist(c,s).其中,si∈S為kNN查詢結果集,s∈S為kNN查詢結果集以外的點.

定義3反最近鄰(reversenearestneighbor,RNN)查詢[11]假設D維數據集P和查詢點q,RNN查詢是找出P的子集RNN(q),滿足RNN(q)={pi∈P|?pi∈P:dist(q,pi)≤dist(pi,pj)},i≠j.

其中,dist( )為對象間的歐氏距離,pj∈P為q的k近鄰,k=1時為RNN查詢,k≥2時為RkNN查詢.

定義4雙色反最近鄰(bichromaticreversenearestneighbor,BRNN)查詢[11]給定歐氏距離空間數據集P和O,其中P和O是不同類型的數據集,若給定數據集P中的一點p,雙色反最近鄰查詢結果是返回所有點o∈O,其中o是p∈P的反最近鄰,即不存在任意一點p′∈P滿足dist(o,p′)

如圖1所示,給定便利店集合S和顧客集合C,假設數據集中有2個便利店S1、S2及5個顧客C1、C2、C3、C4和C5的位置信息,若顧客總訪問距離最近的便利店,則顧客C1、C2、C3總訪問便利店S1,顧客C4和C5總訪問便利店S2.對于BRNN查詢有BRNN(S1, S) = {C1, C2, C3}和BRNN(S2, S) = {C4, C5},若想開設一家新的便利店S3,則需要找到一個最優位置區域,使得S3被安置在該區域時能夠吸引盡可能多的顧客,那么如何得到滿足該條件的最優位置區域呢？這是一個簡單的BRNN查詢問題.

定義5最近位置圓(nearestlocationcircle,NLC)[11]給定客戶對象c∈C,NLC是以客戶c的位置為圓心,半徑為d(c,NN(c,S))的圓,其中NN(c,S)是客戶c的最近鄰.如圖1所示,客戶c1的NLC是以c1為圓心,半徑為d(c1,NN(c1,S))的圓,客戶c2的NLC是以c2為圓心,半徑為d(c2,NN(c2,S))的圓.

定義6最大雙色反最近鄰(maxbichromaticreversenearestneighbor,MaxBRNN)查詢[11]假設存在查詢集P和數據集O.MaxBRNN查詢需要返回最大區域R,R滿足下面條件：若新服務點p建立在R中,則p點對整個區域的影響最大.若查詢集P和數據集O的數據個數均為2,MaxBRNN查詢返回的最大區域R為圖1的陰影區域A.

定義7 倒排網格索引(invertedgridindex,IGI)結構 在大規模空間數據集中,倒排網格索引結構是用來存儲網格空間中網格(Cell)的劃分與空間數據對象間倒排映射關系的一種空間數據索引結構.

圖1　最近位置圓示例Fig.1　Example of nearest location circle

3SILM算法

MaxOverlap算法[11]是目前解決最優選址問題的最佳算法.該算法通過在查詢集與數據集中的點之間繪制NLC求解MaxBRNN問題,通過找到NLC間重疊最多的部分,得到最好的雙色反近鄰查詢結果區域.如圖2所示,客戶集合C = {c1, c2, c3, c4, c5}和便利店集合S = {s1, s2},MaxOverlap算法通過繪制NLC以及求解大量的NLC交點獲得最佳位置區域(見圖2(d)的陰影部分).

圖2　MaxOverlap算法示例[11]Fig.2　Example of MaxOverlap algorithm[11]

MaxOverlap算法需要計算和評估多個NLC交點,所以該算法的時間復雜度為二次方,執行效率較差.此外,MaxOverlap算法是在單機環境下設計的串行算法,不支持分布式并行分解,所以該算法不能在移動云計算環境下直接運行.針對MaxOverlap算法存在的缺點,開發SILM算法進行改進.

圖3　SILM算法的Map函數Fig.3　Map function of SILM algorithm

首先,建立空間網格索引,并整體掃描網格空間,從而得到IGI數據結構.然后在Map函數中對分片數據區域使用PCT輪圈算法[17],如圖3所示,即以點ci為圓心,r = |ci, si|為半徑輪圈,同時將圓區域內或與圓相交的網格Counter(gi)值記為1,即Counter(gi)=1,其中gi為網格被一個節點遍歷過的次數.如圖3所示為以c1、c2為圓心,以d(c1, s1)、d(c2, s2)為半徑的輪圈結果.若網格被掃描2次,Counter(gi) = 2；若網格被掃描3次,Counter(gi) = 3,以此類推.

每個分片數據區域單獨處理后,在Reduce函數中按照網格處理算法掃描及合并,在每次掃描的過程中,采用類似于文獻[18]的WordCount算法對重疊的網格Counter(gi)值累加,最后輸出整個空間區域權值W最大的網格區域.如圖4所示為兩個NLC重疊的執行過程與結果,其中深色陰影部分為兩個NLC合并后的最終輸出結果.

圖4　SILM算法的Reduce函數Fig.4　Reduce function of SILM algorithm

具體的SILM算法偽碼如算法1所示.

算法1SILM

輸入:InvertedgridindexG,DatasetC, S, ci∈C, si∈S

輸出:SILM(C, S)∥theSILMCells

Map( ):

1.InitializesetScnd=PCT(G, si, k)

2.foreachPCTRounddo

3.Counter(g0)=0

4.fori=1ton

5.ifCellisscanned

6.emit(Counter(gi)) =Counter(gi-1)+1

7.endif

9.endfor

Reduce( ):

10.Counter(gi)=0

11.foreachvalueinvaluesdo

12.Counter(gi) =Counter(gi)+value;

13.endfor

14.emitcellofmax(Counter(gi))

3. 《陸游年譜》(于北山著)，紹興二十八年(1158)：“七月，曾幾為禮部侍郎，有賀啟。八月，王師心來為紹興守，對務觀頗加禮遇，陳棠由山陰應召赴臨安，賦詩送之，……。冬季，始出仕，為福州寧德縣主簿?！雹?/p>

該算法的執行步驟如下.

1)掃描整個網格空間中的數據并建立IGI.IGI數據結構中包含存儲在每個網格單元內的空間對象列表.在空間查詢時,首先要確定網格空間中網格的位置,然后查找該網格內的所有空間對象.

如圖5所示為4×4倒排網格索引示例,網格C1指向包含(P2、P1、P3)的空間對象數據列表.可采用預聚類索引方法改良網格索引的數據傾斜問題.為了節約篇幅,這里不再復述,詳見文獻[19].

如圖6所示為基于預聚類的倒排網格索引示例,包含4×4網格,以Key-Value值存儲數據,如集合CS1,包含和.基于預聚類的倒排網格索引的實驗分析,詳見文獻[19].

圖5　倒排網格索引示例Fig.5　Example of inverted grid index

圖6　基于預聚類的倒排網格索引Fig.6　Pre-clustering based inverted grid index

2)在索引的基礎上,在Map函數中對網格進行分區.

Map函數：每個Mapper并行讀取一個文件分塊,給定一個客戶對象c∈C,采用CellCount方法輪次訪問網格周圍的對象c.若s∈S的數量超過k,Map將客戶對象作為Key值并給出其在S中的值.

3)分區后對每一個節點進行單獨處理,利用kNN輪圈方法畫圓求得kNN查詢結果集(算法1的第1行).

圖7　kNN輪圈示例Fig.7　Example of kNN Round

kNN輪圈的目的是在空間數據集P中找到距離查詢點q最近的k個點.如圖7所示為以q為圓心,分別以與q相距最近的k個點為半徑輪圈,直至找到k個點為止.若k取1,則kNN為NN.NN查詢為在數據集P中找到距離查詢點q的最近點.

4)利用遍歷算法對網格計數,遍歷一次的網格Counter(gi) = 1,遍歷兩次的網格Counter(gi) = 2,遍歷三次的網格Counter(gi) = 3,依次類推,直至kNN查詢結果集中的所有數據點均被遍歷為止(算法1的第3～8行).

PCT算法的基本思想是以查詢點q為圓心,一輪輪并行讀取周圍的網格.如圖8(a)所示為第一批輪圈組,包括半徑為δ和2δ的兩個輪圈線程并行執行CircleTrip算法求NN.如圖8(b)所示為批量并行執行半徑為3δ和4δ的輪圈.

圖8　PCT算法示例Fig.8　Example of PCT algorithm

5)在Reduce函數中掃描及合并.在掃描過程中,對重疊的網格Counter(gi)值累加(算法1的第11～13行),最后輸出數值最大的網格區域作為查詢結果(算法1的第14行).

Reduce函數：Reducer將在Mapper中獲得的查詢點或查詢點集作為Key值,NN查詢對象點作為Value值.通過歐氏距離計算得到查詢點q與近鄰點的距離,排序得到kNN結果集,并作為Reduce函數的最終輸出結果.

4BRNN算法的分析比較

4.1時間復雜度

MaxOverlap算法的時間復雜度O(|O|×log|P|+m2|O|+m|O|log|O|)為二階多項式(其中m為NLC相交次數的最大值).

對于SILM算法,需要構造服務點網格索引,該步驟的時間復雜度為O(|S|log|S|),從Ji等[20]的工作可知,網格索引的性能明顯優于R-tree索引.使用網格對NLC進行計算并通過訪問最小數量的網格發出輪圈遍歷NN查詢結果,該步驟的時間復雜度為O(|C|log|S|).對于每次遍歷的n個網格,使用CellCount算法計算網格的最大值,該步驟的時間復雜度為nO(l).SILM算法的時間復雜度O(|S|×log|S|+|C|log|S|+nO(1))為一階多項式.SILM算法的時間復雜度明顯低于MaxOverlap算法.

4.2代價模型

SILM算法與之前的工作相比,因采用倒排網格索引結構與并行查詢方法,更適合在移動云計算環境下運行.在MapReduce框架下,從3個階段分析SILM算法的時間代價.

1)Map階段.m個Mappers處理Sm字節的數據,每個Mapper在本地磁盤處理數據的平均速率為Ds字節/s,則Map階段的時間代價為

(1)

2)Shuffling階段.Ss字節數據從Mapper經過洗牌傳輸到r個Reducers.洗牌的主要代價與網絡在不同節點間的傳輸損耗有關.Dr為在不同的節點間實際傳輸的數據與所有數據的比率.在Shuffling過程中,傳輸的數據量為Scnd×Dr字節,這些數據被r個Reducers并行接收,每個Reducer的平均接收速率為Ns字節/s.Shuffling階段的總時間代價為

(2)

3)Reduce階段.r個Reducers處理Sr字節的數據,每個Reducer在本地磁盤讀取數據的平均速率為Ds字節/s,則Reduce階段的時間代價為

(3)

SILM算法的預期總時間代價為

(4)

由式(4)可知,SILM算法的效率受m、Ds、r等參數的影響.隨著集群點數量的增加,SILM算法因采用MapReduce并行框架,總響應時間隨數據點數量近似線性上升,而MaxOverlap算法因需要求解大量NLC交點,總響應時間隨數據點數量近似二次方上升.

此處的Sm字節被并行讀取,每個Mapper平均讀取的字節為Sm/m,數據劃分采用MapReduce框架下的隨機劃分機制,讀取機制在MapReduce框架下自動進行,隨機劃分的正確性在文獻[20]中已得到充分證明.

5實驗研究

5.1實驗設置

該實驗集群為高速千兆以太網下由12個計算節點組成的服務器集群,其中1個16核AMD皓龍62 722.1GHz處理器為主節點,其他11個雙核AMD2.0GHz處理器為從節點,每個節點都有SATA硬盤(300GB)、內存(64GB)和Ubuntu12.10服務器操作系統(64位).

對于所有實驗設置相同的實驗環境,在MaxReduce框架下,ClouderaHadoop2.0.0-cdh4.2.1的源碼是在JDK1.7下編譯的.主節點單獨運行一個NameNode和JobTracker守護進程,從節點分別運行一個TaskTracker和DataNode守護進程.每個文件的復制因子均被設置為1,目的是避免寫入開銷以及在Mappers和Reducers之間傳送的數據被壓縮.每個Map過程和Reduce過程的虛擬內存為4GB,分布式文件系統塊的大小為64MB.

該實驗采用2個數據集：真實數據集(realdatasets,RDS)和仿真數據集(syntheticdatasets,SDS).RDS由美國東北部的企業信息(金融機構、汽車服務、餐館和商店等)組成,該數據集從Navteq*http:∥www.navteq.com/.中檢索得到,含約1.3×109個數據點,原始數據在解壓前約為13GB.SDS為隨機位置生成器在105×105空間域中產生,該數據集具有Zipf分布及偏度系數為0.2等特點,含約2.0×109個數據點,用以模擬真實世界.

5.2網格寬度影響

考慮到網格寬度δ會影響SILM算法的性能,采用學術界的通用方式,即通過多次訓練性實驗得到δ對SILM算法性能的影響,并確定使用2個數據集的最佳網格寬度.

通過對Ji等[17]的研究可知,在特定數據集中,網格寬度的最佳值取決于數據點分布.首先研究單機環境下δ的變化對CPU開銷的影響,通過使用1.8×105個數據點的子集確定δ對CPU開銷的影響.

如圖9所示,網格寬度過大或過小都會導致SILM算法的性能降低.圖中，T為算法執行時間.當δ較小(如δ為8×8)時,每個網格單元包含大量數據點,因此在每個網格中執行SILM算法時會消耗大量時間.當δ較大(如δ為256×256)時,每個網格單元包含少量數據點,雖然局部的計算時間較少,但網絡和磁盤在移動云計算環境下運行會產生I/O開銷.為了使SILM算法達到最佳性能,在密集的RDS中設置的網格寬度為64×64(見圖9(a)),在稀疏的SDS中設置的網格寬度為128×128(見圖9(b)).

圖9　網格寬度對CPU開銷的影響Fig.9　CPU overload under different grid widths

5.3數據點數量的影響

給出不同數量數據點下,MaxOverlap算法和SILM算法的平均響應時間T.圖10給出在RDS和SDS中數據點數量n對T的影響曲線,復制因子n和k默認為1.圖中,RDS中n從103變化到108,SDS中n從2.0×103變化到2.0×108.

如圖10(a)所示,當n較小(104以下)時,MaxOverlap算法的性能優于SILM算法,這是由于SILM算法采用倒排網格索引交易空間換取時間所導致的.隨著n的增加(104以上),由于MaxOverlap算法的響應時間T近似二次方上升,響應時間隨著NLC交點的增加而迅速增加.SILM算法所采用的倒排網格索引結構解決NLC交點問題僅需要花費O(l)時間.隨著n的增加,SILM算法響應時間T近似線性上升,因此,SILM算法較MaxOverlap算法花費的時間更少.如圖10(b)所示,當n超過2.0×106時,MaxOverlap算法的響應時間T是SILM算法的2倍多.

圖10　數據點數量對響應時間的影響Fig.10　Response time under different number of data points

圖11　SILM算法的可擴展性Fig.11　Scalability of SILM algorithm

隨著n的增加,SILM算法的效率較當前解決MaxBRNN問題最佳的MaxOverlap算法更高.

5.4SILM算法的可擴展性

研究SILM算法在RDS和SDS中的可擴展性.在MapReduce框架下,確定了最佳網格寬度并集中研究可擴展性的影響參數,其他參數如Mappers數值m、Reducers數值r等在集群資源中被自動確定.

研究服務點數量對SILM算法性能的影響,并將此影響命名為SS-SILM.將顧客數量固定為106,同時將服務點數量從104變化到108.研究顧客數量對SILM算法性能的影響,將此影響命名為CO-SILM,并將服務點數量固定為106,同時將顧客數量從104變化到108.如圖11所示分別為SILM算法在RDS和SDS中的可擴展性.圖中，N為參與計算的服務器節點數量.

如圖11所示,隨著N的增加及SILM算法的并行化擴大,SILM算法的兩種影響的響應時間都近似線性減小.由圖11可知,SS-SILM的性能優于CO-SILM,同時在RDS中,SS-SILM的響應時間比CO-SILM快了近0.3倍.這是由于SILM算法采用倒排網格索引結構,與顧客數量相比,服務點數量對NLC重疊的平均數量有更大的影響.

6結語

本文通過對MaxBRNN改良問題的研究,提出可以在移動云計算環境下快速查詢的算法—SILM算法.該算法在倒排網格索引結構的基礎上,設計了雙色反最近鄰查詢算法.目前,最佳的MaxOverlap算法的時間復雜度為二階多項式,而本文設計的SILM算法將時間復雜度降為一階多項式,使得查詢效率明顯提高.實驗結果表明,在移動云計算環境下,當數據點較大(數據點數量大于2.0×106)時,SILM算法的效率是MaxOverlap算法的2倍,這證明了SILM算法的高效性.

在今后工作中,將對SILM算法進一步優化,如結合Spark來采用更大規模的數據集進行實驗,或采用類似于MapReduce的內存計算框架來進一步提高SILM算法的性能.

參考文獻(References):

[1]TAOYu-fei,PAPADIASD,LIANXiang.ReversekNNsearchinarbitrarydimensionality[C]∥Proceedingsofthe30thInternationalConferenceonVeryLargeDataBases-Volume30.Toronto:VLDBEndowment, 2004: 744-755．

[2]DEANJ,GHEMAWATS.MapReduce:simplifieddataprocessingonlargeclusters[J].CommunicationsoftheACM, 2008, 51(1): 107-113．

[3]SINGHA,GLUHF,ALISAT.Highdimensionalreversenearestneighborqueries[C]∥Proceedingsofthe12thInternationalConferenceonInformationandKnowledgeManagement.NewYork:ACM, 2003: 91-98．

[4]KORNF,MUTHUKRISHNANS.Influencesetsbasedonreversenearestneighborqueries[C]∥ACMSIGMODRecord.NewYork:ACM, 2000: 201-212．

[5]STUPARA,MICHELS,SCHENKELR.RankReduce-processingK-nearestneighborqueriesontopofMapReduce[C]∥Proceedingsofthe8thWorkshoponLarge-ScaleDistributedSystemsforInformationRetrieval.Geneva:ACM, 2010: 13-18．

[6]KANGJM,MOKBELMF,SHEKHARS,etal.Continuousevaluationofmonochromaticandbichromaticreversenearestneighbors[C]∥23rdInternationalConferenceonDataEngineering.Istanbul:IEEE, 2007: 806-815．

[7]CONDIET,CONWAYN,ALVAROP,etal.MapReduceonline[C]∥ProceedingsofNSDI.SanJose:ACM, 2010, 10(4): 20．

[8]CONDIET,CONWAYN,ALVAROP,etal.OnlineaggregationandcontinuousquerysupportinMapReduce[C]∥Proceedingsofthe2010ACMSIGMODInternationalConferenceonManagementofData.NewYork:ACM, 2010: 1115-1118．

[9]LIUTing,ROSENBERGC,ROWLEYHA.Clusteringbillionsofimageswithlargescalenearestneighborsearch[C]∥IEEEWorkshoponApplicationsofComputerVision.AustinTexas:IEEE, 2007: 28．

[10]LIJun,ZHANGPeng,TANJian-long,etal.Continuousdatastreamqueryinthecloud[C]∥Proceedingsofthe20thACMInternationalConferenceonInformationandKnowledgeManagement.NewYork:ACM, 2011: 2389-2392．

[11]WONGRCW,TAMER?ZSUM,YUPS,etal.Efficientmethodformaximizingbichromaticreversenearestneighbor[J].ProceedingsoftheVLDBEndowment, 2009, 2(1): 1126-1137．

[12]YANGCong-Jun,LINKI.Anindexstructureforefficientreversenearestneighborqueries[C]∥Proceedingsof17thInternationalConferenceonDataEngineering.Heidelberg:IEEE, 2001: 485-492．

[13]AKDOGANA,DEMIRYUREKU,BANAEI-KASHANIF,etal.Voronoi-basedgeospatialqueryprocessingwithMapReduce[C]∥2010IEEE2ndInternationalConferenceonCloudComputingTechnologyandScience(CloudCom).Indianapolis:IEEE, 2010: 9-16．

[14]LIUYu-bao,WONGRC-H,WANGKe,etal.AnewapproachformaximizingbichromaticreversenearestneighborsearchKAIS-newapproachforMaxBRNN[J].KnowledgeandInformationSystems, 2012, 36(1): 23- 58．

[15]YANDa,WONGRCH,NGW.Efficientmethodsforfindinginfluentiallocationswithadaptivegrids[C]∥Proceedingsofthe20thACMInternationalConferenceonInformationandKnowledgeManagement.NewYork:ACM, 2011: 1475-1484．

[16]CLARKSONKL.Nearestneighborqueriesinmetricspaces[J].DiscreteandComputationalGeometry, 1999, 22 (1): 63-93．

[17]JIChang-qing,LIZhi-yang,QUWen-yu,etal.Scalablenearestneighborqueryprocessingbasedoninvertedgridindex[J].JournalofNetworkandComputerApplications, 2014, 44(1): 172-182．

[18] 張文光,陳俊,姚鈺輝,等. 分布式網絡環境中基于MapReduce的WordCount實現[J]. 貴州師范大學學報：自然科學版, 2015, 33(1): 93-97．

ZHANGWen-guang,CHENJun,YAOYu-hui,etal.MapReduce-basedWordCountachieveindistributednetworkenvironment[J].JournalofGuizhouNormalUniversity:NaturalSciences, 2015, 33(1): 93-97．

[19]JIChang-qing,QUWen-yu,LIZhi-yang,etal.Scalablemulti-dimensionalRNNqueryprocessing[J].ConcurrencyandComputation:PracticeandExperience, 2015, 27(16): 4156-4171．

[20]JIChang-qing,DONGTing-ting,LIYu,etal.Invertedgrid-basedkNNqueryprocessingwithMapReduce[C]∥ 7thChinaGridAnnualConference(ChinaGrid).Beijing:IEEE, 2012: 25-32.

收稿日期：2012-10-17.浙江大學學報(工學版)網址： www.journals.zju.edu.cn/eng

基金項目：國家自然科學基金資助項目(61370199，61501076)；遼寧省教育科研一般項目(L2014492，L2014283)；國家、遼寧省大學生創新創業訓練資助項目(201611258015，201611258040)；遼寧省“十二五”教學改革資助項目(JG14DB037)；大連市科技計劃資助項目(20150280)；大連大學博士啟動專項基金資助項目(20151QL022)；廣東省石化裝備故障診斷重點實驗室開放基金資助項目(GDUPTKLAB201505)；大連市智慧醫療與健康重點實驗室資助項目;中國高等教育學會大學素質教育專題研究課題(CALE201610).

作者簡介：季長清(1980-)，男，博士，副教授，從事云計算、大數據、空間數據庫、物聯網、移動計算等研究.ORCID:0000-0003-3473-2018. E-mail: jcqgood@gmail.com

DOI:10.3785/j.issn.1008-973X.2016.07.015

中圖分類號：TP 302

文獻標志碼：A

文章編號：1008-973X(2016)07-1330-08

Bichromaticreversenearestneighborqueryalgorithminenvironmentofmobilecloudcomputing

JIChang-qing1,2,YUSheng1,WANGBao-feng2,TAOShuai2,WANGZu-min2,WANGRun-fang2

(1.College of Physical Science and Technology, Dalian University, Dalian 116622, China;2.College of Information Technology, Dalian University, Dalian 116622, China)

Abstract:A new and high-efficiency bichromatic reverse nearest neighbor query algorithm-SILM algorithm was designed based on the inverted grid index structure within the MapReduce framework by the study on max bichromatic reverse nearest neighbor query optimization problem in the environment of mobile cloud computing. For the split data area, PCT round algorithm was applied in the Map function and the weight of circular area or grids intersected with the circle was denoted as 1. Then the split data areas were scanned and merged by grid processing algorithms in the Reduce function, and the weights of overlapping grids were accumulated. The grid area with the largest weight of the grid space was outputted. SILM algorithm can not only realize the distributed computation on multiple calculation nodes, but also complete the large-scale parallel query requests in mobile cloud computing environment. The experiment on the high-efficiency of SILM algorithm was conducted. Results show that the efficiency of SILM algorithm is 2 times more than that of the best algorithm on solving the optimal location problem when the number of data points is larger than 2.0×106．

Key words:max bichromatic reverse nearest neighbor; inverted grid index; mobile cloud computing