马尔可夫模型在空间数据预取中的应用

一、引?? 言

互联网技术的进步推动了空间信息服务的发展, 网络成为人们获取空间信息的主要途径。然而, 由于网络带宽的限制, 用户浏览空间数据时仍要长时间等待。减少等待时间常采用两种方法: 缓存( cach ing)与预取( prefetching)。

大多数 G IS 服务器都采用了分层分块缓存技术[ 1??3] , 预先将矢量或栅格数据输出为大小固定的瓦片( tile)。在这种模式下, 客户端向服务器发送数据请求, 服务器根据范围参数返回已缓存的瓦片。用户执行放大、缩小、漫游等操作后, 浏览的范围改变, 客户端向服务器发送新的请求。下一时刻可能浏览的瓦片与当前的浏览范围及下一步的操作相关, 因此, 可以在空闲时猜测下一时刻可能浏览的数据并下载至本地。最为常用的方法为邻近区域预取, 即在空闲时下载与当前浏览区域相邻的瓦片。如果下一步用户执行平移操作, 本地缓存可能已包括全部或部分所需的瓦片数据。邻近区域预取只考虑了平移操作, 准确率低且容易导致网络拥塞。本文将重点讨论分层分块缓存模式下瓦片的预取, 试图借鉴网页预取的研究成果, 应用 M arkov模型提高预测的准确性。

在网页预取中, M arkov模型的应用已有较多的研究。B estavros最早使用转移概率矩阵描述用户的浏览特征[ 4] , 模型简单、有效。 Sarukkai在 EPA 服务器日志文件上的试验表明[ 5] , 采用基本M arkov链模型对用户的浏览进行预测, 其准确率可以达到70% 左右。上述模型均采用一个 M arkov链描述所有用户的浏览特征, 存储转移概率矩阵的复杂度是网页数量的平方, 而且采用高阶转移矩阵所需的存储空间还会成倍增加。为减少存储空间、提高预测准确率, 邢永康等人提出了多 M arkov链[ 6] , 将用户分为不同类别并用不同的M arkov链表示不同类别用户的浏览特征。

空间数据浏览(包括矢量与栅格, 以下统称为地图浏览)与网页浏览具有相似性, 可将任意时刻窗口中的地图视为网页, 将地图操作视为网页中的超链接。不使用分层分块, 这样的地图有无穷多个, 不能应用M arkov预测模型。一种可能的方式是, 使用分层分块技术将数据划分为有限个瓦片, 用瓦片作为转移状态。然而, 与网页浏览不同, 用户可以同时浏览多个瓦片但只能浏览一个网页。文献[ 7??8]用前 k次瓦片移动方向作为转移状态, 假定所有瓦片具有相同的转移概率, 提出了邻近选择M arkov链( ne ighbor se??

lection m arkov cha in, NSMC)。该模型简单, 存储开销小, 但是模型没有充分考虑空间数据组织形式, 适合于仅有一个比例尺的情形。此外, 空间地物重要性不同, 被访问的几率差别较大, NSMC模型不能体现这一差异特征。本文将结合服务器缓存技术与客户端显示技术, 探讨适用于地图浏览的M arkov预测模型。

二、Markov预测模型

更多内容请查看pdf