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

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

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

?

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

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

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

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

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

瓦片數(shù)據(jù)的實(shí)時(shí)快速加載是提高網(wǎng)絡(luò)GIS服務(wù)質(zhì)量的重要內(nèi)容,客戶端緩存瓦片數(shù)據(jù)則是提高GIS服務(wù)質(zhì)量的重要途徑.五層十五級(jí)瓦片數(shù)據(jù)組織模型按比例對(duì)瓦片數(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ù)存儲(chǔ)在本地,以減少數(shù)據(jù)的請(qǐng)求頻率和網(wǎng)絡(luò)傳輸量,快速響應(yīng)請(qǐng)求,進(jìn)而提升客戶端的用戶體驗(yàn)[2].并且當(dāng)客戶端緩存存儲(chǔ)區(qū)快飽和時(shí),可通過(guò)緩存置換算法選擇并刪除部分瓦片[3],以緩存從服務(wù)器端響應(yīng)請(qǐng)求所返回的新瓦片.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)

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

2.2.1 空間位置價(jià)值

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

(2)

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

2.2.2 時(shí)間價(jià)值

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

(3)

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

(4)

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

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

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

(5)

式(5)中,Vsize(i)為瓦片數(shù)據(jù)大小價(jià)值,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ù)緩存置換算法

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

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

表2 用戶請(qǐng)求分布表Table 2 User request distribution

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

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

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

基于以上分析,用戶行為選擇參與的空間數(shù)據(jù)緩存置換算法認(rèn)為：影響五層十五級(jí)瓦片緩存效率的主要因素包括瓦片的空間位置、訪問(wèn)時(shí)間頻率、數(shù)據(jù)大小和用戶行為選擇(即用戶對(duì)不同產(chǎn)品類型和生產(chǎn)時(shí)間的瓦片的選擇傾向),且用戶行為選擇過(guò)程中產(chǎn)生的傾向瓦片的價(jià)值大于非傾向瓦片的價(jià)值.以此提出用戶行為選擇參與的五層十五級(jí)空間數(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ù)價(jià)值,Vspatial(i)、Vtime(i)、Vsize(i)分別代表瓦片的空間價(jià)值、時(shí)間價(jià)值、文件大小價(jià)值,三者的計(jì)算方法與式(2)、(3)、(5)相同,Vproduct(i)代表瓦片的產(chǎn)品類型價(jià)值,Vdata_time(i)代表瓦片的生產(chǎn)時(shí)間價(jià)值.WDspa、WDtm、WDsz、WDpro、WDdt表示各個(gè)影響因子對(duì)緩存效率影響的權(quán)重,且有WDspa+WDtm+WDsz+WDpro+WDdt=1.

(8)

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

(9)

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

3 實(shí)驗(yàn)過(guò)程與分析

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

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

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

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

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

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

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

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

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

4 結(jié) 論

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

[1] 段龍方.面向遙感數(shù)據(jù)的云數(shù)據(jù)庫(kù)技術(shù)研究與應(yīng)用[D].開(kāi)封：河南大學(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].測(cè)繪學(xué)報(bào),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的最小價(jià)值空間數(shù)據(jù)緩存替換算法研究[J].華中師范大學(xué)學(xué)報(bào)：自然科學(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] 劉磊,熊小鵬.最小駐留價(jià)值緩存替換算法[J].計(jì)算機(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].計(jì)算機(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].計(jì)算機(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] 王棟,鄭逢斌,賴包積,等.基于五層十五級(jí)遙感數(shù)據(jù)結(jié)構(gòu)的并行算法研究[J].微計(jì)算機(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].開(kāi)封：河南大學(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)查詢中基于最小訪問(wèn)代價(jià)的緩存替換算法[J].計(jì)算機(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.

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

禇 信(1991-)，ORCID:http://orcid.org/0000-0001-8883-8728,男，碩士研究生，主要從事移動(dòng)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