李艷云，牛保寧，康家興

(太原理工大學(xué) 信息與計算機(jī)學(xué)院，太原 030024)

時空熱點是指交通流量較大、居民來往次數(shù)較多的時空區(qū)域。不同于二維平面區(qū)域，時空熱點是特定的三維空間,是具有時間信息的熱點地理區(qū)域，如7:00-9:00的長風(fēng)街是時空熱點，但其他時間段的長風(fēng)街有可能不是時空熱點。本文以出租車軌跡數(shù)據(jù)為對象，通過對其進(jìn)行時空分析[1]和數(shù)據(jù)挖掘[2]，從而發(fā)現(xiàn)城市時空熱點[3-4]。城市時空熱點發(fā)現(xiàn)對城市規(guī)劃[5]、交通管理、打擊犯罪等一系列基于位置的服務(wù)有重要的參考價值。

為此，針對第一階段map-reduce嚴(yán)重耗時及資源空閑的問題，本文提出一種對軌跡數(shù)據(jù)采樣的方法S-RSampling.通過分析軌跡數(shù)據(jù)隨時間的變化，得到其分布規(guī)律，確定采樣分層數(shù)和采樣比例。在每條軌跡數(shù)據(jù)映射成〈k,v〉時，根據(jù)其分層數(shù)、分層比例進(jìn)行采樣，大幅度降低查詢時間。為降低任務(wù)空閑等待時間，在k值相同的〈k,v〉聚合時，對所有〈k,v〉隨機(jī)采樣，緩解數(shù)據(jù)分布不均勻的影響，減少資源等待時間。針對第二階段map-reduce計算浪費的問題，本文提出一種閾值過濾方法TFiltering.根據(jù)單元格屬性值的分布，動態(tài)確定閾值T，并將屬性值從大到小排序top-T的立方單元格作為熱點候選集，僅計算熱點候選集中立方單元格的熱度值，從而減少計算浪費，提高時空熱點查詢效率。本文的創(chuàng)新點如下。

1) 提出一種對軌跡數(shù)據(jù)采樣的方法S-RSampling.在軌跡數(shù)據(jù)映射成〈k,v〉時，根據(jù)軌跡數(shù)據(jù)分布規(guī)律分層采樣，大幅降低查詢時間；在k值相同的〈k,v〉聚合時，為減少資源等待時間，對所有〈k,v〉隨機(jī)采樣，緩解數(shù)據(jù)分布不均勻的影響。

2) 提出一種閾值過濾方法TFiltering.探索出一種確定閾值的方法，依據(jù)立方單元格屬性值的分布規(guī)律,動態(tài)確定閾值T；選擇熱點候選集，將屬性值從大到小排序top-T的立方單元格，作為熱點候選集，減少計算浪費，提高時空熱點查詢效率。

1 研究現(xiàn)狀

時空熱點查詢在ACM SIGSPATIAL GISCUP 2016編程競賽[11]中被要求提出高效、快速的算法，以實現(xiàn)對紐約市出租車軌跡數(shù)據(jù)的熱點分析，開發(fā)運(yùn)行于Spark分布式集群的map-reduce算法。目前，對于這類高效時空熱點查詢的研究并不多，其思想都是基于Spark分布式計算框架和Getis-Ord公式的熱度統(tǒng)計法。根據(jù)應(yīng)用場景不同，可以將現(xiàn)有算法分為兩類，一類是無約束條件的查詢，這類查詢不需要用戶指定查詢參數(shù),而是對全部軌跡數(shù)據(jù)進(jìn)行一次性計算；另一類是有約束條件的多參數(shù)查詢，這類查詢可以由用戶指定查詢參數(shù)，如地理范圍、時間范圍等，針對不同的查詢參數(shù)處理不同的軌跡數(shù)據(jù)，返回用戶指定個數(shù)的時空熱點。

無約束條件類算法中，NIKITOPOULOS[12]提出BigCAB算法，嚴(yán)格遵循熱度統(tǒng)計法思想，將每個立方單元格作為RDDs元素，每一步都精確計算。SALLES et al[13]提出的K-H-CP算法在BigCAB算法基礎(chǔ)上將城市時空分區(qū)，將分區(qū)作為RDDs元素。因為大部分立方單元格及鄰居作為一個RDDs元素被存儲在同一節(jié)點中，所以在計算鄰居間相互影響時，節(jié)點間的通信開銷降低。PARAS et al[14]提出的STG算法與K-H-CP算法類似，該算法通過將時空鄰接的立方單元格組成25×25×25的組。一個組的立方單元格存儲在同一節(jié)點上，從而降低節(jié)點間的通信開銷。K-H-CP和STG算法都是通過改變RDDs元素來降低節(jié)點間的通信開銷，均為精確算法。不同于上述三個算法，SHANGFU et al[15]提出的SR-K-M算法是在BigCAB算法的基礎(chǔ)上加了過濾和細(xì)化策略。由于過濾掉大部分立方單元格，所以計算量和網(wǎng)絡(luò)通信開銷大幅度降低。

以上這些算法都需要對全部軌跡數(shù)據(jù)進(jìn)行計算，由于軌跡數(shù)據(jù)量巨大，所以遍歷一遍軌跡數(shù)據(jù)是造成整個查詢過程耗時的主要原因。而且對于數(shù)據(jù)分布不均導(dǎo)致的資源空閑等待，以及計算大量無用立方單元格造成計算浪費的問題，上述算法沒有相應(yīng)的優(yōu)化。

有約束條件的多參數(shù)查詢算法如康家興等[16]提出的多參數(shù)城市時空熱點查詢，該算法對軌跡數(shù)據(jù)建立三維網(wǎng)格索引，能靈活地滿足不同的查詢。根據(jù)用戶指定的不同參數(shù)，處理不同的軌跡數(shù)據(jù)，返回用戶指定個數(shù)的時空熱點。雖然處理不同的軌跡數(shù)據(jù)，但仍要對相應(yīng)的全部軌跡數(shù)據(jù)進(jìn)行一次遍歷，當(dāng)所需的軌跡數(shù)據(jù)量較大時，耗時問題仍然存在。而且對于計算浪費問題，該算法沒有相應(yīng)優(yōu)化策略。

2 預(yù)備知識

2.1 Getis-Ord公式

Getis-Ord統(tǒng)計量常用來進(jìn)行熱點分析，其計算公式如下：

(1)

(2)

(3)

(4)

2.2 熱度統(tǒng)計法

熱度統(tǒng)計法是將城市時空按設(shè)定好的單元格粒度，劃分為若干相同大小的立方單元格，根據(jù)坐標(biāo)映射公式，將軌跡數(shù)據(jù)映射到立方單元格中，統(tǒng)計立方單元格的屬性值，利用Getis-Ord公式計算出各立方單元格的熱度值。

出租車軌跡數(shù)據(jù)p記錄了乘客下車經(jīng)緯度、下車時間點以及乘客數(shù)等有用信息。將這些重要信息提取出來用(plon,plat,pt,pv)表示，(plon,plat)表示下車位置經(jīng)緯度信息；pt表示下車時間點，記錄了年、月、日、和時間等信息；pv表示乘客數(shù)。

軌跡數(shù)據(jù)p到立方單元格坐標(biāo)(x,y,t)(x,y分別表示經(jīng)緯度坐標(biāo)軸，t表示時間軸)的映射公式為：

{p→(x,y,t)|x=?plon/x0」,

y=?plat/y0」,t=?pt/t0」} .

(5)

式中：x0，y0，t0分別為單元格經(jīng)度、緯度和時間軸劃分粒度[16]。

熱度統(tǒng)計法的大致流程如圖1所示。第一階段map-reduce：map函數(shù)根據(jù)坐標(biāo)映射公式將每條軌跡數(shù)據(jù)映射到立方單元格中，即將軌跡數(shù)據(jù)處理成〈k,v〉(其中k表示單元格坐標(biāo)(x,y,t)，v表示乘客數(shù))；reduce函數(shù)將k相同的〈k,v〉聚合得到〈k,vnum〉，計算出各立方單元格的屬性值vnum(即公式(1)中的xj).

圖1 基于Getis-Ord公式的熱度統(tǒng)計法流程圖Fig.1 Flowsheet of heat statistics method based on Getis-Ord formula

3 優(yōu)化方法

針對現(xiàn)有算法存在的第一階段map-reduce耗時且效率低，以及第二階段map-reduce計算浪費的問題，本文提出一種對軌跡數(shù)據(jù)采樣的方法S-RSampling和一種閾值過濾方法TFiltering.為了方便后續(xù)理解，先解釋現(xiàn)有算法第一階段map-reduce的具體步驟。

1) 從hdfs(即Hadoop分布式文件系統(tǒng))讀取軌跡數(shù)據(jù)。

2) 用map()函數(shù)將每條軌跡數(shù)據(jù)根據(jù)坐標(biāo)映射公式處理成〈k,v〉的形式。相同k對應(yīng)的〈k,v〉不止一個，因為多條軌跡數(shù)據(jù)會映射到同一個立方單元格中。

3) 通過reduceBykey()函數(shù)將k值相同的〈k,v〉聚合成〈k,vnum〉.〈k,vnum〉代表坐標(biāo)為k的立方單元格屬性值為vnum.

由于算法是查詢top-k時空熱點，只需對單元格的熱度值進(jìn)行排序，不需要計算出每個單元格的實際熱度值，所以不一定要對全部軌跡數(shù)據(jù)進(jìn)行處理。另外，由于軌跡數(shù)據(jù)量巨大，每條軌跡被映射成〈k,v〉后，數(shù)據(jù)量仍然很大，而且數(shù)據(jù)分布不均勻?qū)е掠嬎阈式档?。為此，本文提出S-RSampling方法。該方法分為兩步，第一步是在步驟2)之前，對軌跡數(shù)據(jù)進(jìn)行規(guī)律采樣。具體地，分析軌跡數(shù)據(jù)隨時間的分布規(guī)律，根據(jù)其分布規(guī)律確定采樣分層數(shù)及采樣比例，按分層數(shù)和比例對軌跡數(shù)據(jù)進(jìn)行分層采樣，使得樣本能夠反映全部軌跡數(shù)據(jù)的分布。第二步是在步驟2)之后，對〈k,v〉數(shù)據(jù)進(jìn)行隨機(jī)采樣。具體地，通過Sample算子對〈k,v〉數(shù)據(jù)進(jìn)行隨機(jī)采樣，每個〈k,v〉被采到的概率相同。

3.1 S-RSampling方法

S-RSampling方法分為兩步，第一步是在軌跡數(shù)據(jù)映射前，根據(jù)軌跡數(shù)據(jù)分布規(guī)律，對軌跡數(shù)據(jù)進(jìn)行分層采樣，稱為規(guī)律采樣。第二步是在軌跡數(shù)據(jù)映射后(即map后)，對〈k,v〉數(shù)據(jù)進(jìn)行隨機(jī)采樣，稱為map隨機(jī)采樣。

3.1.1規(guī)律采樣

本文根據(jù)時間找到軌跡數(shù)據(jù)分布規(guī)律并依據(jù)分布規(guī)律進(jìn)行采樣。在針對同樣數(shù)據(jù)集的其它熱點查詢?nèi)蝿?wù)中，直接根據(jù)其分布規(guī)律進(jìn)行采樣，極大地降低查詢時間。出租車軌跡數(shù)據(jù)包含下車經(jīng)緯度、下車時間點以及乘客數(shù)等字段。根據(jù)下車時間點字段將軌跡數(shù)據(jù)以1 h為單位分割成24份，分別統(tǒng)計每個時間段內(nèi)的乘客數(shù)。具體步驟如下：

1) 從hdfs讀取軌跡數(shù)據(jù)；

2) 分割軌跡數(shù)據(jù)的每個字段；

3) 取出下車地點經(jīng)緯度、時間、乘客數(shù)等重要信息；

4) 根據(jù)時間字段的空格分割數(shù)據(jù)，并統(tǒng)計每個時間段內(nèi)的乘客數(shù)。

對12個月的數(shù)據(jù)進(jìn)行實驗，取平均值得到一天(24 h)中不同時間段的軌跡數(shù)量，從而得到軌跡數(shù)據(jù)隨時間的分布規(guī)律，如圖2所示。橫軸代表時間，縱軸代表軌跡數(shù)據(jù)數(shù)量。實驗中不會特殊考慮周末節(jié)假日等軌跡數(shù)量峰值的時間段情況。這是由于一方面將軌跡數(shù)據(jù)中的時間字段轉(zhuǎn)換成周末節(jié)假日等信息需要大量的額外消耗；另一方面周末節(jié)假日的軌跡數(shù)量本來就比較多，按比例采樣時周末節(jié)假日數(shù)據(jù)被采到的概率本來就大，所以不需要特殊處理周末節(jié)假日的數(shù)據(jù)。

圖2 軌跡數(shù)據(jù)數(shù)量隨時間分布圖Fig.2 Distribution of trajectory data over time

根據(jù)分布圖的極小值點，本文將軌跡數(shù)據(jù)根據(jù)極小值點對應(yīng)的時間劃分為l1,l2,…,lm+1(m為極小值個數(shù))多層，統(tǒng)計各層軌跡數(shù)據(jù)數(shù)量之比r1∶r2∶…∶rm+1.規(guī)律采樣策略對l1,l2,…,lm+1層的軌跡數(shù)據(jù)進(jìn)行r1∶r2∶…∶rm+1分層采樣，使得樣本符合原始軌跡數(shù)據(jù)的分布規(guī)律，保證使用小數(shù)據(jù)集也能得到精確的結(jié)果。規(guī)律采樣過程如算法1.

算法1規(guī)律采樣算法

輸入：不同層的軌跡數(shù)據(jù)和采樣比例

輸出：分層采樣后的軌跡數(shù)據(jù)

/*從hdfs讀取不同層的軌跡數(shù)據(jù)，rdd1、rdd2和rdd3為不同層數(shù)據(jù)*/

1) val rdd1 = sc.textFile ("hdfs://master:9000 /input/2015green/1green")

2) val rdd2 = sc.textFile ("hdfs://master:9000 /input/2015green/3green")

3) val rdd3 = sc.textFile ("hdfs://master:9000 /input/2015green/6green")

/*對不同層數(shù)據(jù)進(jìn)行分層采樣，并合并，以便后續(xù)將不同數(shù)據(jù)一同處理，rdd5為合并后的數(shù)據(jù)集*/

4) val rdd4 = rdd1.sample(false,r1).union (rdd2.sample(false,r2))

5) val rdd5 = rdd4.union(rdd3.sample(false, r3))

6) rdd5.saveAsTextFile("hdfs://master:9000/output/OutputRegular") /*保存數(shù)據(jù)*/

3.1.2map隨機(jī)采樣

由于軌跡數(shù)據(jù)量巨大，經(jīng)過規(guī)律采樣后〈k,v〉仍舊很多，而且〈k,v〉數(shù)據(jù)分布不均勻造成計算效率低。本文在第一階段map后對所有〈k,v〉進(jìn)行隨機(jī)采樣，減少計算量和資源等待時間。具體地，在第一階段map之后，通過Sample算子對這一階段產(chǎn)生的〈k,v〉進(jìn)行隨機(jī)采樣，實驗中通過調(diào)整采樣率來比較查詢結(jié)果準(zhǔn)確率。map隨機(jī)采樣計算過程描述如算法2.

算法2map隨機(jī)采樣算法

輸入：第一階段map后的〈k,v〉和采樣率

輸出：采樣后的〈k,v〉

1) val conf = new SparkConf().setAppName

2) val sc = new SparkContext(conf)

3) val rdd2 = rdd1.sample(false,r) /*rdd1為算法輸入的〈k,v〉，r為采樣率*/

4) rdd2.saveAsTextFile("hdfs://master:9000/output/OutputMap") /*保存數(shù)據(jù)*/

3.2 TFiltering方法

對12個月的數(shù)據(jù)進(jìn)行實驗，得到立方單元格熱度值和數(shù)量的長尾分布，如圖3所示，橫軸代表立方單元格熱度值區(qū)間(×102)，縱軸代表立方單元格的數(shù)量(×104)。如熱度值在100到200的立方單元格有16萬多個?？梢钥闯?，大部分立方單元格的熱度值很小，計算這些不可能成為時空熱點的立方單元格，無疑會造成計算浪費。

圖3 單元格熱度值與數(shù)量分布圖Fig.3 Distribution of cubes,heat and number

3.2.1閾值確定方法

由于立方單元格的熱度值越大其屬性值通常也較大，所以根據(jù)單元格的屬性值選擇熱點候選集。具體地，本文在第一階段map-reduce后將立方單元格根據(jù)屬性值從大到小排序得到單元格屬性值的分布規(guī)律，如圖4(數(shù)據(jù)量為12個月)，橫軸代表單元格編號(單元格按屬性值從大到小的排序編號)，縱軸代表單元格屬性值。計算分布曲線的拐點坐標(biāo)(xid,yvalue)，并將xid作為閾值基數(shù)。

圖4 單元格屬性值分布Fig.4 Distribution of cubes,value

考慮兩種極端情況：一是top-xid個單元格緊密相鄰；二是top-xid個單元格互不相鄰，互不影響。

第一種情況，屬性值排序top-xid的單元格中，除了極少數(shù)邊界單元格，其余單元格的鄰居貢獻(xiàn)都能在這xid個單元格中計算得到，所以本文取xid作為閾值，屬性值排序top-xid的單元格作為熱點候選集。

第二種情況，屬性值排序top-xid的單元格中，每個單元格鄰居貢獻(xiàn)的計算都需要額外的26個鄰居單元格，所以本文取27xid作為閾值，屬性值排序top-27xid的單元格作為熱點候選集。

綜合上述兩種情況，本文取閾值T為兩種極端情況下的平均值(xid+27xid)/2，即14xid.數(shù)據(jù)集不同，分布曲線就不同，所以閾值T也不同，閾值T隨著數(shù)據(jù)集的不同而動態(tài)變化。實驗表明，這種閾值選取方法在不同數(shù)據(jù)集下的算法結(jié)果準(zhǔn)確率為100%.閾值選取的具體步驟如下：

1) 將單元格按屬性值從大到小排序；

2) 得到單元格屬性值分布曲線f(x)；

3) 計算曲線f(x)的拐點坐標(biāo)(xid,yvalue)；

4) 根據(jù)T=14xid，計算得到閾值T.

3.2.2熱點候選集的選取

在確定了閾值T后，根據(jù)單元格屬性值和閾值選取熱點候選集。具體地，對map隨機(jī)采樣后的數(shù)據(jù)進(jìn)行聚合，并對聚合得到的〈k,vnum〉，按vnum值從大到小對立方單元格排序，將top-T的立方單元格作為時空熱點候選集。熱點候選集選擇過程如算法3.

算法3熱點候選集選擇

輸入：map隨機(jī)采樣后的〈k,v〉和閾值T

輸出：熱點候選集〈k,vnum〉

1) val rdd2 = rdd1.reduceByKey((x,y)=〉x+y) /*對輸入的數(shù)據(jù)rdd1按k進(jìn)行聚合*/

2) val rdd3=rdd2.sortBy(_._2,false)/*對聚合后的數(shù)據(jù)rdd2按vnum進(jìn)行排序*/

3) val rdd4=rdd3.top(T)/*取vnum排序top-T的單元格作為熱點候選集*/

4) rdd4.saveAsTextFile("hdfs://master:9000/output/OutputFilter") /*保存數(shù)據(jù)*/

4 實驗分析與驗證

本文實驗運(yùn)行在Spark2.2.0集群，集群有2個實際工作節(jié)點，每個工作節(jié)點有2個核，4 G內(nèi)存。實驗數(shù)據(jù)為2015年的紐約市出租車數(shù)據(jù)，約15×108條記錄，共計約24 G，覆蓋范圍為緯度40.5 N-40.9 N，經(jīng)度73.7 W-74.25 W.本文實驗中立方單元格劃分了約36×104個，經(jīng)緯度和時間方向網(wǎng)格粒度分別為：200 m、200 m和2 h.實驗評價指標(biāo)為結(jié)果準(zhǔn)確率和查詢響應(yīng)時間。為了在實驗結(jié)果中方便書寫，這里將規(guī)律采樣、map隨機(jī)采樣和閾值過濾分別用符號SS、RS和TF表示。

4.1 規(guī)律采樣

為了比較不同采樣率下算法的查詢響應(yīng)時間和結(jié)果準(zhǔn)確率，本文進(jìn)行了多種規(guī)律采樣率下的對比實驗。通過實驗發(fā)現(xiàn)，在采樣率為10%的情況下，查詢響應(yīng)時間和結(jié)果準(zhǔn)確率達(dá)到較好的平衡，實驗結(jié)果如表1所示。

表1 規(guī)律采樣采樣率選取Table 1 Selection of regular sampling rate

為了驗證規(guī)律采樣的有效性，本文分別對BigCAB算法與加入SS(采樣率為10%)的BigCAB算法、STG算法與加入SS(采樣率為10%)的STG算法進(jìn)行對比實驗。在不同數(shù)據(jù)量下對查詢響應(yīng)時間進(jìn)行比較，實驗結(jié)果如圖5所示(橫軸表示數(shù)據(jù)量，以月份數(shù)量代表數(shù)據(jù)量大小，縱軸表示查詢響應(yīng)時間，下同)。加入SS的BigCAB算法較BigCAB算法查詢響應(yīng)時間平均降低34.0%，最大降低42.3%；加入SS的STG算法較STG算法查詢響應(yīng)時間平均降低34.8%，最大降低41.0%.

這是因為，本文根據(jù)分層數(shù)和分層比例對原始軌跡數(shù)據(jù)進(jìn)行合理采樣，使采樣得到的數(shù)據(jù)能較好地代表原始數(shù)據(jù)。從而，在不降低查詢結(jié)果準(zhǔn)確率的基礎(chǔ)上，大幅減低查詢響應(yīng)時間。

圖5 規(guī)律采樣實驗結(jié)果Fig.5 Experimental result of regular sampling

4.2 map隨機(jī)采樣

為了比較在第一階段map后，隨機(jī)采樣在不同采樣率下算法的查詢響應(yīng)時間和結(jié)果準(zhǔn)確率，本文在無規(guī)律采樣的基礎(chǔ)上進(jìn)行了多種隨機(jī)采樣率下的對比實驗。通過實驗發(fā)現(xiàn)，在采樣率為10%的情況下，查詢響應(yīng)時間和結(jié)果準(zhǔn)確率達(dá)到較好的平衡，實驗結(jié)果如表2所示。

表2 map隨機(jī)采樣采樣率選取Table 2 Selection of map random sampling rate

為了驗證map隨機(jī)采樣的有效性，本節(jié)對BigCAB算法以及加入各優(yōu)化策略的BigCAB算法、STG算法以及加入各優(yōu)化策略的STG算法進(jìn)行對比實驗(采樣率均為10%)。在不同數(shù)據(jù)量下比較查詢響應(yīng)時間，實驗結(jié)果如圖6所示。加入RS的BigCAB算法較BigCAB算法查詢時間平均降低25.7%，最大降低35.2%；加入SS和RS的BigCAB算法較BigCAB算法查詢時間平均降低43.7%，最大降低52.3%；加入RS的STG算法較STG算法查詢時間平均降低25.2%，最大降低31.0%；加入SS和RS的STG算法較STG算法查詢時間平均降低43.3%，最大降低49.5%.

因為規(guī)律采樣后的數(shù)據(jù)較好地代表了原始軌跡數(shù)據(jù)，映射后的〈k,v〉數(shù)據(jù)也具有代表性。考慮到需要降低查詢響應(yīng)時間，本文僅對〈k,v〉數(shù)據(jù)進(jìn)行簡單的隨機(jī)采樣。所以能在查詢結(jié)果準(zhǔn)確率不下降的情況下，減少查詢響應(yīng)時間。

圖6 map隨機(jī)采樣實驗結(jié)果Fig.6 Experimental result of map random sampling

4.3 閾值過濾

為了驗證閾值過濾的有效性，本文對BigCAB算法與加入各優(yōu)化策略的BigCAB算法、STG算法與加入各優(yōu)化策略的STG算法(采樣率均為10%)在不同數(shù)據(jù)量下進(jìn)行查詢響應(yīng)時間對比實驗，實驗結(jié)果如圖7所示。加入TF的BigCAB算法較BigCAB算法查詢響應(yīng)時間平均降低31.3%，最大降低43.3%；加入SS、RS和TF的BigCAB算法較BigCAB算法查詢響應(yīng)時間平均降低55.4%，最大降低58.7%；加入TF的STG算法較STG算法查詢響應(yīng)時間平均降低30.5%，最大降低43.0%；加入SS、RS和TF的STG算法較STG算法查詢響應(yīng)時間平均降低54.9%，最大降低58.3%.

由于熱點區(qū)域周圍通常也較熱，熱點單元格不可能存在于熱度值都小的區(qū)域。所以，存在大量不可能成為時空熱點，且對鄰居單元格的貢獻(xiàn)沒有意義的單元格。本文通過閾值過濾，將這些無用的立方單元格過濾，減少計算浪費，從而在查詢結(jié)果準(zhǔn)確率不降低的情況下，減少了查詢響應(yīng)時間。

圖7 閾值過濾實驗結(jié)果Fig.7 Experimental result of threshold filter

5 總結(jié)與展望

本文針對現(xiàn)有算法對全部軌跡數(shù)據(jù)遍歷耗時巨大，以及單元格熱度值與數(shù)量呈現(xiàn)長尾分布導(dǎo)致的效率低和計算浪費等問題，提出如下優(yōu)化方法：一是對軌跡數(shù)據(jù)采樣的方法S-RSampling，一是閾值過濾方法TFiltering.通過對軌跡數(shù)據(jù)進(jìn)行規(guī)律采樣，避免對全部數(shù)據(jù)的遍歷，大幅降低時間消耗。map隨機(jī)采樣減少〈k,v〉數(shù)據(jù)量，減少shuffle傳輸開銷以及reduce計算量，緩解數(shù)據(jù)分布不均勻?qū)е掠嬎阈实偷膯栴}；找到一種確定閾值的方法，通過閾值過濾選擇熱點候選集，減少對不可能成為時空熱點的立方單元格的計算，避免計算浪費。對于具有相同數(shù)據(jù)集的熱點查詢?nèi)蝿?wù)，使用上述優(yōu)化策略能在保證結(jié)果準(zhǔn)確率的基礎(chǔ)上有效降低查詢時間。不足之處是鄰居貢獻(xiàn)的計算耗費存儲空間，計算鄰居貢獻(xiàn)時所需的空間是第一階段map-reduce后〈k,v〉數(shù)據(jù)所占空間的27倍，后續(xù)將繼續(xù)研究，找到一種能簡化鄰居貢獻(xiàn)的代替Getis-Ord公式的方法。