Adaptation of a Neighbor Selection Markov Chain for Prefetching Tiled Web GIS Data
Adaptation of a Neighbor Selection Markov Chain for Prefetching Tiled Web GIS Data
复制标题
DOI：
10.1007/3-540-36077-8_21
复制
发表时间：
2002-10
期刊：
影响因子：
--
通讯作者：
Dong-Ho Lee;Jungsup Kim;Soo Duk Kim;Kichang Kim;Yoo-Sung Kim;Jaehyun Park
中科院分区：
文献类型：
--
作者：
Dong-Ho Lee;Jungsup Kim;Soo Duk Kim;Kichang Kim;Yoo-Sung Kim;Jaehyun Park
随着互联网使用的增长，许多有用的数据都在互联网上提供。地图等地理数据就是其中之一。然而，由于地理数据通常是非常庞大的，它需要特殊的处理，在服务。一个有用的技术是平铺。例如，地图被分成称为瓦片的较小的块，并逐个瓦片提供。由于客户端通常依次请求多个图块，因此缓存一些流行的图块以供将来使用或预取尚未请求但预计很快会被请求的图块是有益的。我们提出了预测正确的瓦片预取的技术。我们的技术是基于一个观察，即一旦一个瓷砖已被要求有一个强烈的趋势，相邻的瓷砖被要求在下一步。哪个邻居的概率最高是我们应该回答的问题。我们提出了两种技术。一种是基于概率的：我们计算瓦片之间的转移概率，并预取最可能的邻居。另一种是previous-k-movement方法，我们监控客户端在到达当前图块之前所做的前k次移动，并根据它们预测下一次移动。一个叫做“邻居选择马尔可夫链”的图被用来帮助预测。我们解释这两种方法，比较它们，并显示实验结果。
With the growth of internet usage, many kinds of useful data are served in the internet. Geographic data such as a map is one of them. However since geographic data is usually very huge, it needs special treatment in serving. One useful technique is tiling. For example, a map is divided into smaller pieces called a tile, and served tile by tile. Since the client usually requests several tiles in sequence, it is beneficial to cache some of the popular tiles for future usage or prefetching ones that are not requested yet but are expected soon. We propose techniques for predicting the right tiles to prefetch. Our techniques are based on an observation that once a tile has been requested there is a strong tendency that neighboring tiles are requested in the next step. Which neighbor has the highest probability is the question we should answer. We propose two techniques. One is probability-based: we compute transition probabilities between tiles and prefetch the most probable neighbor. The other isprevious-k-movementapproach in which we monitor the previous k movements the client made before reaching the current tile and predict the next movement based on them. A graph called “Neighbor Selection Markov Chain” is used to help the prediction. We explain both methods, compare them, and show experimental results.