Spark環(huán)境下基于網格索引的軌跡k近鄰查詢方法

夏 英，王瑞迪，張 旭，阮文亮

(重慶郵電大學 計算機科學與技術學院，重慶 400065)

0 引 言

近年來，隨著移動互聯(lián)網、云計算、大數據等技術的發(fā)展，交通、環(huán)境、社交網絡等領域都匯聚了海量的軌跡數據。軌跡數據具有典型的時空特性，對軌跡數據進行有效管理和分析，有利于發(fā)現(xiàn)用戶的移動模式，并在此基礎上提供更加豐富的空間信息服務。移動對象軌跡的k近鄰(k nearest neighbor trajectories，kNNT)查詢是一種重要的空間信息服務，即由用戶給定查詢軌跡T，系統(tǒng)在軌跡集合S中檢索與其最相鄰的k條軌跡，并按照相鄰程度排序返回給用戶。軌跡k近鄰查詢廣泛地應用于軌跡數據庫中的分類、路線推薦以及智能交通管理[1]。

針對kNNT查詢問題已經進行了很多相關的研究。S. Qi等[2]設計了一種混合近鄰算法，基于空間范圍的搜索方式，解決了獨立運行多個近鄰搜索帶來的I/O成本和維持優(yōu)先隊列的CPU成本過高等問題。A. Akdogan等[3]和戴健等[4]在分布式環(huán)境中使用了基于Voronoi圖的方法來對空間數據分區(qū)，在迭代的MapReduce任務中解決空間對象的kNN[3]，kNN Join[4]查詢問題。文獻[5]提出了基于MapReduce框架下R-樹索引的并行創(chuàng)建方法，首次實現(xiàn)了R-樹索引的并行化。文獻[6]通過線性掃描的方式劃分數據，并提出了MapReduce框架下的k近鄰查詢算法，該算法在Map階段過濾了大量與查詢無關的數據以減少運算，然后在Reduce階段生成候選集。對于時空軌跡數據，文獻[7]充分利用了計算機集群的并行能力，提出了一種基于MapReduce的軌跡數據查詢處理框架，解決了軌跡數據的范圍查詢問題。季長青等[8]提出了基于網格索引的kNN查詢方法，利用了并行輪圈遍歷查詢算法(parallel circle trip，PCT)來對網格進行過濾，然后在驗證階段逐一對候選集進行驗證。另外，A. Eldawy等[9]給出了一種新的空間大數據處理平臺SpatialHadoop，并實現(xiàn)了基于其的k近鄰查詢(kNN query)、范圍查詢(range query)以及空間鄰接查詢(spatial join query)。但是，在面對大規(guī)模的軌跡數據時，由于資源的限制，傳統(tǒng)集中式環(huán)境下的查詢方法難以在獨立的計算機上處理這些數據。此外，當前一些分布式環(huán)境下的kNN查詢方法是針對k最近鄰點的，忽略了軌跡的空間連續(xù)性和時間屬性[10]。一些考慮了軌跡連續(xù)特征的方法，又僅支持一些普通軌跡查詢，而不是基于時空距離的軌跡kNN查詢。因此，對分布式環(huán)境下的移動軌跡k近鄰查詢的研究還有很大的提升空間。

為了提高軌跡k近鄰查詢方法的性能，有必要應用并行計算技術，設計分布式環(huán)境下的高效kNNT查詢方法。Spark是一個實現(xiàn)了MapReduce編程范式的基于內存計算的分布式計算框架，應用了DAG計算模型，有效減少了Shuffle的次數，具有良好的容錯性和伸縮性。本文將Spark技術應用于軌跡k近鄰查詢，考慮軌跡數據的空間和時間特性，提出針對軌跡數據的分布式網格索引及軌跡還原表的輔助結構，并基于此索引實現(xiàn)分布式的kNNT查詢方法。

1 相關定義

結合移動對象的運動行為，對移動對象軌跡的相關概念做如下定義。

定義1(移動軌跡)軌跡數據是帶有時間戳并按時間排序的點序列。軌跡Tr可以表示為Tr={p1,p2,…,pn}，其中，pj是軌跡Tr中的第j個點。每個點可以表示為(x,y,t)，其中，t是時間戳，(x,y)是移動對象在t時刻的坐標。

定義2(最短匹配距離)軌跡Tr={p1,p2,…,pn}和點q最短距離為dist(pj,q)，且?pk≠pj，dist(pj,q)≤dist(pk,q)。其中，是q和Tr的最短匹配對。

最近對距離經常用于衡量2條軌跡的距離[11]，但是這種計算方式忽略了軌跡中其他點的貢獻。另外，關于軌跡距離的測量還有其他研究，但側重于軌跡形狀[12]。然而本文方法更多考慮空間距離，定義3是軌跡距離測量方法。

定義3(軌跡距離)給定任意一條軌跡Tr={p1,p2,…,pn}和查詢軌跡t={q1,q2,…,qm}。Tr和t中任一點q的距離是其最短匹配對的距離，因而Tr和t的聚合距離是t中全部點的最短匹配距離之和，即

(1)

定義4(軌跡k近鄰查詢)給定軌跡數據集S和查詢軌跡t，kNNT查詢就是從S中檢索出k條軌跡的集合K，其中，K={Tr1,Tr2,…,Trk}，?Tri∈K和?Trj∈D-K，dist(Tri,t)≤dist(Trj,t)。

2 軌跡k近鄰查詢處理框架設計

kNNT查詢處理框架如圖1所示。整個軌跡k近鄰查詢的處理框架由存儲模塊、網格索引模塊、查詢模塊組成。首先，預處理階段會過濾軌跡數據中重復和無效的數據記錄，并導入分布式文件系統(tǒng)HDFS以保證存儲的可靠性；其次，大量的軌跡數據使得kNNT查詢時的計算成本過高，因而，需要構建索引來加速查詢過程。網格單元和Voronoi圖都是基于空間感知的劃分策略，可以將軌跡數據組織到不同區(qū)域，從而減少候選軌跡集的數量，降低計算成本。本文在Spark環(huán)境下針對移動軌跡數據采用網格索引。網格索引具有扁平化和易于并行化的特性，可以使用MapReduce模型中的分治策略來構建多個子網索引，大大提高了并行效率。此外，網格索引更適合處理動態(tài)數據集，而Voronoi圖索引在處理動態(tài)數據集時需要對局部索引重建，效率較低。因此，使用網格劃分策略將n維空間劃分為多個網格單元。最后，網格索引構建完成后，借助于軌跡還原表的輔助結構，可以快速地獲得kNNT的查詢結果。

圖1 kNNT查詢處理框架Fig.1 Framework of kNNT query processing

3 分布式網格索引構建

不失一般性，可以假設空間是一個矩形。給定二維空間軌跡數據集S，其中，任意軌跡上的一點p坐標為(p.x,p.y)。對于點p，函數index(p)返回包含點p的網格，表示為

c[p.x/δ,p.y/δ]=index(p)

(2)

(2)式中：δ是網格邊長；p.x是橫坐標；p.y是縱坐標。

圖2是軌跡的切分和映射過程。在使用邊長為δ的網格將空間區(qū)域劃分為多個規(guī)則網格單元后，所有軌跡數據都被分配到至少一個網格中。如果軌跡線段完全被一個網格覆蓋，那么這條軌跡就完全屬于這個網格。另外，如果軌跡跨越了空間網格邊界，軌跡會在邊界處被切分，再映射到2個相鄰網格中。網格索引使用鍵值對進行存儲，同一網格中的軌跡段存儲在相同的網格鍵值中，如圖2中的網格g<1,0>包含了{s(B34,B34′),s(A12,A12′)}2條軌跡數據段。

圖2 軌跡切分和映射Fig.2 Trajectory split and mapping

圖3 網格索引構建Fig.3 Process of building grid index

算法1網格構建算法Grid。

輸入：軌跡數據；

輸出：網格索引文件。

步驟如下。

1) procedure MAP(k1,v1)

2)trSegMap←SpatialPartition(v1); //切分軌跡到網格中

3) for eachtrSeg∈trSegMapdo

4)k2 ←trSeg.gridIdPair,v2 ←trSeg

5)cache(k2,v2)

6) end for

7) end procedure

8) procedure REDUCE(k2,v2)

9) gridRDD.partitionBy(gridPartitioner) //對GridId分區(qū)且排序

10) OUTPUT(k2,v2) //輸出網格索引文件

11) end procedure

4 軌跡k近鄰查詢方法

4.1 軌跡還原表

為了在執(zhí)行軌跡k近鄰查詢時能夠檢索和重建完整軌跡，需要在切分軌跡到網格的同時，保留子軌跡段間的聯(lián)系。因此，提出了軌跡還原表(trajectory rebuild table，TRT)的輔助結構。它是一個倒排索引的數據結構，類似表格構造，使用鍵值對來組織管理數據。鍵值對中的鍵是軌跡Id，而值是一個包含了軌跡跨越的所有網格的Id列表。

在軌跡k近鄰查詢方法的預處理階段，本文在Spark中將TRT加載到內存，以廣播變量的形式來分發(fā)數據，避免了任務間變量的重復復制，從而減少了網絡通信的開銷。所有的Worker節(jié)點在準備檢索候選軌跡時可以讀取TRT來查找和重建整條完整軌跡。其具體的MapReduce處理過程如下：在Map階段，每個節(jié)點將一條軌跡切分并映射到由軌跡標識符和該軌跡經過的網格組成的鍵值對中；在Reduce階段，以軌跡Id進行分組并輸出。

4.2 基于Spark的軌跡k近鄰查詢方法

這部分主要介紹Spark環(huán)境下kNNT查詢的處理過程。輪圈算法CircularTrip[13]通常是訪問周圍網格的有效方法，該算法以査詢點為圓心，使用多次畫圈的方式來訪問周圍的鄰近網格及網格內包含的對象，然后，計算距離并排序得到查詢點的鄰近對象。但CircularTrip算法并不支持分布式和軌跡查詢。因此，在此基礎上提出了Spark環(huán)境下的基于網格索引的軌跡k近鄰查詢方法，并記為kNNT-Grid。

在進行軌跡k近鄰搜索候選軌跡之前，本文在預處理階段中將輸入的查詢軌跡定位到網格中，然后，確定這些網格的中心。圍繞該中心，默認執(zhí)行一次CircleSearch()算法來初始化候選網格集合candidateGridList。同時，將軌跡還原表TRT從HDFS緩存到Executer的內存當中，避免了每個Task節(jié)點的重復讀取，減少了磁盤I/O。

在Map階段，Task節(jié)點會在每個分區(qū)中加載網格索引文件，遍歷其中的數據行，找到不重復的候選軌跡id集合，然后，繼續(xù)執(zhí)行CircleSearch()算法來查找更多的候選軌跡，直到候選集合大小大于要查詢的k值。然后，搜索軌跡還原表rebuildTable來獲取整個軌跡。在Reduce階段，使用了TreeMap來存儲軌跡段并排序還原為完整軌跡，以便可以計算完整候選軌跡與輸入軌跡之間的距離。最后，將k個最近鄰的軌跡進行排序，并保存到HDFS中。算法2是kNNT-Grid的偽碼。

算法2軌跡k近鄰查詢算法kNNT-Grid。

輸入：查詢軌跡inputTr={p1,p2, … ,pn}，網格索引文件，k值；

輸出：k近鄰軌跡。

步驟如下。

1) procedure MAP-INIT

2) inputGridSet←Φ; candidateGridList←Φ;

3) inputGridSet=locTraj2Grid(inputTr)

4)findCenter(inputGridSet,centerX,centerY) //找到中心網格

5) candidateGridList ++=CircularSearch(1) //默認輪圈一次

6)readRebuildTableFromHDFS(context)

7) end procedure

8) procedure MAP

9) candiNum=0;lineList=null;candiIdSet←Φ

10) // 讀取每一個分區(qū)的所有軌跡數據

11) wholeCandidateSegRDD = sc.textFile.

12) (INPUT_PATH).mapPartitions(

13) lineList = it.toList.map(_._1)

14) //遍歷找出不重復候選軌跡Id集合

15) candiIdSet=traverse(lineList,candiGridList)

16) while candiNum < K_NUM do

17) candiIdSet ++=traverse(lineList

18) ,CircularSearch(++cycle_num))

19) end while

20)findRebuildEntireTraj(candiIdSet,lineList))

21) end procedure

22) procedure REDUCE

23) tempMap←Φ

24) for each seg ∈ v2s do

25) tempMap.put(trId, seg) // 使用

TreeMap 還原完整軌跡

26) end for

27)calcuTraj2TrajDist(tempMap,inputTr)

28) end procedure

kNNT-Grid算法主要通過檢索網格索引并結合軌跡還原表來獲得最終的軌跡k近鄰查詢結果，而網格索引文件在集群中是被切分為多個分區(qū)存放在HDFS上的。假設一個分區(qū)中的軌跡數量為n，候選網格集合大小為m，候選軌跡片段數為k。Map任務主要用于查找候選軌跡集并還原完整軌跡片段，算法2中15-20行對分區(qū)中軌跡和候選網格的迭代遍歷，其時間復雜度為O(mn)。同時，Reduce任務主要用于合并Map任務輸出的候選軌跡片段，利用TreeMap存儲并排序還原為完整候選軌跡，時間復雜度為O(klogk)。因而，kNNT-Grid算法整體的時間復雜度為O(mn)+O(klogk)。

5 實驗分析

5.1 實驗方案

針對提出的分布式網格索引以及基于此索引的軌跡k近鄰查詢方法，與同類方法在索引構建性能，查詢性能和可擴展性等3個方面進行比較。

本文實驗是在一個包含8個節(jié)點的Spark集群上進行，1個節(jié)點作為Master節(jié)點，另外7個節(jié)點作為Worker節(jié)點。所提及的算法均采用Scala語言實現(xiàn)。具體的實驗環(huán)境如表1所示。

表1 實驗環(huán)境

實驗采用北京市出租車數據集和成都市出租車數據集。北京市出租車數據集為Microsoft GeoLife(DS1)[13]和DataTang(DS2)[14]，分別是2G和30G。DS1總行程為1 251 654 km，時間為48 203 h。DS2是由12 000輛出租車在2012年10月至12月期間收集，采集間隔為50～55 s，大約有450萬個軌跡。而成都市出租車數據集DataCastel(DS3)[15]包含了成都市1.4萬輛出租車在2014年8月3日到30日中的行駛軌跡，超過14億個GPS記錄。它們都是出租車軌跡數據，具有相似的屬性，如軌跡號、緯度、經度、時間戳、速度等。本文忽略了與實驗無關的數據項如出租車載客狀態(tài)。

5.2 實驗結果分析

1)為了分析索引構建性能，本文選取Voronoi-Based[3]算法(VD)和MRTree[5]算法進行比較。VD是分布式環(huán)境下Voronoi圖索引并行創(chuàng)建的實現(xiàn)，其在Map函數中讀入Split分片后將數據按照x軸坐標遞增排序，構建出局部Voronoi子圖，然后，在Reduce函數中合并成完整Voronoi圖；MRTree算法是基于分布式環(huán)境下R樹索引的構建算法，其在Partition函數中將空間數據集切分為n個分片，然后，在每個分片上同時創(chuàng)建各自的R-樹子索引，最后，將n個子樹索引合并為完整的R-樹索引。2種算法都是分布式索引的典型實現(xiàn)。在DS1數據集中隨機選擇50萬個數據對象，取Spark集群節(jié)點個數分別為2，4，6和8，統(tǒng)計并比較2種索引的創(chuàng)建時間。從圖4中可以看出，本文的分布式網格索引的構建性能都優(yōu)于VD和MRTree，這是由于網格索引扁平化的結構更適用于分布式計算，能夠靈活地通過MapReduce分治策略構建子網索引。但是，Voronoi圖索引的構建需要復雜的多邊形計算和局部索引重建操作，耗時較長。而MRTree索引結構由于樹形結構的分層特征，在建立中需要反復迭代導致效率較低。此外，索引構建時間的下降率并不是線性的，這主要是因為節(jié)點個數的增加，節(jié)點間網絡通信代價隨之增大。

圖4 索引構建性能Fig.4 Performance of Building Index

2)為了分析查詢算法性能，本文實現(xiàn)了kNNT-Base[6]算法，并將其作為基準方法和kNNT-Grid進行對比。kNNT-Base提供了MapReduce框架下進行空間查詢的過濾和集成思路，在過濾階段剔除了大量與查詢無關數據對象來生成候選集，因而擁有較好的性能。選取相等大小的不同區(qū)域的數據集DS1和DS3，取網格寬度0.01，如圖5所示。由于kNNT-Grid只搜索候選集的一部分，而不是整個數據集，所以kNNT-Grid的效率總是優(yōu)于kNNT-Base。對于kNNT-Grid，當k很小時，CircleSearch()首次查找到的候選軌跡的數量總是大于k，因而不需要執(zhí)行更多的CircleSearch()，所以時間開銷接近。然而，隨著k增加，候選軌跡的數量變得小于k，執(zhí)行更多的CircleSearch()會花費更多的時間。但是對于kNNT-Base，查詢時間總是緩慢增長。

3)為了分析網格寬度對查詢性能的影響，從2個數據集中隨機選擇具有相同大小(2G)的子數據集，并取k為20。在預處理階段對數據集的采樣發(fā)現(xiàn)，數據的采集范圍集中在北京市經度116.2°至116.55°和緯度39.6°至40.4°的主要城區(qū)內。通過對網格邊長的較大差異化取值，使得網格在上述范圍內分別能夠稀疏性分布和稠密性分布，從而直觀地展示出網格寬度對查詢性能的影響。因而在實驗中，δ的取值為0.1，0.01，0.001和0.000 5。實驗結果如圖6所示，當單元格寬度為0.1時，網格太稀疏以至于每個網格單元存儲了過多的軌跡，使得CircleSearch()算法一次掃描的候選軌跡數量過多，因而時間開銷最多。然而，網格越小，索引文件越多。比如選擇0.000 5，則群集會因為初始化太多Split分片導致性能下降。從圖6中可以看到，網格寬度為0.01時單元格中的軌跡對象分布較為均衡，因而查詢性能最好。

4)為了分析查詢算法的可擴展性，本文使用數據集DS2，取δ為0.01，k為20，如圖7所示。隨著數據量的增加，2種方法的響應時間都逐漸增加，但kNNT-Grid的增長幅度相對較小。這主要是因為網格索引可以幫助定位和搜索候選集的一部分，而kNNT-Base需要搜索整個數據集。因而kNNT-Grid的可擴展性更好。

圖6 網格寬度對查詢性能的影響Fig.6 Effect of width of grid on the query efficiency

圖7 查詢算法可擴展性Fig.7 Query scalability

6 結束語

為了在分布式環(huán)境下高效地支持大規(guī)模軌跡數據的kNNT查詢，本文設計了一種Spark環(huán)境下軌跡數據的分布式網格索引，將軌跡映射到空間網格中。此外，本文應用了軌跡還原表來檢索和重建整個軌跡。最后，提出了Spark環(huán)境下基于網格索引的軌跡k近鄰查詢方法kNNT-Grid。該方法在Map階段定位查詢軌跡并執(zhí)行CircleSearch()算法查找并還原候選軌跡集，并在Reduce階段排序并輸出k個最近鄰軌跡?；诓煌瑪祿膶嶒灡砻?，kNNT-Grid可以提高查詢性能，并具有良好的可擴展性。