適用于矢量瓦片緩存替換的視點(diǎn)相關(guān)預(yù)測(cè)區(qū)域算法

王治銘，范光鵬，陳飛翔,2，崔曉暉,2*

(1.北京林業(yè)大學(xué)信息學(xué)院，北京 100083；2.國家林業(yè)草原林業(yè)智能信息處理工程技術(shù)研究中心，北京 100083)

0 引言

隨著地球空間數(shù)據(jù)獲取技術(shù)和網(wǎng)絡(luò)服務(wù)技術(shù)日趨成熟，獲取的空間數(shù)據(jù)呈現(xiàn)出海量特征，空間數(shù)據(jù)的實(shí)時(shí)獲取和可視化應(yīng)用是WebGIS的重點(diǎn)[1,2]。瓦片技術(shù)的出現(xiàn)提升了空間數(shù)據(jù)服務(wù)的可用性[3]，然而傳統(tǒng)的柵格瓦片數(shù)據(jù)體量巨大，且存在瀏覽性能瓶頸。矢量瓦片憑借其占用帶寬小和交互性強(qiáng)的優(yōu)勢(shì)，受到更多關(guān)注[4-7]，對(duì)比矢量數(shù)據(jù)的漸進(jìn)傳輸方式，使用矢量瓦片更加高效[8]。矢量瓦片同樣依據(jù)四叉樹模型生成多分辨率瓦片金字塔，并通過瓦片層級(jí)和X、Y方向序號(hào)建立唯一索引[9]；同時(shí)在客戶端建立良好的緩存機(jī)制，能夠進(jìn)一步提高數(shù)據(jù)的傳輸效率，更好地滿足空間數(shù)據(jù)應(yīng)用的實(shí)時(shí)性需求[10,11]。

研究緩存的管理和分配，需考慮如何放置和替換存儲(chǔ)內(nèi)容，緩存的命中率直接影響獲取存儲(chǔ)內(nèi)容的延遲或響應(yīng)時(shí)間[12]。當(dāng)緩存已滿且請(qǐng)求的新數(shù)據(jù)不在其中時(shí)，需要通過其他途徑獲取，并使用一定的策略對(duì)緩存進(jìn)行數(shù)據(jù)更新[13]。目前，在瓦片緩存替換方面的相關(guān)研究有：王浩等提出一種瓦片訪問平均時(shí)間間隔最長的緩存算法[10]，該算法結(jié)合最近最少使用(LRU)策略的特征，考慮了瓦片在一定時(shí)期內(nèi)的流行度，將超出平均緩存壽命最長且訪問熱度最低的瓦片置換出內(nèi)存；涂振發(fā)等提出最小空間數(shù)據(jù)價(jià)值緩存置換算法[14]，在考慮數(shù)據(jù)訪問時(shí)間和頻率的基礎(chǔ)上，引入瓦片空間位置和可視區(qū)域面積等因子評(píng)估瓦片緩存價(jià)值；劉佳星等融合瓦片金字塔的結(jié)構(gòu)特性，提出基于地理單元熱度的緩存策略[15]，并應(yīng)用熱度揮發(fā)機(jī)制對(duì)該策略進(jìn)行優(yōu)化；柴龍成等提出基于熱點(diǎn)區(qū)域簇群的瓦片緩存策略[16]，考慮了瓦片訪問的空間局部性特征，并結(jié)合空間數(shù)據(jù)的空間自相關(guān)特性計(jì)算瓦片緩存價(jià)值；吳家皋等考慮圖層對(duì)數(shù)據(jù)緩存價(jià)值的影響，將緩存更新抽象成0/1背包問題進(jìn)行求解[17]。上述緩存方法主要將空間數(shù)據(jù)的訪問時(shí)間作為替換的重要因素，未充分考慮數(shù)據(jù)的空間特征，并且緩存策略未結(jié)合矢量瓦片的特性，無法獲得較高的緩存效率。

基于預(yù)測(cè)區(qū)域的緩存算法[18]是一種用于緩存位置相關(guān)數(shù)據(jù)的方法，預(yù)測(cè)區(qū)域?qū)嵸|(zhì)是指客戶端活動(dòng)范圍，算法依據(jù)緩存數(shù)據(jù)與預(yù)測(cè)區(qū)域的位置關(guān)系更新緩存，充分考慮了數(shù)據(jù)訪問的空間特征。本文在此基礎(chǔ)上提出了一種適用于矢量瓦片緩存替換的視點(diǎn)相關(guān)預(yù)測(cè)區(qū)域算法：首先根據(jù)瓦片金字塔結(jié)構(gòu)，將空間劃分為若干個(gè)大小相同的位置相關(guān)數(shù)據(jù)單元，并引入空間單元熱度，基于訪問熱度高的空間單元構(gòu)建預(yù)測(cè)區(qū)域；通過分析預(yù)測(cè)區(qū)域獲得數(shù)據(jù)單元緩存價(jià)值，進(jìn)而得到瓦片緩存價(jià)值，最后進(jìn)行緩存置換。

1 適用于矢量瓦片緩存替換的視點(diǎn)相關(guān)預(yù)測(cè)區(qū)域算法

1.1 視點(diǎn)相關(guān)預(yù)測(cè)區(qū)域算法流程

視點(diǎn)相關(guān)預(yù)測(cè)區(qū)域算法具體流程(圖1)為： 1)客戶端記錄用戶地圖操作的類型和視點(diǎn)的當(dāng)前位置，并請(qǐng)求瓦片數(shù)據(jù)；2)判斷所請(qǐng)求的瓦片是否命中緩存，是則直接返回緩存中的數(shù)據(jù)，執(zhí)行步驟4)，否則下載瓦片數(shù)據(jù)，執(zhí)行步驟3)；3)判斷緩存空間是否已滿，是則不斷淘汰隊(duì)尾的瓦片，直到緩存能夠容納請(qǐng)求的瓦片，否則執(zhí)行步驟4)；4)更新客戶端的矢量要素緩存，計(jì)算瓦片訪問熱度(取決于其所包含的要素的熱度平均值)，并根據(jù)金字塔結(jié)構(gòu)計(jì)算位置相關(guān)數(shù)據(jù)單元的訪問熱度(與覆蓋瓦片的熱度相關(guān))；5)選擇高訪問熱度的數(shù)據(jù)單元，用以構(gòu)建預(yù)測(cè)區(qū)域,判斷數(shù)據(jù)單元是否在預(yù)測(cè)區(qū)域內(nèi)，是則通過視點(diǎn)移動(dòng)速度和方向計(jì)算視點(diǎn)的預(yù)估位置，進(jìn)而計(jì)算數(shù)據(jù)單元到視點(diǎn)預(yù)估位置的距離并將其作為距離因子，否則直接用數(shù)據(jù)單元到視點(diǎn)當(dāng)前位置的距離作為距離因子；6)結(jié)合距離因子、訪問概率和訪問熱度計(jì)算位置相關(guān)數(shù)據(jù)單元的價(jià)值；7)獲取瓦片的緩存價(jià)值，對(duì)緩存中的瓦片隊(duì)列重新排序。

圖1 視點(diǎn)相關(guān)預(yù)測(cè)區(qū)域算法流程Fig.1 Flow chart of the proposed predicted region algorithm

1.2 矢量要素的瓦片訪問熱度計(jì)算

目前計(jì)算瓦片訪問熱度的方法可分為基于特征統(tǒng)計(jì)的方法和基于智能預(yù)算的方法[19],這兩類方法均以單個(gè)瓦片為最小單元評(píng)估瓦片的訪問熱度。而矢量數(shù)據(jù)包含屬性數(shù)據(jù)和位置數(shù)據(jù)，前者以瓦片為單位進(jìn)行組織且與要素類型相關(guān)，后者則以矢量要素為單位進(jìn)行組織[20,21]，故本文引入矢量要素類型和組織結(jié)構(gòu)的影響因素，提出一種融合矢量瓦片特性的瓦片訪問熱度計(jì)算方法。

設(shè)任意瓦片T對(duì)應(yīng)一個(gè)矢量要素列表EList，其中包含該瓦片地理范圍內(nèi)的所有矢量要素。將客戶端內(nèi)存中已經(jīng)緩存的瓦片集合記為C，用戶執(zhí)行一次地圖操作所請(qǐng)求的瓦片數(shù)據(jù)集合記為R。在客戶端需要維護(hù)一個(gè)緩存矢量要素CElei(其存儲(chǔ)結(jié)構(gòu)見式(1))的列表CeList，其中記錄著客戶端曾經(jīng)訪問過的矢量要素。

CElei=(EleIndexi,ElePop(EleIndexi))

(1)

式中：EleIndexi為緩存矢量要素CElei的索引;ElePop為要素的訪問熱度。

初始時(shí)CeList中要素?cái)?shù)量為0，隨著用戶移動(dòng)、縮放地圖，產(chǎn)生瓦片請(qǐng)求集合，不斷有新的數(shù)據(jù)進(jìn)入緩存，其更新方式如下：

CeList=CeList∪EList

(2)

ElePop(EleIndexi)=ElePop(EleIndexi)+Inci

(3)

Inci=s/SpanNum(i,z)

(4)

式中：Inci為緩存矢量要素CElei的訪問熱度增量；s為矢量要素訪問熱度增量標(biāo)準(zhǔn)因子;SpanNum(i,z)表示在第z層級(jí)、索引為EleIndexi的矢量要素所跨越的瓦片數(shù)量，考慮到點(diǎn)要素不會(huì)出現(xiàn)跨越瓦片的情況，為避免點(diǎn)類型的途徑要素?zé)岫仍龇^大，令SpanNum≥2。

根據(jù)用戶不同的地圖操作行為和矢量要素類型，將客戶端的緩存矢量要素分為途徑矢量要素、觀察矢量要素和貶值矢量要素3類。1)如果某要素為用戶請(qǐng)求瓦片的要素，且該要素不在客戶端的矢量要素列表中，或該要素已在客戶端建立緩存，但訪問熱度為0，則認(rèn)為該要素為首次加載，可能是用戶切換觀察點(diǎn)時(shí)的途徑要素；另外，如果瓦片是地圖縮小操作過程中請(qǐng)求的數(shù)據(jù)，則不再考慮前一個(gè)條件，而認(rèn)為其包含的所有矢量要素都是途徑要素。途徑要素不是用戶觀察的重點(diǎn)，其訪問熱度增量(計(jì)算方式見式(4))雖為正值，但絕對(duì)值較小。2)如果某要素是客戶端的緩存矢量要素且其訪問熱度大于0，則認(rèn)為該要素是用戶在局部區(qū)域內(nèi)瀏覽的細(xì)節(jié)，屬于觀察要素；觀察要素是用戶關(guān)注的矢量要素，應(yīng)保持較高的訪問熱度，故直接用熱度增量標(biāo)準(zhǔn)因子(s)表征其熱度增量。3)如果要素不是所請(qǐng)求瓦片的矢量要素，即用戶本次地圖操作并未訪問該要素，則認(rèn)為其是貶值矢量要素；貶值矢量要素的訪問熱度持續(xù)衰減，考慮到其未來有可能成為觀察要素，要素的訪問熱度不應(yīng)減少過快，應(yīng)采用與途徑要素?zé)岫仍隽款愃频挠?jì)算方法(式(4))，但值為負(fù)。

瓦片T存儲(chǔ)在客戶端緩存中，其矢量要素列表含有n個(gè)矢量要素，則其訪問熱度可表示為：

(5)

1.3 預(yù)測(cè)區(qū)域構(gòu)建及矢量瓦片替換

瓦片作為一種地理空間數(shù)據(jù)，其訪問模式同時(shí)具有時(shí)間和空間局部性特征[22,23]:當(dāng)用戶訪問特定區(qū)域內(nèi)的某瓦片時(shí)，該瓦片周圍的瓦片在下一時(shí)刻被訪問的可能性也很高[24]。充分考慮這種空間局部性特征，本文在預(yù)測(cè)區(qū)域緩存算法的基礎(chǔ)上，提出適用于矢量瓦片緩存替換的視點(diǎn)相關(guān)預(yù)測(cè)區(qū)域算法：首先將空間劃分為位置相關(guān)數(shù)據(jù)單元，并根據(jù)瓦片熱度和金字塔結(jié)構(gòu)計(jì)算空間單元熱度；結(jié)合空間自相關(guān)性和單元熱度，在數(shù)據(jù)單元維度上構(gòu)建預(yù)測(cè)區(qū)域，考慮到該預(yù)測(cè)區(qū)域?yàn)橐朁c(diǎn)位置范圍，數(shù)據(jù)單元和預(yù)測(cè)區(qū)域的位置關(guān)系將直接影響緩存價(jià)值的求解，故在緩存價(jià)值計(jì)算中引入緩存項(xiàng)和視點(diǎn)位置的距離因子，結(jié)合其訪問概率和訪問熱度，可得空間單元緩存價(jià)值；最后根據(jù)瓦片的層級(jí)和覆蓋的空間單元價(jià)值計(jì)算瓦片緩存價(jià)值，進(jìn)行緩存替換。

矢量瓦片的金字塔結(jié)構(gòu)使不同層級(jí)的瓦片存在地理范圍上的重疊，且上層瓦片涵蓋的地理范圍很大，不宜直接進(jìn)行預(yù)測(cè)區(qū)域分析，故用瓦片金字塔最底層的網(wǎng)格對(duì)地理空間進(jìn)行規(guī)則劃分，將分割得到的空間數(shù)據(jù)單元稱為位置相關(guān)數(shù)據(jù)單元(圖2)。

圖2 位置相關(guān)數(shù)據(jù)單元?jiǎng)澐諪ig.2 Division of location-dependent data units

預(yù)測(cè)區(qū)域算法[18]是一種位置感知方法，算法的關(guān)鍵是對(duì)客戶端近期活動(dòng)范圍進(jìn)行合理預(yù)測(cè)。本文算法基于位置相關(guān)數(shù)據(jù)單元構(gòu)建視點(diǎn)相關(guān)的預(yù)測(cè)區(qū)域。在傳統(tǒng)方法中，計(jì)算當(dāng)前視點(diǎn)位置與移動(dòng)地圖后視點(diǎn)位置之間的距離，將其作為預(yù)測(cè)區(qū)域的半徑[25]，但當(dāng)視點(diǎn)移動(dòng)距離很小時(shí)，大部分?jǐn)?shù)據(jù)單元會(huì)落在預(yù)測(cè)區(qū)域外，所有數(shù)據(jù)緩存項(xiàng)的緩存價(jià)值都極低，被替換出緩存的概率較高。本文算法計(jì)算數(shù)據(jù)緩存項(xiàng)有效范圍參考點(diǎn)到視點(diǎn)當(dāng)前位置的均方根距離，用來估計(jì)預(yù)測(cè)區(qū)域半徑[18]。當(dāng)位置相關(guān)數(shù)據(jù)單元的數(shù)量較大且分布均勻時(shí)，該方法計(jì)算效率低且估算的預(yù)測(cè)區(qū)域半徑過大，因此，根據(jù)瓦片熱度估算位置相關(guān)數(shù)據(jù)單元的訪問熱度，結(jié)合空間數(shù)據(jù)的空間自相關(guān)性進(jìn)一步優(yōu)化：選取訪問熱度大于均值的數(shù)據(jù)單元作為有效單元，計(jì)算其到視點(diǎn)的均方根距離Hdp(式(6))，將其作為預(yù)測(cè)區(qū)域半徑，圖3為預(yù)測(cè)區(qū)域構(gòu)建示意圖。

圖3 預(yù)測(cè)區(qū)域構(gòu)建Fig.3 Construction of predicted region

(6)

式中：N為有效單元的數(shù)量；(xi,yi)為第i個(gè)有效單元的坐標(biāo)；(xc,yc)為當(dāng)前視點(diǎn)命中的數(shù)據(jù)單元坐標(biāo)，計(jì)算結(jié)果向上取整。

構(gòu)建預(yù)測(cè)區(qū)域及計(jì)算緩存價(jià)值均需使用空間單元熱度。考慮到瓦片的金字塔結(jié)構(gòu)特征，位置相關(guān)數(shù)據(jù)單元的訪問熱度應(yīng)由瓦片訪問熱度和金字塔層級(jí)決定，初始時(shí)熱度均為0。對(duì)于瓦片T地理范圍內(nèi)的數(shù)據(jù)單元Ui，其訪問熱度計(jì)算公式如下：

Popu(Ui)=Popu(Ui)+Pop(T)/22(L-z)

(7)

式中：L表示金字塔的最高層級(jí)；z表示命中數(shù)據(jù)單元Ui的瓦片T的層級(jí)。

對(duì)位置相關(guān)數(shù)據(jù)單元進(jìn)行預(yù)測(cè)區(qū)域分析時(shí)，由于位置相關(guān)單元的有效范圍大小相同且都是正方形，容易選取有效范圍的參考點(diǎn)，在計(jì)算緩存價(jià)值時(shí)也去除了有效范圍面積的影響因素。本文引入單元訪問熱度參與緩存價(jià)值計(jì)算，并結(jié)合訪問概率和表示緩存項(xiàng)[26]與預(yù)測(cè)區(qū)域位置關(guān)系的距離因子，設(shè)計(jì)位置相關(guān)數(shù)據(jù)單元Ui的緩存價(jià)值Valu(Ui)計(jì)算公式如下：

(8)

式中：Pi為位置相關(guān)數(shù)據(jù)單元Ui的訪問概率，本文采用指數(shù)老化方法計(jì)算，Pi=α/(tc-tl)+(1-α)×Pi(tc為系統(tǒng)當(dāng)前時(shí)間，tl、α分別為位置相關(guān)數(shù)據(jù)單元最近一次訪問時(shí)間和重要性權(quán)值)，初始時(shí)所有位置相關(guān)數(shù)據(jù)單元的Pi均設(shè)為0;D(Ui)表示預(yù)測(cè)區(qū)域PR內(nèi)Ui的預(yù)測(cè)位置與當(dāng)前位置的距離(式(9))；D′(Ui)表示當(dāng)Ui不屬于預(yù)測(cè)區(qū)域PR時(shí)，預(yù)測(cè)區(qū)域中心與Ui間的距離(式(10))。

(9)

(10)

式中：(xp，yp)為視點(diǎn)預(yù)估位置，(xc，yc)為視點(diǎn)當(dāng)前位置；β為UnitDir(位置相關(guān)數(shù)據(jù)單元相對(duì)于預(yù)測(cè)區(qū)域中心的方向向量)與數(shù)據(jù)單元坐標(biāo)系X軸正方向的夾角;Lm為預(yù)測(cè)的視點(diǎn)移動(dòng)距離，θ為視點(diǎn)移動(dòng)方向向量Dir與UnitDir的夾角(圖4)，vc為視點(diǎn)移動(dòng)的速度(與客戶端顯示地圖的當(dāng)前分辨率有關(guān)，地圖移動(dòng)的最大距離不會(huì)超過顯示地圖對(duì)角線覆蓋的數(shù)據(jù)單元長度)，rand為0～1范圍內(nèi)的隨機(jī)數(shù)，xs、ys分別為顯示地圖覆蓋范圍X、Y方向上的位置相關(guān)數(shù)據(jù)單元數(shù)量。

如果隨著地圖操作，視點(diǎn)與數(shù)據(jù)單元的距離越來越小，其緩存價(jià)值應(yīng)越來越大，故采用θ的負(fù)余弦函數(shù)參與距離因子運(yùn)算。圖4展示了不同方向的數(shù)據(jù)單元處理方法，此時(shí)視點(diǎn)移動(dòng)方向?yàn)樗椒较颍扰cβ相同。

圖4 不同方向的數(shù)據(jù)單元處理方法Fig.4 Processing of data units at different locations

使用上述算法計(jì)算出位置相關(guān)數(shù)據(jù)單元的緩存價(jià)值，依據(jù)瓦片金字塔結(jié)構(gòu)特征，量化位置相關(guān)數(shù)據(jù)單元緩存價(jià)值對(duì)涵蓋它的相應(yīng)層級(jí)瓦片緩存價(jià)值的影響；同時(shí)考慮不同瓦片的數(shù)據(jù)量大小，得到矢量瓦片T的緩存價(jià)值Value(T)為：

(11)

式中：Size(T)表示矢量瓦片T的數(shù)據(jù)量；M為T包含的位置相關(guān)數(shù)據(jù)單元數(shù)量。

對(duì)客戶端緩存中的矢量瓦片按照緩存價(jià)值大小排序。當(dāng)需要進(jìn)行緩存置換時(shí)，總是將緩存價(jià)值最小的瓦片替換出緩存，直到緩存剩余空間能夠置入最新請(qǐng)求的瓦片數(shù)據(jù)為止。

2 實(shí)驗(yàn)數(shù)據(jù)與結(jié)果分析

本文實(shí)驗(yàn)數(shù)據(jù)為從OpenStreetMap下載的中國區(qū)域數(shù)據(jù)，包含7 552 860個(gè)要素(759 462個(gè)點(diǎn)要素、4 046 059個(gè)線要素和2 747 339個(gè)面要素)。在無本地緩存的情況下，實(shí)驗(yàn)(測(cè)試環(huán)境：型號(hào)ThinkPad E531，CPU為i5雙核，主頻2.60 GHz，內(nèi)存容量 8 GB)采集不同用戶進(jìn)行地圖操作時(shí)客戶端所產(chǎn)生的矢量瓦片請(qǐng)求日志共386 243條，根據(jù)其中的瓦片層級(jí)、序號(hào)解析瓦片索引，同時(shí)記錄瓦片的數(shù)據(jù)大小及用戶操作的相隔時(shí)間，還原用戶瀏覽過程。將采集的日志結(jié)果隨機(jī)劃分為4組瓦片請(qǐng)求集合，分別采用傳統(tǒng)的先進(jìn)先出(FIFO)、最近最少使用(LRU)、最不經(jīng)常使用(LFU)策略以及本文提出的緩存策略進(jìn)行測(cè)試，客戶端用sqlite數(shù)據(jù)庫文件作為本地緩存，并計(jì)算4組數(shù)據(jù)集合的平均瓦片命中率(從客戶端緩存中直接獲取的請(qǐng)求瓦片數(shù)量占總請(qǐng)求數(shù)量的百分比，與客戶端的響應(yīng)時(shí)間相關(guān))、平均字節(jié)命中率(從客戶端緩存中直接獲取的瓦片字節(jié)量占總請(qǐng)求字節(jié)量的百分比，與帶寬緊密相關(guān))和平均瓦片請(qǐng)求耗時(shí)作為評(píng)估指標(biāo)。針對(duì)本文使用的緩存策略，還應(yīng)記錄每次數(shù)據(jù)請(qǐng)求時(shí)的地圖操作類型和視域范圍。實(shí)驗(yàn)中的矢量瓦片統(tǒng)一使用MBTiles存儲(chǔ)格式，客戶端請(qǐng)求的瓦片數(shù)據(jù)均來源于本地文件而非網(wǎng)絡(luò)，從而減少網(wǎng)速慢等因素的影響。

2.1 不同緩存策略下命中率對(duì)比

應(yīng)用本文所提出的策略時(shí)，需要指定算法中矢量要素的訪問熱度標(biāo)準(zhǔn)增量s以及位置相關(guān)數(shù)據(jù)單元的最近訪問重要性權(quán)值α。經(jīng)測(cè)試，s=3、α=0.6時(shí)，本策略在各組實(shí)驗(yàn)中瓦片請(qǐng)求效率均為最高。實(shí)驗(yàn)設(shè)置客戶端的緩存空間最大為200 MB，將用戶請(qǐng)求數(shù)據(jù)分為不同的數(shù)據(jù)集合，分別模擬不同相對(duì)緩存下客戶端的緩存執(zhí)行流程，計(jì)算4種緩存策略下所有數(shù)據(jù)集合的平均瓦片命中率(圖5a)和平均字節(jié)命中率(圖5b)。實(shí)驗(yàn)結(jié)果表明，隨著相對(duì)緩存的增大，不同的緩存策略均表現(xiàn)出更高的緩存效率。其中，F(xiàn)IFO算法緩存效率最低，LFU算法比LRU算法緩存命中率更高；本文視點(diǎn)相關(guān)預(yù)測(cè)區(qū)域算法在不同數(shù)據(jù)集和不同緩存大小情況下緩存命中率都最高，約為FIFO算法的1.5倍、LRU算法的1.2倍，相比緩存效率不錯(cuò)的LFU算法也有明顯優(yōu)勢(shì)，主要原因是本文算法基于預(yù)測(cè)區(qū)域?qū)τ脩粜袨檫M(jìn)行合理預(yù)測(cè)，計(jì)算的緩存價(jià)值排序更符合實(shí)際瀏覽時(shí)對(duì)象替換出內(nèi)存的正確順序。

圖5 不同緩存策略下平均瓦片命中率和平均字節(jié)命中率對(duì)比Fig.5 Comparison of average tile hit rate and average byte hit rate under different cache strategies

2.2 不同緩存策略下的請(qǐng)求耗時(shí)對(duì)比

當(dāng)相對(duì)緩存為100%，即客戶端緩存空間可容納200 MB矢量瓦片數(shù)據(jù)時(shí)，統(tǒng)計(jì)4種策略下瓦片請(qǐng)求的平均響應(yīng)時(shí)間(圖6)。結(jié)果表明，對(duì)于相同的數(shù)據(jù)源，在客戶端緩存空間大小相同的情況下，本文視點(diǎn)相關(guān)預(yù)測(cè)區(qū)域算法的平均瓦片請(qǐng)求耗時(shí)更低。在請(qǐng)求瓦片集合為256 MB時(shí)，4種方法的平均瓦片請(qǐng)求耗時(shí)差距不大，可能是設(shè)置了客戶端緩存空間大小為200 MB，能夠容納請(qǐng)求過程中的大部分瓦片，導(dǎo)致4種方法下客戶端執(zhí)行緩存置換的次數(shù)大致相同，命中率相差不大，平均瓦片請(qǐng)求耗時(shí)也基本持平。而最好情況下本文算法比FIFO耗時(shí)縮短約50%，比LRU耗時(shí)縮短約30%，相比LFU也略有優(yōu)勢(shì)。算法耗時(shí)主要由劃分的位置相關(guān)數(shù)據(jù)單元數(shù)量決定，對(duì)于高分辨率的大規(guī)模瓦片數(shù)據(jù)，緩存價(jià)值計(jì)算的耗時(shí)更多。應(yīng)用本文算法時(shí)，客戶端還需為矢量要素和位置相關(guān)數(shù)據(jù)單元建立額外緩存，前者可以忽略，故額外緩存也與位置相關(guān)數(shù)據(jù)單元數(shù)量有關(guān)。對(duì)于最高分辨率為213×213的瓦片數(shù)據(jù)，額外緩存約為200 MB。因此，本文算法的總體性能優(yōu)于其他緩存策略，更適用于中小型數(shù)據(jù)量矢量瓦片的緩存管理。

圖6 不同緩存策略下平均瓦片請(qǐng)求耗時(shí)對(duì)比Fig.6 Comparison of average request time of tiles under different cache strategies

3 結(jié)語

本文結(jié)合矢量瓦片的數(shù)據(jù)組織結(jié)構(gòu)及瓦片訪問的空間局部性特征，提出一種適用于矢量瓦片緩存替換的視點(diǎn)相關(guān)預(yù)測(cè)區(qū)域算法。該算法考慮了矢量瓦片存儲(chǔ)信息按矢量要素組織的特征，根據(jù)不同的地圖操作更新矢量要素的熱度，通過矢量要素訪問熱度反映瓦片熱度；結(jié)合瓦片訪問的空間局部性特征，提高矢量瓦片的訪問效率；基于位置相關(guān)數(shù)據(jù)單元構(gòu)建預(yù)測(cè)區(qū)域，評(píng)估瓦片的緩存價(jià)值，輔助客戶端緩存管理。實(shí)驗(yàn)結(jié)果表明，針對(duì)不同數(shù)據(jù)集，本文策略相比傳統(tǒng)的緩存置換策略瓦片命中率和字節(jié)命中率更高，耗時(shí)更短，更適用于中小型數(shù)據(jù)量矢量瓦片的緩存替換。然而，本文算法需要額外的空間緩存矢量要素?zé)岫群涂臻g數(shù)據(jù)單元熱度，如何減小緩存空間將是下一步的研究重點(diǎn)；還需進(jìn)一步從歷史訪問數(shù)據(jù)中提取更多的信息參與決策，以提升矢量瓦片的可視化速度。