馬爾可夫模型在空間數(shù)據(jù)預(yù)取中的應(yīng)用

一、引?? 言

互聯(lián)網(wǎng)技術(shù)的進(jìn)步推動(dòng)了空間信息服務(wù)的發(fā)展, 網(wǎng)絡(luò)成為人們獲取空間信息的主要途徑。然而, 由于網(wǎng)絡(luò)帶寬的限制, 用戶瀏覽空間數(shù)據(jù)時(shí)仍要長(zhǎng)時(shí)間等待。減少等待時(shí)間常采用兩種方法: 緩存( cach ing)與預(yù)取( prefetching)。

大多數(shù) G IS 服務(wù)器都采用了分層分塊緩存技術(shù)[ 1??3] , 預(yù)先將矢量或柵格數(shù)據(jù)輸出為大小固定的瓦片( tile)。在這種模式下, 客戶端向服務(wù)器發(fā)送數(shù)據(jù)請(qǐng)求, 服務(wù)器根據(jù)范圍參數(shù)返回已緩存的瓦片。用戶執(zhí)行放大、縮小、漫游等操作后, 瀏覽的范圍改變, 客戶端向服務(wù)器發(fā)送新的請(qǐng)求。下一時(shí)刻可能瀏覽的瓦片與當(dāng)前的瀏覽范圍及下一步的操作相關(guān), 因此, 可以在空閑時(shí)猜測(cè)下一時(shí)刻可能瀏覽的數(shù)據(jù)并下載至本地。最為常用的方法為鄰近區(qū)域預(yù)取, 即在空閑時(shí)下載與當(dāng)前瀏覽區(qū)域相鄰的瓦片。如果下一步用戶執(zhí)行平移操作, 本地緩存可能已包括全部或部分所需的瓦片數(shù)據(jù)。鄰近區(qū)域預(yù)取只考慮了平移操作, 準(zhǔn)確率低且容易導(dǎo)致網(wǎng)絡(luò)擁塞。本文將重點(diǎn)討論分層分塊緩存模式下瓦片的預(yù)取, 試圖借鑒網(wǎng)頁(yè)預(yù)取的研究成果, 應(yīng)用 M arkov模型提高預(yù)測(cè)的準(zhǔn)確性。

在網(wǎng)頁(yè)預(yù)取中, M arkov模型的應(yīng)用已有較多的研究。B estavros最早使用轉(zhuǎn)移概率矩陣描述用戶的瀏覽特征[ 4] , 模型簡(jiǎn)單、有效。 Sarukkai在 EPA 服務(wù)器日志文件上的試驗(yàn)表明[ 5] , 采用基本M arkov鏈模型對(duì)用戶的瀏覽進(jìn)行預(yù)測(cè), 其準(zhǔn)確率可以達(dá)到70% 左右。上述模型均采用一個(gè) M arkov鏈描述所有用戶的瀏覽特征, 存儲(chǔ)轉(zhuǎn)移概率矩陣的復(fù)雜度是網(wǎng)頁(yè)數(shù)量的平方, 而且采用高階轉(zhuǎn)移矩陣所需的存儲(chǔ)空間還會(huì)成倍增加。為減少存儲(chǔ)空間、提高預(yù)測(cè)準(zhǔn)確率, 邢永康等人提出了多 M arkov鏈[ 6] , 將用戶分為不同類別并用不同的M arkov鏈表示不同類別用戶的瀏覽特征。

空間數(shù)據(jù)瀏覽(包括矢量與柵格, 以下統(tǒng)稱為地圖瀏覽)與網(wǎng)頁(yè)瀏覽具有相似性, 可將任意時(shí)刻窗口中的地圖視為網(wǎng)頁(yè), 將地圖操作視為網(wǎng)頁(yè)中的超鏈接。不使用分層分塊, 這樣的地圖有無(wú)窮多個(gè), 不能應(yīng)用M arkov預(yù)測(cè)模型。一種可能的方式是, 使用分層分塊技術(shù)將數(shù)據(jù)劃分為有限個(gè)瓦片, 用瓦片作為轉(zhuǎn)移狀態(tài)。然而, 與網(wǎng)頁(yè)瀏覽不同, 用戶可以同時(shí)瀏覽多個(gè)瓦片但只能瀏覽一個(gè)網(wǎng)頁(yè)。文獻(xiàn)[ 7??8]用前 k次瓦片移動(dòng)方向作為轉(zhuǎn)移狀態(tài), 假定所有瓦片具有相同的轉(zhuǎn)移概率, 提出了鄰近選擇M arkov鏈( ne ighbor se??

lection m arkov cha in, NSMC)。該模型簡(jiǎn)單, 存儲(chǔ)開銷小, 但是模型沒有充分考慮空間數(shù)據(jù)組織形式, 適合于僅有一個(gè)比例尺的情形。此外, 空間地物重要性不同, 被訪問的幾率差別較大, NSMC模型不能體現(xiàn)這一差異特征。本文將結(jié)合服務(wù)器緩存技術(shù)與客戶端顯示技術(shù), 探討適用于地圖瀏覽的M arkov預(yù)測(cè)模型。

二、Markov預(yù)測(cè)模型

更多內(nèi)容請(qǐng)查看pdf