论文部分内容阅读
公共地图服务的广泛应用带来了大量的访问需求，导致网络流量急剧增加，造成网络拥塞，服务器过载和传输时延，严重地影响了公共地图服务的服务质量。挖掘群体用户访问的模式与规律，用以推测用户下一步的访问行为，从而有效地在服务器端进行缓存预取，成为提高公共地图服务性能和质量的关键方法之一。公共地图服务的预取策略研究已经有很多，大多基于客户端用户对空间数据访问的时间或者空间局部性，但是时间和空间局部性只是一种定性描述，并没有精确的定量表达，使得预取不够精确。而精确的预取往往采用马尔科夫模型，但是直接地运用马尔科夫模型会产生庞大的计算开销，且存储复杂度高。本文基于马尔科夫模型，根据群体用户对空间数据瓦片访问的区域空间聚集性求取区域访问的转移概率，再结合瓦片访问的时空局部性进行预取并缓存，不仅在预取上更为精确，而且在一定程度下减少了计算开销。本文首先基于群体用户对瓦片访问的空间聚集性，对访问的瓦片进行基于位置的聚类，将瓦片划分为多个小的空间聚集区域。其中，每层的聚类个数依据瓦片所在的层、该层被访问的瓦片总数和缓存的储存容量来确定。然后基于群体用户访问在时间上的连续性，建立聚集区域的马尔科夫转移概率矩阵，获得各个聚集区域在时间上被连续访问的概率，从而基于时间局部性对用户下一步访问的区域进行预测。最后结合公共地图服务器端缓存的容量，对概率较高的区域进行预取。当某个区域内的瓦片不能完全被预取时，对瓦片进行访问概率排序，优先预取访问概率高的瓦片。实验表明，本文提出的基于群体用户访问区域时空局部性的预取策略具有较高的预取准确率，且基于空间聚集性的区域马尔科夫模型减少了大量的计算开销。该策略在应对群体用户的并发访问，有效利用有限的缓存容量和维护公众地图服务系统稳定性等方面有着良好的性能。