[發(fā)明專利]用于網(wǎng)絡(luò)空間信息服務(wù)系統(tǒng)的空間信息集群緩存預(yù)取方法

有效

• 申請?zhí)枺?/td>: 201110242750.6
• 申請日: 2011-08-23
• 公開（公告）號: CN102355490A
• 公開（公告）日: 2012-02-15
• 發(fā)明（設(shè)計）人: 李銳;徐正全;郭銳
• 申請（專利權(quán)）人: 武漢大學(xué)
• 主分類號: H04L29/08
• 分類號: H04L29/08
• 代理公司: 武漢科皓知識產(chǎn)權(quán)代理事務(wù)所(特殊普通合伙) 42222
• 代理人: 張火春

技術(shù)領(lǐng)域

本發(fā)明屬于網(wǎng)絡(luò)空間信息服務(wù)技術(shù)領(lǐng)域，特別涉及面對大規(guī)模用戶高強(qiáng)度漫游訪問的網(wǎng)絡(luò)空間信息服務(wù)系統(tǒng)的空間信息集群緩存預(yù)取方法。

背景技術(shù)

網(wǎng)絡(luò)空間信息服務(wù)系統(tǒng)（網(wǎng)絡(luò)GIS）日益流行使其訪問量經(jīng)歷了持續(xù)高速增長。例如NASA?World?Wind?的數(shù)據(jù)請求數(shù)達(dá)到了每天650萬次,所涉及的空間信息量超過155GB；Google?Earth?與Google?Maps訪問量在06年已超過1億；法國推出的衛(wèi)星地圖Geoportail，首日訪問量即達(dá)到了500萬。面對大規(guī)模和高強(qiáng)度的用戶訪問請求，空間信息集群服務(wù)器端緩存預(yù)取技術(shù)在節(jié)省網(wǎng)絡(luò)帶寬、減輕后端服務(wù)器負(fù)載壓力、縮短用戶請求響應(yīng)時間等方面，具有巨大的優(yōu)勢，可用于滿足用戶在漫游數(shù)字地球時對空間信息服務(wù)質(zhì)量感知需求。但確定預(yù)取候選對象一直是預(yù)取技術(shù)的難點(diǎn)。建立有效的用戶漫游預(yù)測模型，對用戶漫游過程作出準(zhǔn)確的預(yù)測，是空間信息集群緩存預(yù)取的關(guān)鍵。

緩存預(yù)取實(shí)際上是一種主動緩存技術(shù)，緩存系統(tǒng)利用用戶對數(shù)據(jù)的訪問請求模式的先驗(yàn)知識，當(dāng)緩存處理當(dāng)前用戶數(shù)據(jù)請求時，預(yù)測該客戶在最近的將來將要訪問的數(shù)據(jù)并預(yù)先從服務(wù)器中將對應(yīng)的數(shù)據(jù)獲取回來并放在緩存存儲區(qū)中。可見，緩存預(yù)取技術(shù)中，最核心的部分是對用戶未來數(shù)據(jù)請求的準(zhǔn)確預(yù)測[1]。緩存預(yù)取技術(shù)，具有明顯的雙面效應(yīng)。如果預(yù)測準(zhǔn)確，將對應(yīng)的數(shù)據(jù)預(yù)先存儲在緩存服務(wù)器，則下一時刻用戶訪問該數(shù)據(jù)時，將直接由緩存響應(yīng)，大大地降低了用戶數(shù)據(jù)請求響應(yīng)時間；否則，如果預(yù)測不準(zhǔn)確，不但沒有將用戶下一時刻將要訪問的數(shù)據(jù)預(yù)先存儲在緩存中，沒有起到降低用戶數(shù)據(jù)請求響應(yīng)時間的目的，而且，由于預(yù)取無用的數(shù)據(jù)，給服務(wù)器端增加了無任何價值的數(shù)據(jù)訪問，也浪費(fèi)了網(wǎng)絡(luò)資源。

目前，研究人員對網(wǎng)頁的緩存預(yù)取做出了很多有益研究，多采用馬爾可夫模型（Markov模型）提高預(yù)取的準(zhǔn)確率，且都針對單客戶端的操作預(yù)取。在網(wǎng)絡(luò)GIS領(lǐng)域，緩存預(yù)取方面研究相對較少。傳統(tǒng)空間數(shù)據(jù)緩存預(yù)取的方法采用分層分塊的緩存預(yù)取技術(shù)，預(yù)先將矢量或柵格數(shù)據(jù)輸出為大小固定的瓦片(?tile)，根據(jù)當(dāng)前時刻瀏覽瓦片范圍，預(yù)測下一時刻可能要訪問的瓦片集合[2]；文獻(xiàn)[3]提出基于概率的瓦片預(yù)取算法，該算法考慮到當(dāng)前瓦片鄰近瓦片范圍，計算所有相關(guān)瓦片的訪問概率并選擇前t個（預(yù)取個數(shù)）概率最大的瓦片進(jìn)行預(yù)取，但這種概率排序的合理性未給出；文獻(xiàn)[4]提出了基于前K步瓦片移動的鄰居瓦片選擇Markov鏈的算法來預(yù)取用戶未來可能訪問的瓦片，在一定程度上提高了系統(tǒng)性能，但因假定所有瓦片具有相同的訪問轉(zhuǎn)移概率，而未考慮空間地物重要性不同，及被訪問概率的差別；文獻(xiàn)[5]提出基于希波特（Hillbert）曲線的預(yù)取方法，使用此聚類方法來反映空間數(shù)據(jù)的“空間位置性”，利用兩個空間對象Hilbert值的差異程度來判斷空間對象之間的距離遠(yuǎn)近，設(shè)置一個距離閾值，將閾值范圍內(nèi)的空間對象設(shè)置為預(yù)測的對象集合；文獻(xiàn)[6]通過大量學(xué)習(xí)樣本，驗(yàn)證基本Markov預(yù)測模型能有效地提高瓦片數(shù)據(jù)的預(yù)取命中率，但由于地圖瀏覽與網(wǎng)頁瀏覽的過程不同，高階Markov模型不會提高預(yù)測準(zhǔn)確率。以上研究都關(guān)注于瓦片當(dāng)前的轉(zhuǎn)移狀態(tài)，考慮到其空間距離上相鄰的瓦片總是傾向于在被訪問時間上也相鄰，即瓦片的空間局部性。并且各個方法中訪問概率的獲取基本通過假設(shè)初始值或經(jīng)過較長學(xué)習(xí)過程確定其概率，而其學(xué)習(xí)數(shù)據(jù)的選取是個隨機(jī)過程。

研究證明空間數(shù)據(jù)瓦片訪問請求存在訪問傾斜和重復(fù)性，符合社會學(xué)中的“二八原則”，即百分之二十的瓦片吸引了百分之八十的請求，空間數(shù)據(jù)瓦片的長期訪問概率與其訪問排名之間符合齊普夫（Zipf）分布規(guī)律[7]。且因Zipf分布及其分布規(guī)律反映了群體用戶的行為，可以用于建立有效集群緩存機(jī)制，建立基于熱點(diǎn)數(shù)據(jù)的用戶訪問集群緩存模型，將訪問頻率（F_i）高的瓦片請求直接由服務(wù)器緩存響應(yīng)，而不需要對后端的存儲設(shè)備進(jìn)行重復(fù)讀取，以此節(jié)省大量的I/O?帶寬，縮短用戶響應(yīng)時間[8]。