用戶行為選擇參與的五層十五級瓦片緩存置換策略研究

褚 信, 蔡陽軍, 杜震洪*, 張 豐, 劉仁義, 王煉剛, 何 敬

(1.浙江大學(xué) 浙江省資源與環(huán)境信息系統(tǒng)重點實驗室, 浙江 杭州 310028； 2.浙江大學(xué) 地理信息科學(xué)研究所,浙江 杭州 310027; 3.杭州市住房保障辦公室，浙江 杭州 310006)

?

用戶行為選擇參與的五層十五級瓦片緩存置換策略研究

褚 信1,2, 蔡陽軍3, 杜震洪1,2*, 張 豐1,2, 劉仁義2, 王煉剛1,2, 何 敬1,2

(1.浙江大學(xué) 浙江省資源與環(huán)境信息系統(tǒng)重點實驗室, 浙江 杭州 310028； 2.浙江大學(xué) 地理信息科學(xué)研究所,浙江 杭州 310027; 3.杭州市住房保障辦公室，浙江 杭州 310006)

FIFO、LRU、LFU、GDLVF等傳統(tǒng)瓦片緩存置換算法側(cè)重于瓦片訪問時間和頻率、瓦片大小、空間位置關(guān)系,不適合具有多源、異構(gòu)特點的五層十五級瓦片數(shù)據(jù),在五層十五級瓦片數(shù)據(jù)緩存的應(yīng)用上存在局限性.提出了用戶行為參與的緩存置換算法UPBA(User Preference Based Tile Cache Replacement Algorithm),并從用戶行為、瓦片訪問的時間和頻率、瓦片大小、空間位置關(guān)系等方面分析了UPBA算法，提出了提高置換效率的方法.并對最高分辨率為100和250 m、生產(chǎn)時間為2014年11月、2015年1～3月的高分一號、高分二號、資源三號影像數(shù)據(jù)集進(jìn)行日志驅(qū)動仿真實驗.結(jié)果表明：相較傳統(tǒng)的緩存置換算法,UPBA提高了瓦片請求的命中率和字節(jié)命中率,降低了客戶端流量消耗和服務(wù)器端負(fù)載.

五層十五級；瓦片緩存置換；空間數(shù)據(jù)

瓦片數(shù)據(jù)的實時快速加載是提高網(wǎng)絡(luò)GIS服務(wù)質(zhì)量的重要內(nèi)容,客戶端緩存瓦片數(shù)據(jù)則是提高GIS服務(wù)質(zhì)量的重要途徑.五層十五級瓦片數(shù)據(jù)組織模型按比例對瓦片數(shù)據(jù)進(jìn)行切分并重采樣成1 000×1 000標(biāo)準(zhǔn)分辨率切片數(shù)據(jù),將多源異構(gòu)遙感影像數(shù)據(jù)標(biāo)準(zhǔn)化后統(tǒng)一于金字塔數(shù)據(jù)組織模型下[1].

緩存算法，將所需要的數(shù)據(jù)存儲在本地,以減少數(shù)據(jù)的請求頻率和網(wǎng)絡(luò)傳輸量,快速響應(yīng)請求,進(jìn)而提升客戶端的用戶體驗[2].并且當(dāng)客戶端緩存存儲區(qū)快飽和時,可通過緩存置換算法選擇并刪除部分瓦片[3],以緩存從服務(wù)器端響應(yīng)請求所返回的新瓦片.

目前，緩存置換算法已從FIFO、LRU、LRU等單因子算法演進(jìn)到MIX、GD-Size等多因子算法,各種算法結(jié)合數(shù)據(jù)訪問的時間或空間局部性,在不同的訪問模型下表現(xiàn)各自的優(yōu)越性[4-6].筆者在研究幾種傳統(tǒng)算法的基礎(chǔ)上,結(jié)合五層十五級瓦片數(shù)據(jù)的特點,提出了用戶行為選擇參與的五層十五級瓦片緩存置換算法UPBA(User Preference Based Tile Cache Replacement Algorithm).

1 基于五層十五級的瓦片數(shù)據(jù)緩存索引

五層十五級瓦片數(shù)據(jù)組織模型摒棄了四叉樹切分標(biāo)準(zhǔn),將瓦片數(shù)據(jù)劃分為5層,每一層3個級別，總共15級.如表1所示,每一層內(nèi)的級別按照5∶2.5∶1的比例進(jìn)行排列,上層的最后一級與下層的第一級之間的比例為2∶1,按此比例對瓦片數(shù)據(jù)進(jìn)行切分，重采樣成1 000×1 000的標(biāo)準(zhǔn)分辨率瓦片數(shù)據(jù)[7-8].

瓦片數(shù)據(jù)的命名，采用五層十五級標(biāo)準(zhǔn)命名方式,

表1 五層十五級劃分標(biāo)準(zhǔn)表Table 1 Five-layer Fifteen-level division standard

瓦片的名稱是由原始數(shù)據(jù)的衛(wèi)星、傳感器、采集時間這些基本數(shù)據(jù)屬性結(jié)合分塊數(shù)據(jù)所屬的級數(shù)和瓦片的地理信息(左下角的行列號)拼接而成.例如命名為HJ1A_CCD2_20110513_4_254_587.tif的數(shù)據(jù)就表示原始數(shù)據(jù)衛(wèi)星是HJ星，傳感器是CCD2,原始影像的采集時間是2011年5月13日,瓦片數(shù)據(jù)在五層十五級中的第4級,瓦片數(shù)據(jù)左下角的行號是254,列號是587.

本文根據(jù)五層十五級空間數(shù)據(jù)組織模型,以瓦片為粒度,構(gòu)造了瓦片緩存索引.瓦片數(shù)據(jù)的緩存索引與瓦片數(shù)據(jù)分開存儲,被緩存的瓦片數(shù)據(jù)單獨存放

圖1 基于R樹的瓦片緩存索引Fig.1 Tile cache index based on R-tree

在緩存文件區(qū)域.如圖1所示,緩存索引使用R樹構(gòu)建,索引項采用Key-value結(jié)構(gòu),row_num是該瓦片所在行號,column_num是列號,level_num是層級,product是產(chǎn)品類型,tile_size是文件大小,data_time是生產(chǎn)時間,create_time是首次存儲時間,last_access_time是最后一次訪問時間,access_times是訪問總次數(shù),geometry是覆蓋的地理范圍.

2 用戶行為參與的空間數(shù)據(jù)緩存置換算法

2.1 幾種傳統(tǒng)的空間數(shù)據(jù)緩存置換算法

傳統(tǒng)的緩存置換算法，如FIFO、LFU、 LRU等側(cè)重于對瓦片的時間和頻率特征進(jìn)行分析：FIFO算法認(rèn)為緩存瓦片中瓦片再次訪問的概率p反比于當(dāng)前時刻與瓦片首次存儲于緩存中的時刻的時間間隔,有p～1/△t=1/current_system_time-create_time, FIFO算法總是置換p最小(create_time最小)的瓦片；LFU算法認(rèn)為瓦片再次被訪問的概率與瓦片被訪問的次數(shù)成正比,有p～ access_times,該算法總是將訪問次數(shù)最少的瓦片移除；LRU算法認(rèn)為瓦片再次被訪問的概率與瓦片被訪問時刻與當(dāng)前時刻的時間間隔成反比,有p～1/△t=1/current_system_time-last_access_time,該算法總是將許久未訪問(last_access_time最小)的瓦片移除[2-3,9].

綜合分析以上幾種傳統(tǒng)瓦片置換算法,FIFO算法忽略了某一用戶對特定區(qū)域長時間、高頻度的訪問,可能刪除用戶感興趣的某一區(qū)域；LFU算法可能將前期經(jīng)常訪問但是以后并不經(jīng)常訪問的瓦片長期保留在緩存中,LRU算法可能將用戶偶發(fā)訪問的瓦片保留在緩存中,造成緩存污染.

2.2 面向網(wǎng)絡(luò)GIS的最小價值空間數(shù)據(jù)緩存置換算法

涂振發(fā)等[3]綜合考慮上述傳統(tǒng)空間數(shù)據(jù)緩存置換算法的優(yōu)缺點,提出了面向網(wǎng)絡(luò)GIS的最小價值空間數(shù)據(jù)緩存置換算法GDLVF,該算法除了考慮傳統(tǒng)緩存置換算法的時間、訪問頻率、文件大小等因素外,還兼顧了空間數(shù)據(jù)的空間位置特征,并依據(jù)這些因素使用特定的價值函數(shù)計算數(shù)據(jù)價值,移除其中數(shù)據(jù)價值最小的數(shù)據(jù)集:

V(i)=Vspatial(i)×Vtime(i)×Vsize(i)，

(1)

式(1)中,V(i)為瓦片i的數(shù)據(jù)價值,Vspatial(i)為空間位置價值,Vtime(i)為時間價值,Vsize(i)為數(shù)據(jù)大小價值.

2.2.1 空間位置價值

GDLVF算法認(rèn)為數(shù)據(jù)距離和有效范圍區(qū)域是影響緩存置換算法的重要因素,有效范圍區(qū)域是落在當(dāng)前可視窗口范圍內(nèi)的區(qū)域,數(shù)據(jù)距離是瓦片數(shù)據(jù)的中心點距離當(dāng)前可視窗口中心點的距離,有效區(qū)域范圍越大、數(shù)據(jù)距離越小的數(shù)據(jù)被再次訪問的可能性越大[3,10],并以此提出瓦片空間位置價值的計算公式：

(2)

式(2)中Vspatial(i)為瓦片數(shù)據(jù)的空間位置價值,Area(i)為瓦片數(shù)據(jù)有效范圍的面積,D(i)為瓦片的數(shù)據(jù)距離,并且規(guī)定0≤Area(i)<1時,設(shè)定Area(i)=1,當(dāng)0≤D(i)<1時,設(shè)定D(i)=1.

2.2.2 時間價值

GDLVF算法認(rèn)為,越久未被訪問的數(shù)據(jù)其再次被訪問的概率越小,最近越被頻繁訪問的數(shù)據(jù)其再次被訪問的概率越大,并以此提出了瓦片時間價值的計算公式：

(3)

式(3)中,Vtime(i)為瓦片數(shù)據(jù)的時間價值,avg_access_time(i)為瓦片數(shù)據(jù)的平均訪問間隔時間.

(4)

式(4)中,avg_access_time(i)為瓦片的平均訪問間隔時間,current_time為系統(tǒng)當(dāng)前時間,store_time(i)為瓦片首次存儲時間,access_count(i)為瓦片被訪問次數(shù).

2.2.3 數(shù)據(jù)大小價值

GDLF算法認(rèn)為數(shù)據(jù)值能夠影響緩存數(shù)據(jù)的個數(shù),通常移除那些較大的數(shù)據(jù)以容納更多的小數(shù)據(jù),并認(rèn)為較大的數(shù)據(jù)擁有較高的數(shù)據(jù)價值,較小的數(shù)據(jù)擁有較低的數(shù)據(jù)價值,考慮到柵格影像金字塔瓦片的數(shù)據(jù)從幾kB到幾百kB不等,GDLVF算法使用加權(quán)數(shù)據(jù)大小代替數(shù)據(jù)大小計算,并以此提出瓦片數(shù)據(jù)大小價值的計算公式：

(5)

式(5)中,Vsize(i)為瓦片數(shù)據(jù)大小價值,WDZ(i)為瓦片數(shù)據(jù)的加權(quán)數(shù)據(jù)大小.

(6)

式(6)中,WDZ(i)為瓦片的加權(quán)數(shù)據(jù)大小,size(i)為瓦片數(shù)據(jù)大小,benchmark_size為基準(zhǔn)數(shù)據(jù),基準(zhǔn)數(shù)據(jù)為緩存瓦片數(shù)據(jù)的平均值.

2.3 用戶行為選擇參與的空間數(shù)據(jù)緩存置換算法

為研究用戶在一定時間范圍內(nèi)對五層十五級瓦片數(shù)據(jù)中產(chǎn)品類型和生產(chǎn)時間的請求分布情況,本文采集了五層十五級瓦片系統(tǒng)的用戶日志,日志中詳細(xì)記錄了用戶名、請求瓦片名稱、產(chǎn)品類型、瓦片生產(chǎn)時間,并抽取其中2份日志進(jìn)行處理分析,結(jié)果如表2所示.以用戶1為例,在日志收集時間范圍內(nèi),共發(fā)送了15 485次瓦片請求,其中GF-1瓦片數(shù)據(jù)的請求數(shù)量占總請求數(shù)量的78%,生產(chǎn)日期為2015年7月的瓦片數(shù)據(jù)請求總數(shù)占所有瓦片請求總數(shù)的72%.由此可見，在日志搜集時間范圍內(nèi),用戶1的瓦片請求主要集中在某一特定產(chǎn)品類型和生產(chǎn)時間上.

由表2可知,在某種特定需求的驅(qū)動下,用戶在一定的時間周期內(nèi)會對某一產(chǎn)品類型或生產(chǎn)時間的瓦片數(shù)據(jù)進(jìn)行持續(xù)性關(guān)注,對該產(chǎn)品類型或生產(chǎn)時間的瓦片產(chǎn)生了明顯的傾向性(偏好)行為,即為用戶傾向的瓦片數(shù)據(jù),其被用戶再次請求的概率要大于非傾向瓦片數(shù)據(jù).

表2 用戶請求分布表Table 2 User request distribution

GDLVF算法面向傳統(tǒng)的金字塔模型設(shè)計產(chǎn)生,對傳統(tǒng)的金字塔模型瓦片數(shù)據(jù)的緩存效率要高于以FIFO、LFU為代表的傳統(tǒng)緩存置換算法,但是GDLVF算法在緩存五層十五級瓦片數(shù)據(jù)時存在以下局限.

(1)GDLVF算法考慮了瓦片的訪問頻率、空間位置、數(shù)據(jù)大小對瓦片數(shù)據(jù)緩存效率的影響,但是該算法在緩存五層十五級瓦片數(shù)據(jù)時,可能會出現(xiàn)在多個價值相等或相差不大的瓦片數(shù)據(jù)中同時存有用戶傾向瓦片數(shù)據(jù)的情況.此種情況發(fā)生時,GDLVF算法會同等對待這些瓦片,導(dǎo)致用戶傾向的瓦片數(shù)據(jù)可能會被置換刪除.然而，根據(jù)上文分析,用戶傾向的瓦片數(shù)據(jù)被再次訪問的概率要大于非傾向瓦片數(shù)據(jù),前者的實際數(shù)據(jù)價值大于后者,應(yīng)優(yōu)先置換刪除用戶非傾向瓦片數(shù)據(jù).綜上所述,GDLVF無法體現(xiàn)五層十五級用戶行為選擇對緩存效率的影響,不符合五層十五級瓦片對象訪問的局部性規(guī)律.

(2)GDLVF算法將影響瓦片緩存效率的3個因子相乘得到瓦片的數(shù)據(jù)價值,從而使得3個因子對瓦片緩存效率的影響權(quán)重相等.

基于以上分析,用戶行為選擇參與的空間數(shù)據(jù)緩存置換算法認(rèn)為：影響五層十五級瓦片緩存效率的主要因素包括瓦片的空間位置、訪問時間頻率、數(shù)據(jù)大小和用戶行為選擇(即用戶對不同產(chǎn)品類型和生產(chǎn)時間的瓦片的選擇傾向),且用戶行為選擇過程中產(chǎn)生的傾向瓦片的價值大于非傾向瓦片的價值.以此提出用戶行為選擇參與的五層十五級空間數(shù)據(jù)緩存置換算法UPBA：

V(i)=WDspa×Vspatial(i)+WDtm×Vtime(i)+

WDsz×Vsize(i)+WDpro×Vproduct(i)+

WDdt×Vdata_time(i),

(7)

式(7)中,V(i)代表瓦片的空間數(shù)據(jù)價值,Vspatial(i)、Vtime(i)、Vsize(i)分別代表瓦片的空間價值、時間價值、文件大小價值,三者的計算方法與式(2)、(3)、(5)相同,Vproduct(i)代表瓦片的產(chǎn)品類型價值,Vdata_time(i)代表瓦片的生產(chǎn)時間價值.WDspa、WDtm、WDsz、WDpro、WDdt表示各個影響因子對緩存效率影響的權(quán)重,且有WDspa+WDtm+WDsz+WDpro+WDdt=1.

(8)

式(8)中,Vproduct(i)代表瓦片的產(chǎn)品類型價值,count代表瓦片緩存總個數(shù),count(p)代表該產(chǎn)品類型在緩存中的總個數(shù).

(9)

式(9)中,Vdata_time(i)為瓦片的生產(chǎn)時間價值,count為瓦片緩存總個數(shù),count(d)為同一生產(chǎn)時間的瓦片在緩存中的總個數(shù).

3 實驗過程與分析

實驗采用日志驅(qū)動模式,首先通過大量實驗確定每個因子的影響權(quán)重值,在確定每個因子影響權(quán)重后,著重考察UPBA算法在請求命中率、字節(jié)命中率、客戶端流量消耗、服務(wù)器端處理請求個數(shù)4個方面的表現(xiàn),并與FIFO、LRU、LFU、GDLVF算法做對比分析.實驗數(shù)據(jù)最高分辨率100和250 m、生產(chǎn)時間為2014年11月、2015年1、3月的高分一號、高分二號、資源三號影像數(shù)據(jù),瓦片大小均為1 000 pixel×1 000 pixel,以png格式存儲,單個瓦片大小在30～3 072 kB,用日志記錄實驗結(jié)果,采用Android平板客戶端,客戶端與服務(wù)器端使用Http協(xié)議進(jìn)行通信,客戶端漫游路徑根據(jù)隨機方法生成.

本研究最大的難點在于確定式(7)中每個影響因子的權(quán)重值.目前常用的因子權(quán)重確定方法如統(tǒng)計平均法、層次分析法都有一定的主觀性,為減少主觀因素對結(jié)果的影響,本文采用實驗方法確定權(quán)重因子值,大量實驗表明，當(dāng)WDspa=0.03,WDtm=0.03,WDsz=0.7,WDpro=0.12,WDdt=0.12時,緩存置換效率最高.

圖2、圖3分別為FIFO、LFU、LRU、GDLVF、UPBA 5種緩存置換算法的請求命中率和字節(jié)命中率,實驗設(shè)定客戶端最大緩存空間為500 MB,命中率取客戶端發(fā)送200次請求的命中率的平均值,由圖2可見,UPBA在所有情況下命中率都要大于其他4類緩存置換算法,并且優(yōu)勢明顯,在相對緩存為20%時,UPBA算法相較其他緩存置換算法命中率提高超過100%.在相對緩存50%以內(nèi),FIFO、LFU、LRU、GDLVF對五層十五級瓦片數(shù)據(jù)的請求命中率和字節(jié)命中率基本相同,在相對緩存50%以上,LFU命中率要高于FIFO、LRU、GDLVF,但是幾種算法相差不大.

圖2 相對緩存與請求命中率的關(guān)系Fig.2 Relationship between the request hit rate and relative cache size

圖3 相對緩存與字節(jié)命中率的關(guān)系Fig.3 Relationship between the byte hit rate and relative cache size

圖4 相對緩存與客戶端流量消耗關(guān)系Fig.4 Relationship between client traffic consumption and relative cache size

圖4為在不同的相對緩存下,發(fā)送200次瓦片請求后,客戶端的流量消耗.隨著相對緩存的不斷增加,客戶端200次瓦片請求的流量消耗不斷下降,在不使用緩存的情況下即相對緩存為0時,客戶端發(fā)送200次瓦片請求需要消耗1 955.257 MB流量,流量消耗巨大,當(dāng)相對緩存為100%即客戶端可以緩存500 MB瓦片時,200次請求所消耗的流量為763.262 MB,僅為不開啟緩存時的39%,節(jié)省流量近1 191.995 MB,效果顯著.

圖5 相對緩存與服務(wù)器端處理瓦片效率關(guān)系Fig.5 Relationship between tile handled efficiency and relative cache size

圖5給出了服務(wù)器端處理瓦片效率與相對緩存的關(guān)系,在不使用UPBA算法的情況下,服務(wù)器平均每秒處理1.21個(1 000個請求需要826 s)瓦片請求,在使用UPBA算法后,等相對緩存為100%時服務(wù)器平均每秒處理0.465個瓦片,僅為不使用UPBA算法時的38.4%,降低了服務(wù)器端的負(fù)載,從而可以支持更高的用戶并發(fā)數(shù).

4 結(jié) 論

分析了現(xiàn)有緩存置換算法FIFO、LFU、LRU、GDLVF的優(yōu)缺點,考慮五層十五級瓦片數(shù)據(jù)多源、異構(gòu)的特點,提出了用戶行為選擇參與的五層十五級瓦片數(shù)據(jù)的緩存置換算法UPBA.實驗表明,相較于傳統(tǒng)緩存置換算法和GDLVF算法，UPBA算法在請求命中率和字節(jié)命中率上的表現(xiàn)具有明顯優(yōu)勢,同時降低了客戶端的流量消耗以及服務(wù)器端的負(fù)載.UPBA算法目前使用文件緩存以提高瓦片數(shù)據(jù)加載顯示的效率,下一步工作可嘗試在內(nèi)存中加入緩存，以進(jìn)一步提高瓦片數(shù)據(jù)加載顯示的效率.

[1] 段龍方.面向遙感數(shù)據(jù)的云數(shù)據(jù)庫技術(shù)研究與應(yīng)用[D].開封：河南大學(xué),2014.

DUAN Longfang. The Research and Application of Cloud Database Technology for Remote Sensing Data[D]. Kaifeng: Henan University,2014.

[2] 王浩,俞占武,曾武,等.網(wǎng)絡(luò)地理信息服務(wù)中的空間數(shù)據(jù)緩存算法研究[J].測繪學(xué)報,2009,38(4)：348-355.

WANG Hao, YU Zhanwu, ZENG Wu, et al. The research on the algorithm of spatial data cache in network geographic information service[J]. Acta Geodaetica et Cartographics Sinica,2009,38(4):348-355.

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

TU Zhengfa, MENG Lingkui, ZHANG Wen, et al. Research on the lowest-value cache replacement algorithm of geospatial data in Network GIS[J]. Journal of Huazhong Normal University: Natural Sciences,2012,46(2):230-234.

[4] 劉磊,熊小鵬.最小駐留價值緩存替換算法[J].計算機應(yīng)用,2013,33(4)：1018-1022.

LIU Lei, XIONG Xiaopeng. Least cache value replacement algorithm[J]. Journal of Computer Applications,2013,33(4):1018-1022.

[5] 石磊,葉海琴,衛(wèi)琳,等.Web緩存命中率與字節(jié)命中率關(guān)系[J].計算機工程,2007,44(13)：84-86.

SHI Lei, YE Haiqin, WEI Lin, et al. Relationship between hit ratio and byte hit ratio of web caching[J]. Computer Engineering,2007,44(13):84-86.

[6] 王小燕.一種高效的流媒體代理緩存替換算法[J].計算機工程,2009,35(14)：72-74.

WANG Xiaoyan. High effective stream media proxy cache replacement algorithm[J]. Computer Engineering,2009,35(14):72-74.

[7] 王棟,鄭逢斌,賴包積,等.基于五層十五級遙感數(shù)據(jù)結(jié)構(gòu)的并行算法研究[J].微計算機信息,2012,28(1)：166-167.

WANG Dong, ZHENG Fengbin, LAI Baoji, et al. A new parallel algorithm based on Five-layer Fifteen-level remote sensing data[J]. Microcomputer Information,2012,28(1):166-167.

[8] 王嘯.基于新技術(shù)的海量遙感影像并行切分方法研究[D].開封：河南大學(xué),2012.

WANG Xiao. Research of Remote Sensing Image Parallel Segmentation Method Based on the New Technology[D]. Kaifeng: Henan University,2012.

[9] PODLIPNIG S, BOSZORMENYI L. A survey of web cache replacement strategies[J]. ACM Computing Surveys,2003,35(4):374-398.

[10] 盧秉亮,梅義博,劉娜.位置相關(guān)查詢中基于最小訪問代價的緩存替換算法[J].計算機應(yīng)用,2011,31(3):690-693.

LU Bingliang, MEI Yibo, LIU Na. Cache replacement method based on lowest access cost for location dependent query[J]. Journal of Computer Applications,2011,31(3):690-693.

Research on the user preference based cache replacement algorithm of the Five-layer Fifteen-level tile.

CHU Xin1,2, CAI Yangjun3, DU Zhenhong1,2, ZHANG Feng1,2, LIU Renyi2, WANG Liangang1,2, HE Jing1,2

(1.ZhejiangProvincialKeyLabofGIS,ZhejiangUniversity,Hangzhou310028,China; 2.DepartmentofGeographicInformationScience,ZhejiangUniversity,Hangzhou310027,China; 3.HangzhouHousingSecurityoffice,Hangzhou310006,China)

Traditional tile cache replacement algorithms such as FIFO, LRU, LFU, GDLVF focusing on tile’s access time, access frequency, size, and spatial location relationship, have limitations in practice of caching the Five-layer Fifteen-level tile, and are not suitable for the Five-layer Fifteen-level tile which is multi-source heterogeneous. In this paper, a tile cache replacement algorithm for Five-layer Fifteen-level named UPBA (User Preference Based Tile Cache Replacement Algorithm) was proposed, and its features including user preference, tile access time and frequency, tile size, and spatial location relationship were analyzed. And then, the enhanced tile replacement method of UPBA was presented. The image datasets of GF-1, GF-2 and ZY-3 with resolution of 100 and 250 m, and production time in November of 2014 and January, February, March of 2015 were used in log-driven simulations of UPBA. The result showed that the UPBA had improved the request hit rate and byte hit rate, meanwhile reduced the client traffic consumption and the server load compared to the traditional cache replacement algorithm.

Five-layer Fifteen-level; tile cache replacement; spatial data

2015-12-21.

國家自然科學(xué)基金資助項目(41471313，41101356，41101371，41171321)；國家科技基礎(chǔ)性工作專項(2012FY112300);國家海洋公益性行業(yè)科研專項經(jīng)費資助項目(2015418003，201305012)；浙江省科技攻關(guān)計劃項目(2014C33G20,2013C33051)；中央高?；究蒲袠I(yè)務(wù)費專項資金資助項目(2016XZZX004-02,2016QNA3015).

禇 信(1991-)，ORCID:http://orcid.org/0000-0001-8883-8728,男，碩士研究生，主要從事移動GIS、GIS及其應(yīng)用研究.

*通信作者，ORCID:http://orcid.org/0000-0001-9449-0415,E-mail:duzhenhong@zju.edu.cn.

10.3785/j.issn.1008-9497.2016.04.012

TN 433

A

1008-9497(2016)04-452-06

Journal of Zhejiang University(Science Edition), 2016,43(4):452-457