基于熱點區(qū)域簇群的林區(qū)地圖瓦片緩存策略

柴龍成,高文靈,尹俊飛,陳星涵,陳飛翔

?

基于熱點區(qū)域簇群的林區(qū)地圖瓦片緩存策略

柴龍成,高文靈,尹俊飛,陳星涵,陳飛翔*

北京林業(yè)大學(xué)信息學(xué)院, 北京 100083

為了提升林區(qū)瓦片地圖的運行與服務(wù)效率，本文針對瓦片的特點以及用戶操作習(xí)慣，提出一種基于區(qū)域簇群（Regional Cluster）的瓦片緩存策略。該策略從林區(qū)地圖的區(qū)域性出發(fā)，根據(jù)瓦片記錄信息，首先通過全局空間自相關(guān)分析確定聚類類型，再通過局部空間自相關(guān)分析出熱點區(qū)域。策略結(jié)合瓦片地圖的塔狀結(jié)構(gòu)特點，對傳統(tǒng)的LFU算法進行改進，保留熱點區(qū)域瓦片金字塔內(nèi)的瓦片數(shù)據(jù)群，提高瓦片緩存命中率。實驗表明，該策略能夠提高瓦片緩存命中率，加快林區(qū)瓦片地圖的訪問速度。

瓦片地圖; 緩存策略; 區(qū)域簇群; 空間自相關(guān)

Web GIS（網(wǎng)絡(luò)地理信息系統(tǒng)）是一種基于Web端的地理信息系統(tǒng)，它擁有采集、傳輸、存儲、管理、處理、分析、表達和使用地理空間數(shù)據(jù)等功能[1]，其跨平臺快速部署的特點得到了用戶的廣泛認可。在傳統(tǒng)的Web GIS中，都是由客戶端向服務(wù)器發(fā)送所需區(qū)域范圍請求，服務(wù)器根據(jù)范圍來實時生成圖片并返回，時間長、效率低、出圖慢的缺點很明顯[2]。為了滿足Web GIS對于地圖顯示、切換、瀏覽速度的需求，Google提出了瓦片地圖（Map Tile）的概念，利用提前生成的靜態(tài)圖片，快速響應(yīng)地圖請求[3]。瓦片地圖依照一定的切割規(guī)則，將地圖在不同的比例尺下分層，每層切割成相同大小的瓦片地圖，根據(jù)用戶所需空間范圍返回瓦片數(shù)據(jù)，達到局部地圖快速訪問的目的[4]。在此基礎(chǔ)上，又增加了瓦片緩存機制，通過本地數(shù)據(jù)與遠程服務(wù)器數(shù)據(jù)的共同協(xié)作，大大提高了用戶瀏覽地圖的速度。

在瓦片緩存策略改進方面，國內(nèi)外許多專家學(xué)者做了大量研究，并相應(yīng)提出了面向網(wǎng)絡(luò)GIS的最小價值空間數(shù)據(jù)緩存替換算法GDLVF[5]、用戶行為選擇參與的緩存替換策略UPBA[6]、基于瓦片壽命與訪問熱度的緩存置換策略TCLEPR[7]等。這些文獻設(shè)計的瓦片緩存策略對瓦片地圖更新效率有所提升，但都是根據(jù)單個瓦片粒度計算出的價值來判斷需要替換哪些瓦片，卻忽略了瓦片本身的區(qū)域性、連續(xù)性、層級性等特性，并且林區(qū)地圖本身也有很強的區(qū)域特性。通過分析用戶的移動行為特征以及操作習(xí)慣，每個用戶有其特有的經(jīng)常訪問的地點[8]，并且會在對同一個林場區(qū)域進行較頻繁的縮放、移動操作，在切換到另一個林場地圖區(qū)域后，又會出現(xiàn)類似的行為。用戶在高頻度的縮放、移動、切換地圖時，脫離瓦片特性的緩存策略往往會遇到緩存命中率低、緩存頻繁置換占用大量系統(tǒng)資源的情況。

針對傳統(tǒng)瓦片緩存策略的不足，本文提出了基于區(qū)域簇群（Regional Cluster，簡稱RC）的瓦片緩存策略，將瓦片緩存根據(jù)其位置、層級特點，再結(jié)合林區(qū)區(qū)域性特點，以簇群的方式進行管理。如圖1所示。

1 瓦片緩存區(qū)域簇群管理策略設(shè)計

瓦片緩存區(qū)域簇群管理策略通過對用戶歷史數(shù)據(jù)以及在線實時統(tǒng)計數(shù)據(jù)空間自相關(guān)分析得到訪問頻度高的范圍區(qū)域，根據(jù)各個高頻區(qū)域范圍，建立多區(qū)域金字塔數(shù)據(jù)存儲結(jié)構(gòu)，對瓦片數(shù)據(jù)進行簇群管理，再在LFU緩存策略的基礎(chǔ)上進行改進，將簇群數(shù)據(jù)與離散數(shù)據(jù)統(tǒng)一管理，對于長時間最少訪問的離散數(shù)據(jù)與簇群數(shù)據(jù)分別進行單獨置換與集體置換。

1.1 區(qū)域金字塔索引設(shè)計

1.1.1 統(tǒng)計單位瓦片訪問頻度瓦片金字塔一般采用的是四叉樹模型，是由二維瓦片圖像數(shù)據(jù)的特性決定的[9]。一個二維的圖像可以被均分為四個部分：東北、東南、西北、西南，四叉樹結(jié)構(gòu)可以很好地表示圖像數(shù)據(jù)的分割。如圖2所示，四叉樹在每層級上的節(jié)點數(shù)為4n個，第0層的唯一節(jié)點為根節(jié)點代表整個區(qū)域地圖，第1層存在4個節(jié)點分別顯示整個區(qū)域的1/4，第2層存在16個節(jié)點分別顯示整個區(qū)域的1/16，以此類推[10-13]。

圖1 瓦片緩存策略的區(qū)別

圖2 四叉樹示意圖

其中D為分辨率，為地圖層級，則該層地圖被分割為2的2次冪的瓦片塊。該層每一塊瓦片可以由二維坐標(biāo)(,)唯一索引，再加入瓦片的層級確定的索引，組成瓦片的唯一索引值Tile ID= (,,)。

地圖窗口在滑動、縮放時，每次請求的數(shù)據(jù)范圍皆為矩形區(qū)域。矩形的左下角(min,min)與右上角(max,max)就可以確定窗口矩形的范圍與位置。再將各層每次被訪問的區(qū)域都投影到瓦片塔的最底層(圖3)。把每次投影到底層的對應(yīng)區(qū)域內(nèi)的瓦片被訪問頻數(shù)相應(yīng)增加1，最終可以得到最底層地理單元瓦片塊被訪問頻數(shù)灰度圖。該灰度圖反映了用戶的地圖訪問特點以及各區(qū)域之間瓦片的需求差異。經(jīng)常訪問的林區(qū)以及對同一區(qū)域放縮地圖查看的瓦片區(qū)域會擁有較高的命中次數(shù)。

1.1.2 瓦片區(qū)域金字塔的設(shè)計為了實現(xiàn)區(qū)域簇群瓦片緩存管理，提高瓦片命中率，本研究設(shè)計了多區(qū)域金字塔結(jié)構(gòu)。通過構(gòu)建對于高頻瓦片的區(qū)域瓦片金字塔，來保證高頻瓦片數(shù)據(jù)在緩存內(nèi)的優(yōu)勢。根據(jù)歷史數(shù)據(jù)以及在線實時請求數(shù)據(jù)，熱點區(qū)域劃分得到訪問頻度高的區(qū)域，分別建立多個瓦片緩存金字塔，對區(qū)域數(shù)據(jù)進行統(tǒng)一管理。在高頻度訪問的地區(qū)，移動、縮放地圖所請求的瓦片索引都落在該區(qū)域的瓦片金字塔內(nèi)，通過保留區(qū)域瓦片金字塔內(nèi)的數(shù)據(jù)，可以提高瓦片緩存的命中率。設(shè)最底層的瓦片為最小瓦片單元，每個最小瓦片單元包括了最小的地理元素以及最詳細的地圖信息。多區(qū)域瓦片金字塔結(jié)構(gòu)如圖4所示，根據(jù)四叉樹原則，從瓦片地圖最底層向上收縮，直至收縮到單塊能囊括該高頻區(qū)域的瓦片為止。該瓦片即為區(qū)域瓦片金字塔的塔頂，金字塔每層對應(yīng)的瓦片構(gòu)成了區(qū)域金字塔的主體。為方便計算，區(qū)域瓦片金字塔將該區(qū)域最底層的瓦片索引范圍作為唯一標(biāo)識。

圖3 瓦片金字塔

圖4 區(qū)域瓦片金字塔示意圖

1.2 獲取瓦片熱點區(qū)域

1.2.1 瓦片空間分布模式分析根據(jù)用戶的行為習(xí)慣可知，這些被命中區(qū)域瓦片之間有高度的空間自相關(guān)性?？臻g自相關(guān)是空間依賴性的重要形式，也是后續(xù)開展空間數(shù)據(jù)探索性空間分析（Exploratory spatial data analysis, ESDA），以及劃分熱點區(qū)域的充分條件[14-16]。本文將一名隨機林業(yè)工作人員的用戶地圖訪問記錄，包括底層瓦片命中數(shù)據(jù)以及其命中次數(shù)（未訪問的瓦片次數(shù)記為0），通過Globlal Moran’s統(tǒng)計方法公式（2）來評估這組數(shù)據(jù)的區(qū)域空間自相關(guān)性，其中自相關(guān)性分為三種：聚類模式、離散模式、隨機模式。

將分子通過方差進行歸一化，指數(shù)值在[-1.0，+1.0]區(qū)間之內(nèi)。如果指數(shù)值為正，代表瓦片的命中次數(shù)分布具有正相關(guān)性，即隨著空間分布位置（距離）的聚集，相關(guān)性就越發(fā)顯著。若指數(shù)為負，則代表具有負相關(guān)性。還可以根據(jù)式（4）來計算得分值來判斷瓦片的命中次數(shù)在統(tǒng)計學(xué)上的顯著性。

圖5為對瓦片訪問數(shù)據(jù)進行Globlal Moran’s空間計算分析的結(jié)果。

圖5 瓦片數(shù)據(jù)空間自相關(guān)分析結(jié)果

Fig.5 Results of spatial autocorrelation analysis of tile data

從圖5可知，值是標(biāo)準(zhǔn)差的5.489079倍，遠超過2.58，從而可以判斷該組數(shù)據(jù)在99%的置信度情況下拒絕零假設(shè)，說明其在空間自相關(guān)性中表現(xiàn)出聚類特征。因此可以對該組數(shù)據(jù)進行熱點區(qū)域聚類分析，劃分熱點區(qū)域范圍。

1.2.2 熱點區(qū)域劃分在確定數(shù)據(jù)的全局自相關(guān)特性后，采用局部空間自相關(guān)來分析局部空間數(shù)據(jù)分布特征，如非典型局部區(qū)域、空間聚集區(qū)、異常值等。本文以Anselin Local Moran’s方法式（5）來判定擁有相似訪問頻數(shù)的瓦片數(shù)據(jù)[17,18]。

式子中的參數(shù)定義與Globlal Moran’s公式的參數(shù)定義相同。Anselin Local Moran’s方法的得分顯著性檢驗計算公式（6）。

Anselin Local Moran’s方法根據(jù)Local Moran’s分析得到莫蘭指數(shù)值、值、值，來對瓦片訪問數(shù)據(jù)進行分類。若大于1.96，表示臨近范圍的瓦片訪問數(shù)據(jù)具有95%置信度的相似度，為高值聚類（HH）或者低值聚類（LL）；若小于-1.96，表示其數(shù)據(jù)為95%置信度下的空間異常值；其他的數(shù)據(jù)為不具有統(tǒng)計顯著性的瓦片數(shù)據(jù)。

通過分析得到高值聚類的瓦片數(shù)據(jù)位置83個，可以將其視為用戶訪問的熱點位置。為進一步確認瓦片熱點區(qū)域范圍，以熱點位置為中心，根據(jù)瓦片位置以及瓦片命中次數(shù)構(gòu)造標(biāo)準(zhǔn)差橢圓。橢圓中心為高值聚類瓦片區(qū)域的加權(quán)平均中心，橢圓的長軸與短軸分別由、方向的標(biāo)準(zhǔn)距離確定，式（7）所示。

由公式（8）得到橢圓的傾斜角度：

為方便瓦片金字塔的構(gòu)建，本文以標(biāo)準(zhǔn)差橢圓的水平最小外切矩形（向外取整）范圍作為熱點范圍，如圖6所示。將統(tǒng)計得到的熱點范圍作為區(qū)域金字塔范圍，對各個熱點區(qū)域金字塔內(nèi)的瓦片數(shù)據(jù)進行統(tǒng)一管理。

1.3 瓦片緩存管理策略

為提高緩存命中率，本文設(shè)計了服務(wù)于熱點區(qū)域瓦片數(shù)據(jù)、離散數(shù)據(jù)與簇群數(shù)據(jù)整合管理的緩存管理策略，緩存中的數(shù)據(jù)結(jié)構(gòu)如圖7，分別是RC緩存列隊，四叉樹緩存區(qū)和空間對象區(qū)域。

圖6 部分熱點區(qū)域劃分結(jié)果

圖7 緩存數(shù)據(jù)結(jié)構(gòu)

首先從空間分析得到各個熱點區(qū)域，由左下頂點（0,0）與右上頂點（1,1）唯一確定，兩個頂點的水平距離為1-0,垂直距離記為1-0，分別記為D、D，并且再給每個區(qū)域一個Area ID值，即熱點區(qū)域可記作（Area ID,，，D，D）。統(tǒng)計所有熱點區(qū)域左下頂點的0值得到中位數(shù)x。構(gòu)造以x值為根節(jié)點，以所有0值為子節(jié)點的排序二叉樹。每個節(jié)點存儲有熱點區(qū)域信息，以及用于存儲瓦片金字塔簇群的瓦片表。排序二叉樹的構(gòu)造目的是便于判定用戶請求的瓦片是否位于熱點區(qū)域瓦片金字塔范圍內(nèi)。具體流程如下：

（1）假設(shè)用戶請求的瓦片索引對應(yīng)最底層瓦片索引為（X,Y），將X與二叉樹的節(jié)點進行比較，得到所有滿足X大于X且X-X小于節(jié)點D值的節(jié)點；

（2）將得到的節(jié)點中在軸方向進一步篩選。若存在Y–Y小于Dy值的節(jié)點，則表示該請求的瓦片在該熱點區(qū)域瓦片金字塔范圍內(nèi)，進入第3步。否則該瓦片沒有落在熱點區(qū)域范圍內(nèi)，直接返回；

（3）將該瓦片的Tile ID以及對應(yīng)的瓦片存儲內(nèi)存地址放入該節(jié)點下的瓦片表內(nèi)。

瓦片區(qū)域查詢的過程由子線程完成，不影響主線程瓦片緩存的訪問與載入，所有瓦片緩存地址都儲存在同一張緩存哈希表內(nèi)供地圖進程調(diào)取。

為了提高瓦片的利用率，以及實現(xiàn)區(qū)域瓦片簇群管理，本文在LFU緩存策略基礎(chǔ)上進行了改進，將熱點區(qū)域Area ID與離散瓦片Tile ID放入同一個LFU隊列當(dāng)中。當(dāng)離散瓦片被訪問時，它的Tile ID對應(yīng)的訪問頻次就會增加；當(dāng)熱點區(qū)域的瓦片被訪問時，該區(qū)域的Area ID對應(yīng)的訪問頻次也會增加。由于熱點區(qū)域瓦片表的瓦片數(shù)量大，被訪問的概率高，因此不容易被離散瓦片淘汰，提高了高頻數(shù)據(jù)的緩存壽命。只有用戶長時間很少訪問該熱點區(qū)域，該熱點區(qū)域?qū)?yīng)的瓦片金字塔內(nèi)的數(shù)據(jù)才會被淘汰。

1.4 瓦片緩存管理策略流程

客戶端請求瓦片的縮放等級為以及平面坐標(biāo)（,)，地圖數(shù)據(jù)在該層級上被切割了2的2次冪個地圖瓦片，在二維坐標(biāo)范圍計算瓦片的坐標(biāo)值(,)即可獲取瓦片的唯一坐標(biāo)值(,,)，隨后向服務(wù)端請求瓦片。瓦片數(shù)據(jù)具有唯一的Tile ID，Tile ID是由層級、行號、列號組合變換而成的字符串，可以確定唯一的瓦片地圖塊：Tile ID=(,,) (9)

其中，表示瓦片層級，表示該瓦片在層級的行序號，表示該瓦片在層級的列序號，Tile ID=(,,)表示層級為，行序號為，列序號為的編碼，定位到的索引項采用哈希存儲。設(shè)緩存瓦片索引表的索引項為ind，則Tile ID為索引項的關(guān)鍵字，用來標(biāo)識索引項ind。設(shè)Index為緩存中存放數(shù)據(jù)的索引集：?ind ? Index, ind=(Tile ID, Tile Heat, Size, Fre) (10)

ind(Tile ID) ? Index表示索引集Index中關(guān)鍵字為Tile ID的索引項，Tile Heat表示該瓦片的熱度值，Size表示該瓦片大小，F(xiàn)re表示該瓦片被請求的次數(shù)。

當(dāng)用戶放縮、移動地圖，不斷有新的瓦片請求以及瓦片緩存產(chǎn)生，區(qū)域簇群瓦片管理策略具體流程為：

（1）策略初始化，首先讀取歷史記錄進行空間分析，若符合空間聚類特點，則對數(shù)據(jù)進行熱點分析，得到瓦片請求高頻區(qū)域，將高頻區(qū)域存入排序二叉樹。主進程根據(jù)索引請求查詢判斷緩存哈希表內(nèi)是否存在相應(yīng)的瓦片數(shù)據(jù)，若存在則直接將數(shù)據(jù)返回，否則通知線程池下載對應(yīng)的瓦片數(shù)據(jù)，下載完成后通知主線程，并將數(shù)據(jù)存入緩存哈希表；

（2）子線程根據(jù)瓦片的請求索引，在熱點區(qū)域排序二叉樹內(nèi)進行查詢。如果該索引落在某個熱點區(qū)域內(nèi)，則將該瓦片的Tile ID以及對應(yīng)的數(shù)據(jù)地址存入該區(qū)域的瓦片表內(nèi)，同時將該區(qū)域的Area ID在LFU中的頻數(shù)加1。如果瓦片未落在任何一塊熱點區(qū)域內(nèi)，則直接將該瓦片的Tile ID在LFU中的頻數(shù)加1。當(dāng)向LFU隊列插入數(shù)據(jù)且隊列飽和時，將隊列中訪問頻數(shù)最少的數(shù)據(jù)彈出。若彈出的是Tile ID，將緩存哈希表中對應(yīng)的瓦片數(shù)據(jù)刪除；若彈出的是Area ID，則將Area ID對應(yīng)的熱點區(qū)域節(jié)點從二叉樹中刪除，同時刪除該區(qū)域瓦片表內(nèi)的記錄及對應(yīng)緩存哈希表內(nèi)的數(shù)據(jù)；

（3）當(dāng)隊列中的有Area ID被彈出，則對現(xiàn)有的離散瓦片數(shù)據(jù)進行空間分析，若符合空間聚類特點，就通過熱點區(qū)域分析將得到新的區(qū)域插入到二叉樹中。如此往復(fù)。

RC瓦片緩存管理策略結(jié)合了瓦片自身區(qū)域性的特點，結(jié)合并改進傳統(tǒng)LFU算法的改進與結(jié)合，將簇群瓦片與離散瓦片統(tǒng)一管理，提高了林區(qū)瓦片地圖瀏覽速度。

2 實驗評價

2.1 實驗環(huán)境

實驗通過Wire shark采集客戶端多個用戶的瓦片請求日志，以及用戶對應(yīng)的歷史數(shù)據(jù)日志，共計1120485條記錄。實驗環(huán)境CPU為雙核i5，主頻2.70 GHz，內(nèi)存16 G。根據(jù)用戶的瓦片請求日志，可以獲得瓦片的層級、行列號、大小、請求時間s等數(shù)據(jù)，以此來模擬用戶的客戶端行為。實驗在RC瓦片緩存管理策略的基礎(chǔ)上模擬用戶的客戶端行為，統(tǒng)計瓦片緩存命中率。

2.2 實驗結(jié)果與分析

將統(tǒng)計得到的用戶的瓦片請求分別在LFU、LRU、FIFO、RC緩存策略基礎(chǔ)上進行瓦片模擬調(diào)度。對相應(yīng)的瓦片緩存命中率在不同緩存容量大小下進行比較,得出各緩存策略瓦片緩存命中率實驗數(shù)據(jù)統(tǒng)計表（下表僅展示實驗中10%、20%、30%、40%、50%相對緩存大小下的數(shù)據(jù)）和實驗結(jié)果（如圖8所示）。

圖8 瓦片緩存命中率

表1 各緩存策略瓦片緩存命中率實驗數(shù)據(jù)統(tǒng)計表

實驗表明瓦片四種算法的緩存命中率（瓦片命中率以及字節(jié)命中率）都隨著緩存容量增加而增加，增加的速率逐漸降低，曲線趨于平穩(wěn)。在四種算法中，F(xiàn)IFO緩存策略效率最低，遠低于其他幾種策略。LRU緩存策略表現(xiàn)要優(yōu)于FIFO，對數(shù)據(jù)淘汰隊列有更好的優(yōu)化。LFU緩存策略避免了LRU因為偶然性或者周期性的狀況而產(chǎn)生緩存命中率下滑的影響，在實驗結(jié)果中的表現(xiàn)要優(yōu)于LRU緩存策略。實驗結(jié)果中RC緩存策略的緩存命中率要高于其他緩存策略，是由于RC緩存策略是在LFU緩存策略的基礎(chǔ)上，利用用戶的歷史數(shù)據(jù)，結(jié)合瓦片區(qū)域性、層級性特點，大程度地提高了瓦片緩存命中率。因此，從實驗結(jié)果來看，RC緩存策略在瓦片緩存數(shù)據(jù)管理上有其獨特的優(yōu)勢，RC緩存策略在不同的緩存容量大小下都表現(xiàn)出了最好的結(jié)果。

3 結(jié)語

本文分析了現(xiàn)有瓦片緩存策略的不足之處，針對林區(qū)瓦片地圖的特點，設(shè)計了基于區(qū)域簇群的林區(qū)地圖瓦片管理策略（RC緩存策略）。構(gòu)造區(qū)域瓦片金字塔，將經(jīng)常被訪問的熱點區(qū)域的瓦片數(shù)據(jù)進行統(tǒng)一調(diào)度。RC緩存策略在LFU原有基礎(chǔ)上進行改進，既吸收了LFU緩存策略的優(yōu)點，又滿足了瓦片緩存數(shù)據(jù)區(qū)域性調(diào)度的需求。

實驗結(jié)果顯示，RC緩存管理策略在不同的緩存容量大小情況下，都優(yōu)于FIFO、LRU、LFU緩存策略的瓦片緩存命中率。

由于RC緩存策略涉及到空間相關(guān)分析，雖然在瓦片緩存命中率上有很大優(yōu)勢，但是在時間效率上要低于其他緩存策略。在接下來的研究中，將著重改進RC緩存策略，使其在合理的瓦片數(shù)據(jù)密度下進行空間分析，降低時間開銷，釋放線程資源，提高林區(qū)瓦片地圖效率。

[1] 劉佳星,陳飛翔,陳星涵.一種基于地理單元熱度的瓦片緩存策略[J].計算機工程與應(yīng)用,2017,53(5):90-96

[2] 蘇旭明,譚建成.Web GIS中瓦片地圖關(guān)鍵技術(shù)研究[J].北京測繪,2012(2):9-12

[3] 陳樺,李艷明,朱美正.一種支持大量并發(fā)用戶的瓦片緩存方案研究[J].計算機工程與科學(xué),2012,34(12):144-149

[4] 朱秀麗,周治武,李靜,等.網(wǎng)絡(luò)矢量地圖瓦片技術(shù)研究[J].測繪通報,2016(11):106-109,117

[5] 涂振發(fā),孟令奎,張文,等.面向網(wǎng)絡(luò)GIS的最小價值空間數(shù)據(jù)緩存替換算法研究[J].華中師范大學(xué)學(xué)報:自科 版,2012,46(2):230-234

[6] 褚信,蔡陽軍,杜震洪,等.用戶行為選擇參與的五層十五級瓦片緩存置換策略研究[J].浙江大學(xué)學(xué)報:理學(xué) 版,2016,43(4):452-457

[7] 王浩,喻占武,曾武,等.基于瓦片壽命和訪問熱度的海量空間數(shù)據(jù)緩存置換策略[J].武漢大學(xué)學(xué)報:信息科學(xué) 版,2009,34(6):667-670

[8] Lu X, Wetter E, Bharti N,. Approaching the limit of predictability in human mobility[J]. Scientific reports, 2013(3):2923

[9] 楊瑩.瓦片四叉樹和填充曲線實現(xiàn)海量地形數(shù)據(jù)管理[J].計算機工程與應(yīng)用,2016,52(14):192-196

[10] 李東軍,曾國蓀.一種基于四叉樹的空間數(shù)據(jù)緩存策略[J].計算機工程與應(yīng)用,2008,44(22):162-165

[11] 路東林,智廣玉.地圖發(fā)布平臺下瓦片金字塔技術(shù)研究[J].數(shù)字技術(shù)與用,2013(3):99,101

[12] Gao F, Jiang P, Li X,. A massive tile data organization and management strategy based on file tree[C]//IEEE International Conference on Spatial Data Mining and Geographical Knowledge Services, 2015

[13] 李鶴元,陳剛.基于改進Web墨卡托投影的瓦片地圖服務(wù)設(shè)計與實現(xiàn)[J].測繪工程,2016,25(2):11-16

[14] Getis A. Spatial Autocorrelation[J]. Trends in Ecology & Evolution, 1973,14(5):196

[15] Anselin L. Interactive techniques & exploratory spatial data analysis[J].1999,47(2):415-421

[16] Getis A, Ord JK. The Analysis of Spatial Association by Use of Distance Statistics[J]. Geographical Analysis, 1992,24(3):189-206

[17] 季斌,周濤發(fā),袁峰,等.地球化學(xué)異常信息的空間自相關(guān)提取方法[J].測繪科學(xué),2017(8):1-6

[18] Anselin L. Local Indicators of Spatial Associa- tion-LISA[J]. Geographical Analysis, 1995,27(2):93-115

Forest Map Tile Cache Strategy Based on Hot Area Regional Cluster

CHAI Long-cheng, GAO Wen-ling, YIN Jun-fei, CHEN Xing-han, CHEN Fei-xiang*

100083,

To improve the operation and service efficiency of tile map, this paper proposes a tile caching strategy based on Regional Cluster according to the characteristics of tile and user operation habits. Based on the regional map of forest region and tile record information, this strategy firstly determines the clustering type through global spatial autocorrelation analysis, and then identifies hot spots through local spatial autocorrelation analysis. According to the tower structure characteristics of tile map, the traditional LFU algorithm is improved to preserve the tile data group in tile pyramid of hot spot area and improve the hit rate of tile cache.Experiments demonstrate that the strategy can improve the tile cache hit rate and accelerate the tile map access speed.

Tile map; cache strategy; regional cluster; spatial autocorrelation

TP391

A

1000-2324(2019)02-0328-07

10.3969/j.issn.1000-2324.2019.02.033

2018-06-21

2018-09-12

中央高?；究蒲袠I(yè)務(wù)費專項資金資助(TD2014-02)

柴龍成(1993-),男,碩士研究生,研究領(lǐng)域為空間信息技術(shù). E-mail:1005583751@qq.com

Author for correspondence.E-mail:fxchen@126.com