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

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

?

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

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

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

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

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

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

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

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

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

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

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

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

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

圖2 四叉樹(shù)示意圖

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

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

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

圖3 瓦片金字塔

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

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

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

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

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

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

Fig.5 Results of spatial autocorrelation analysis of tile data

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

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

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

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

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

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

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

1.3 瓦片緩存管理策略

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

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

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

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

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

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

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

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

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

1.4 瓦片緩存管理策略流程

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

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

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

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

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

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

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

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

2 實(shí)驗(yàn)評(píng)價(jià)

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

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

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

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

圖8 瓦片緩存命中率

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

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

3 結(jié)語(yǔ)

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

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

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

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

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

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

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

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

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

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

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

[11] 路東林,智廣玉.地圖發(fā)布平臺(tái)下瓦片金字塔技術(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] 李鶴元,陳剛.基于改進(jìn)Web墨卡托投影的瓦片地圖服務(wù)設(shè)計(jì)與實(shí)現(xiàn)[J].測(cè)繪工程,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].測(cè)繪科學(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

中央高校基本科研業(yè)務(wù)費(fèi)專項(xiàng)資金資助(TD2014-02)

柴龍成(1993-),男,碩士研究生,研究領(lǐng)域?yàn)榭臻g信息技術(shù). E-mail:1005583751@qq.com

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