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

(重慶郵電大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，重慶 400065)

0 引 言

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

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

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

1 相關(guān)定義

結(jié)合移動(dòng)對(duì)象的運(yùn)動(dòng)行為，對(duì)移動(dòng)對(duì)象軌跡的相關(guān)概念做如下定義。

定義1(移動(dòng)軌跡)軌跡數(shù)據(jù)是帶有時(shí)間戳并按時(shí)間排序的點(diǎn)序列。軌跡Tr可以表示為Tr={p1,p2,…,pn}，其中，pj是軌跡Tr中的第j個(gè)點(diǎn)。每個(gè)點(diǎn)可以表示為(x,y,t)，其中，t是時(shí)間戳，(x,y)是移動(dòng)對(duì)象在t時(shí)刻的坐標(biāo)。

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

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

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

(1)

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

2 軌跡k近鄰查詢處理框架設(shè)計(jì)

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

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

3 分布式網(wǎng)格索引構(gòu)建

不失一般性，可以假設(shè)空間是一個(gè)矩形。給定二維空間軌跡數(shù)據(jù)集S，其中，任意軌跡上的一點(diǎn)p坐標(biāo)為(p.x,p.y)。對(duì)于點(diǎn)p，函數(shù)index(p)返回包含點(diǎn)p的網(wǎng)格，表示為

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

(2)

(2)式中：δ是網(wǎng)格邊長(zhǎng)；p.x是橫坐標(biāo)；p.y是縱坐標(biāo)。

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

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

圖3 網(wǎng)格索引構(gòu)建Fig.3 Process of building grid index

算法1網(wǎng)格構(gòu)建算法Grid。

輸入：軌跡數(shù)據(jù)；

輸出：網(wǎng)格索引文件。

步驟如下。

1) procedure MAP(k1,v1)

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

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) //對(duì)GridId分區(qū)且排序

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

11) end procedure

4 軌跡k近鄰查詢方法

4.1 軌跡還原表

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

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

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

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

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

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

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

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

輸出：k近鄰軌跡。

步驟如下。

1) procedure MAP-INIT

2) inputGridSet←Φ; candidateGridList←Φ;

3) inputGridSet=locTraj2Grid(inputTr)

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

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

6)readRebuildTableFromHDFS(context)

7) end procedure

8) procedure MAP

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

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

11) wholeCandidateSegRDD = sc.textFile.

12) (INPUT_PATH).mapPartitions(

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

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

5 實(shí)驗(yàn)分析

5.1 實(shí)驗(yàn)方案

針對(duì)提出的分布式網(wǎng)格索引以及基于此索引的軌跡k近鄰查詢方法，與同類方法在索引構(gòu)建性能，查詢性能和可擴(kuò)展性等3個(gè)方面進(jìn)行比較。

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

表1 實(shí)驗(yàn)環(huán)境

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

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

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

圖4 索引構(gòu)建性能Fig.4 Performance of Building Index

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

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

4)為了分析查詢算法的可擴(kuò)展性，本文使用數(shù)據(jù)集DS2，取δ為0.01，k為20，如圖7所示。隨著數(shù)據(jù)量的增加，2種方法的響應(yīng)時(shí)間都逐漸增加，但kNNT-Grid的增長(zhǎng)幅度相對(duì)較小。這主要是因?yàn)榫W(wǎng)格索引可以幫助定位和搜索候選集的一部分，而kNNT-Base需要搜索整個(gè)數(shù)據(jù)集。因而kNNT-Grid的可擴(kuò)展性更好。

圖6 網(wǎng)格寬度對(duì)查詢性能的影響Fig.6 Effect of width of grid on the query efficiency

圖7 查詢算法可擴(kuò)展性Fig.7 Query scalability

6 結(jié)束語

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