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

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

?

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

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

北京林業大學信息學院, 北京 100083

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

瓦片地圖; 緩存策略; 區域簇群; 空間自相關

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

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

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

1 瓦片緩存區域簇群管理策略設計

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

1.1 區域金字塔索引設計

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

圖1 瓦片緩存策略的區別

圖2 四叉樹示意圖

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

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

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

圖3 瓦片金字塔

圖4 區域瓦片金字塔示意圖

1.2 獲取瓦片熱點區域

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

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

圖5為對瓦片訪問數據進行Globlal Moran’s空間計算分析的結果。

圖5 瓦片數據空間自相關分析結果

Fig.5 Results of spatial autocorrelation analysis of tile data

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

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

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

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

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

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

為方便瓦片金字塔的構建，本文以標準差橢圓的水平最小外切矩形（向外取整）范圍作為熱點范圍，如圖6所示。將統計得到的熱點范圍作為區域金字塔范圍，對各個熱點區域金字塔內的瓦片數據進行統一管理。

1.3 瓦片緩存管理策略

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

圖6 部分熱點區域劃分結果

圖7 緩存數據結構

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

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

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

（3）將該瓦片的Tile ID以及對應的瓦片存儲內存地址放入該節點下的瓦片表內。

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

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

1.4 瓦片緩存管理策略流程

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

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

ind(Tile ID) ? Index表示索引集Index中關鍵字為Tile ID的索引項，Tile Heat表示該瓦片的熱度值，Size表示該瓦片大小，Fre表示該瓦片被請求的次數。

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

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

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

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

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

2 實驗評價

2.1 實驗環境

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

2.2 實驗結果與分析

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

圖8 瓦片緩存命中率

表1 各緩存策略瓦片緩存命中率實驗數據統計表

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

3 結語

本文分析了現有瓦片緩存策略的不足之處，針對林區瓦片地圖的特點，設計了基于區域簇群的林區地圖瓦片管理策略（RC緩存策略）。構造區域瓦片金字塔，將經常被訪問的熱點區域的瓦片數據進行統一調度。RC緩存策略在LFU原有基礎上進行改進，既吸收了LFU緩存策略的優點，又滿足了瓦片緩存數據區域性調度的需求。

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

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

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

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

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

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

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

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

[7] 王浩,喻占武,曾武,等.基于瓦片壽命和訪問熱度的海量空間數據緩存置換策略[J].武漢大學學報:信息科學 版,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] 楊瑩.瓦片四叉樹和填充曲線實現海量地形數據管理[J].計算機工程與應用,2016,52(14):192-196

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

[11] 路東林,智廣玉.地圖發布平臺下瓦片金字塔技術研究[J].數字技術與用,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墨卡托投影的瓦片地圖服務設計與實現[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] 季斌,周濤發,袁峰,等.地球化學異常信息的空間自相關提取方法[J].測繪科學,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

中央高校基本科研業務費專項資金資助(TD2014-02)

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

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