Prefetching Tiled Internet Data Using a Neighbor Selection Markov Chain
Prefetching Tiled Internet Data Using a Neighbor Selection Markov Chain
复制标题
DOI：
10.1007/3-540-48206-7_9
复制
发表时间：
2001-06
期刊：
影响因子：
--
通讯作者：
Yoo-Sung Kim;Kichang Kim;Soo Duk Kim
中科院分区：
文献类型：
--
作者：
Yoo-Sung Kim;Kichang Kim;Soo Duk Kim
互联网中的大型数据文件（例如地图）以小块形式提供，称为图块。为了提高此类数据的服务速度，我们可以在显示当前图块时预取未来的图块。传统的预取技术检查块之间的转换概率以预测要请求的下一个块。然而，当瓦片空间非常巨大，并且其中很大一部分被均匀分布地访问时，监控所有这些瓦片的成本非常高。在本文中，我们提出了一种通过使用 NSMC（邻居选择马尔可夫链）捕获图块请求模式中的规律性并基于它预测未来图块请求的技术。使用我们的技术所需的规律性是，要请求的下一个图块取决于图块空间中的先前k个移动（或请求）。地图在某种意义上显示了这种规律性。电子图书表现出很强的这种规律性。我们展示了如何构建 NSMC 并通过实验衡量其预测能力。
A large data file in the internet such as a map is served in small pieces, called tiles. To improve the service speed for such data, we can prefetch future tiles while the current one is being displayed. Traditional prefetching techniques examine the transition probabilities among the tiles to predict the next tile to be requested. However, when the tile space is very huge, and a large portion of it is accessed with even distribution, it is very costly to monitor all those tiles. In this paper, we propose a technique that captures the regularity in the tile request pattern by using an NSMC (Neighbor Selection Markov Chain) and predicts future tile requests based on it. The required regularity to use our technique is that the next tile to be requested is dependent on previouskmovements (or requests) in the tile space. Map shows such regularity in a sense. Electronic books show a strong such regularity. We show how to build an NSMC and measure its prediction capability through experimentations.