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

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

0 引言

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

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

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

1 適用于矢量瓦片緩存替換的視點相關預測區(qū)域算法

1.1 視點相關預測區(qū)域算法流程

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

圖1 視點相關預測區(qū)域算法流程Fig.1 Flow chart of the proposed predicted region algorithm

1.2 矢量要素的瓦片訪問熱度計算

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

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

CElei=(EleIndexi,ElePop(EleIndexi))

(1)

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

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

CeList=CeList∪EList

(2)

ElePop(EleIndexi)=ElePop(EleIndexi)+Inci

(3)

Inci=s/SpanNum(i,z)

(4)

式中：Inci為緩存矢量要素CElei的訪問熱度增量；s為矢量要素訪問熱度增量標準因子;SpanNum(i,z)表示在第z層級、索引為EleIndexi的矢量要素所跨越的瓦片數(shù)量，考慮到點要素不會出現(xiàn)跨越瓦片的情況，為避免點類型的途徑要素熱度增幅過大，令SpanNum≥2。

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

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

(5)

1.3 預測區(qū)域構建及矢量瓦片替換

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

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

圖2 位置相關數(shù)據(jù)單元劃分Fig.2 Division of location-dependent data units

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

圖3 預測區(qū)域構建Fig.3 Construction of predicted region

(6)

式中：N為有效單元的數(shù)量；(xi,yi)為第i個有效單元的坐標；(xc,yc)為當前視點命中的數(shù)據(jù)單元坐標，計算結果向上取整。

構建預測區(qū)域及計算緩存價值均需使用空間單元熱度?？紤]到瓦片的金字塔結構特征，位置相關數(shù)據(jù)單元的訪問熱度應由瓦片訪問熱度和金字塔層級決定，初始時熱度均為0。對于瓦片T地理范圍內的數(shù)據(jù)單元Ui，其訪問熱度計算公式如下：

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

(7)

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

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

(8)

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

(9)

(10)

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

如果隨著地圖操作，視點與數(shù)據(jù)單元的距離越來越小，其緩存價值應越來越大，故采用θ的負余弦函數(shù)參與距離因子運算。圖4展示了不同方向的數(shù)據(jù)單元處理方法，此時視點移動方向為水平方向，θ與β相同。

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

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

(11)

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

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

2 實驗數(shù)據(jù)與結果分析

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

2.1 不同緩存策略下命中率對比

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

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

2.2 不同緩存策略下的請求耗時對比

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

圖6 不同緩存策略下平均瓦片請求耗時對比Fig.6 Comparison of average request time of tiles under different cache strategies

3 結語

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